應用動態配置記憶體 - 大數乘二算爆你的電腦

好久沒有發文了，又快要被博主通緝了，所以就來談談今天的標題，" 大數乘二 "。
" 大數乘二 " 演算法的開發可以讓讀者練習動態配置記憶體的應用，另外可以複習
一下讀者們可能已經遺忘的對數計算，另外可以順便練習一下條件型的迴圈使用
所以學習寫程式直接透過綜合演練是比較有用，例如在下除了 "C++ : The Core Language"
與 K&R 那本經典的 C 語言書籍，剩下的知識都是直接閱讀各領域的專案原始碼獲得，所以
在下認為純程式語言的書沒啥用，當然這是在下個人觀點，至少對在下是沒啥用，例如
對 C++ 而言，假如讀者沒有另外去學習像 Qt 或是去閱讀 Inside COM 等等這些技術，就很難
了解 C++ 的一些本質 ( 注: 可以參考以前的發文 領略 QT 視窗程式設計)，總之，語言一定
是拿來被應用，有需求才會被創造，所以回到本文，來看看為什麼  " 大數乘二 " 需要動態
配置記憶體呢？ 很簡單，因為用電腦內建的精度就算不出來了，只會給你一個科學記號的
近似值，可是假如要超越 CPU 演算的精度，那就得自己實作演算法。



開發 " 大數乘二 " 演算法需要先了解人類是怎麼做演算動作，然後讓電腦去模擬這種 "乘二"
的動作，這樣就可以達成任意精度，所以本文開發 " 大數乘二 " 演算法的目的，就是為了
計算 二的 N 次方 的精確數字，所以第一件事情當然就是先配置記憶體，這邊就需要預先
知道 二的 N 次方 會有幾位數，這是一個數學問題，讓我們用對數算算看：

圖 1. 二的 N 次方至少有 P 位數

如圖 1 所示，假如要計算 二的 N 次方 ，而且每一個 byte 只存 0 至 9，那麼我們至少得要
配置 P 個 byte，這是最簡單的實現方式，當然還有一些更進階的方法，留給讀者自己去改良
但是預先知道有幾位可以幫助我們節省計算時間，等一下後面實現 " 大數乘二 " 就會用到，
所以讓我們先配置需要用到的記憶體吧，讀者假如是 C++ 的愛用者可以直接用 new 運算子
不過在下的範例程式都是 C 語言，所以使用 malloc，或是用以前介紹過的 Heap API 也可以
動態配置記憶體，malloc 的使用在下不用多說，讀者是程式設計老手的話，應該也用到爛
掉了，新手查查網路就有資料，所以下面只列出程式碼：

pDigitTap = (BYTE*)malloc(g_cdgNumForDec);
ZeroMemory(pDigitTap, g_cdgNumForDec);
pDigitTap[0] = 1;
printf("Allocated %d taps\n", g_cdgNumForDec);

首先配置存放所有運算結果需要的位數，g_cdgNumForDec 的數值就根據圖 1 的公式計算出來
接著先呼叫 ZeroMemory 將配置的記憶體內容清零，然後設定第零個 Tap 為 1 ，因為 C 語言
的陣列從零開始，配置與初始化需要的記憶體完成後，顯示配置了多少 Tap，讓使用者知道
配置了多大的存放空間，讀者可能會有一個疑問，為什麼在下把每一位稱為一個 Tap，這個
讀者就得要有學過 FIR Filter，例如 3-Tap FIR Filter 就有 3 個 Tap 可以放濾波係數，在下把
類似的觀念也套用到要處理的每一位上，在下稱每一位都是一個 Tap，實在不會翻，用圖 2
來表示應該會比較清楚：

圖 2. 數值 9999 存放在一個 4-tap 的數字

前面的程式碼配置了像圖 2 這種記憶體空間，接下來就剩實現 " 大數乘二 " 演算法，來模擬
人類計算乘二的動作，" 乘二 " 是一種很特別的算術，因為它最多只會進一，不會有其他的情
況需要考慮，所以我們只要研究 99 x 2 怎麼計算，其他的情況必然也成立，後面會講 " 乘二 "
有甚麼特別的地方，圖 3 先給出 " 大數乘二 " 演算法的流程圖：

圖 3. 大數乘二 1-Tap 演算法流程圖

" 乘二 " 有甚麼特別的地方地方呢？因為 " 乘二 " 最多只會進一位，所以在 / 10 與 mod 10 的
這兩個步驟可以偷懶一下，將 / 10 與 mod 10 的替換為如下：

Carry = (Val > 9) ? 1      : 0  ;
Tap   = (Val > 9) ? Val-10 : Val;

這樣運算可以省去除法和取餘的動作，加快運算速度，剩下的就沒有甚麼了，照著圖 3 的

演算法寫程式測試而已，下面就給出完整的原始碼：

#include <stdio.h>
#include <windows.h>
/*
==================================================
calc_power_of_two.c
用途：計算任意二的 N 次方的準確數值
前置詞 cdg 表示 count of digits
類似微軟定義的 cch，表示 count of characters
作者 UBIWU
================================================== 
*/
 
/* 使用 timeGetTime API 必須引入 winmm.lib */
#pragma comment(lib, "winmm.lib")
 
/* log10(2.0) ~ 0.30103 */
 
static INT g_cdgNumForBin;
static INT g_cdgNumForDec;
 
/* 大數乘二 */
VOID MultiplyByTwo(BYTE *pdt,SIZE_T len)
{
 BYTE val, digit, carry = 0;
 
 if(pdt == NULL) return;
 
 while(len > 0)
 {
  digit = *pdt;
  val   = digit*2 + carry;
  //carry = val/10;
  //*pdt  = val%10;
  /* 除法與取餘的快速運算版本 */
  carry = (val > 9) ? 1 : 0;
  *pdt  = (val > 9) ? val-10 : val;
  //printf("%d", *pdt); // 除錯用
  pdt++;
  len--;
 }
}
 
int main(int argc,const char *argv[])
{
 BYTE *pDigitTap = NULL;
 ULONG ulCnt, ulLen;
 DWORD dwStart,dwEnd;
 
 if(argc < 2) goto main_exit;
 
 g_cdgNumForBin = atol(argv[1]);
 if(g_cdgNumForBin < 0) goto main_exit;
 printf("Calculate 2^%d...\n", g_cdgNumForBin);
 
 /* 預先計算十進位位數 */
 g_cdgNumForDec = (double)g_cdgNumForBin*0.30103 + 1.0;
 g_cdgNumForDec *= sizeof(BYTE);
 
 /* 配置所需記憶體     */
 pDigitTap = (BYTE*)malloc(g_cdgNumForDec);
 ZeroMemory(pDigitTap, g_cdgNumForDec);
 pDigitTap[0] = 1;
 printf("Allocated %d taps\n", g_cdgNumForDec);
 
 dwStart = timeGetTime();
 
 /* 進行二的 N 次方計算 */
 ulCnt = 0;
 while(ulCnt < g_cdgNumForBin)
 {
  /* 只精確的計算目前需要的位數用於加速運算 */
  UINT cdgNumForDec = (double)(ulCnt+1)*0.30103 + 1.0;
  MultiplyByTwo(pDigitTap, cdgNumForDec /*g_cdgNumForDec*/);
  if(argc > 2 && argv[2][0] == 'v')
   printf("Counter= %d\tNum Of Digits= %d\n", ulCnt, cdgNumForDec);
  ulCnt++;
 }
 
 dwEnd = timeGetTime() - dwStart;
 
 printf("\n");
 /* 列出最後計算結果    */
 ulCnt = g_cdgNumForDec;
 ulLen = 1;
 printf("row 1:\t");
 while(ulCnt > 0)
 {
  printf("%d",pDigitTap[ulCnt - 1]);
  if(ulLen % 50 == 0)
  {
   printf("\n");
   printf("row %d:\t", ulLen/50 + 1);
  }
  ulLen++;
  ulCnt--;
 }
 printf("\nElapsed time = %dms", dwEnd);
 
 /* 釋放配置的記憶體    */
 free(pDigitTap);
 
main_exit:
 return 0;
}

另外記憶體配置完記得得要釋放，在下用 malloc 所以釋放的時候要呼叫 free，其它的就沒啥

好講的啦，讀者可以編譯程式碼自己玩一玩計算任意位數 2 的 N 次方。

下面就給出一個跑 2 的 3151 次方的例子：

讀者們可以看到對電腦來說，算算 2 的 3151 次方只是牛刀小試而已，很快就跑完了，各位
可以試試看輸入很大的數字會怎麼樣 ... 嘿嘿

程式除了第二個參數可以輸入要計算的次方，第三個參數給 v 的話，會列出計算過程，建議
輸入大 N 做計算最好要把 v 加上去，要不然會不知道到第幾次疊代了，例如：

calc_power_of_two 3151 v

這個原型版本給讀者們去玩玩，其實還有很多改良空間，Tap by Tap 只是最簡單的一種形式
不過大概到十萬就要算很久了。

這個程式有啥用呢？哈哈，在下想到的是可以產生很大的垃圾文字檔，例如

calc_power_of_two 3151 > result.txt

這樣就會把結果輸入到 result.txt

讀者可能會好奇詢問怎麼改良 1-Tap 型式更進一步加速演算法
在不考慮與硬體相關使用 GPU 或是多核心的 CPU 程式設計技術
就單一核心 CPU 而言，純粹對演算法作與硬體無關的改良最簡單的
方式為讀者可以思考改成 2-Tap 型式的演算法，就是說每次至少處理兩格
這樣大數乘二的演算法計算量馬上少一半。

注：
本文原始碼上色改用 http://highlight.hohli.com/
這個網站好處是還可以幫程式加行號。

後記：
星期三要去 Conference 真的實在不想去.....
不知道 CNN 學長去法國當參訪學者順不順利
學長回來在跟他聊聊，學長是上個星期四坐飛機...