[C&++] ASCII 轉存記憶體 ( 字串轉二進位大數 )－Edison.X. Blog

這問題還真不知怎麼下標題。原問題是 ptt 上問的，我也給了一份 solution。由於認為這篇給的 solution 留下很多談論空間 ( 其實還不是自己懶得用 bbs 編輯文字 )，於此做下一份筆記。

主要是在於輸入 12 bytes 之字串 (假設保證是 is_dig )，要將其代表的數值塞到 2 個 unsigned int (假設 unsigned int 是 32bits) 裡去，再把所提的演算法用虛擬碼表示寫一下。

Procedure ASCII_TO_BIG ( str As Input , big As Result )

(1) calculate len := length of str , IDX = 0
(2) str [ i ] = str [ i ] - ' 0 ' , for 0 <= i < len
(3) initlaize

除數(Divisor) = 2，被除數(Dividend) = 0 ，餘數 (Remainder)=0，
商(Dividend )=0，暫存 R = 0

(4) For i := 0 to len do

(5)     Dividend = str[i] + R < 被除數 = str[i] + 暫存 >
(6) Quotient = Dividend / Divisor < 商 = 被除數 / 除數 >
(7)   Remainder = Mod ( Dividend , Divisor ) < 餘 = 被除模除數 >
(8)     R = 10 * Remainder < 更新暫存 >
(9)     str [ i ] = Quotient < 更下一次迭代之被除數 >

(A) End of For i
(B) big [ IDX / 32 ] = big [ IDX / 32 ] | (1U<<(IDX %32))
(C) IDX:= IDX + 1
(D) IF str[i] = 0 for 0 <=i < len , Procedure ending ；
Otherwise , goto (3)

End Procedure

轉二進位

依我所提之 solution 作法，複雜度 O(n log n)，大概長這樣。

Code Snippet
typedef unsigned int big_[2];
void str2big(char * str, big_ big)
{
    size_t bit_idx = 0;
    size_t big_idx = 0;
    size_t i, len  = 0;
    int    flag = 1;
 
    // trans ASCII array to number array, ++len is worst
    for(i=0; str[i]; ++i, ++len) str[i] -= '0';
    big[0] = big[1] = 0;
 
    // trans to big number struct
    bit_idx = big_idx = 0;
    while(flag){
        const int Divisor = 2;
        int Remainder = 0;
        int Quotient  = 0;
        int Dividend  = 0;
        int R         = 0;
        for(i=0; i<len ; ++i){
            Dividend  = str[i] + R ; // 被除 = str[i] + R
            Quotient  = Dividend / Divisor ; // 求商
            Remainder = Dividend % Divisor ; // 求餘
            R         = 10 * Remainder; // 餘數影響下個被除
            str[i]    = Quotient           ;
        } // end of for
        if(Remainder==1) {
            big_idx = bit_idx / 32;
            big[big_idx] |= (1U<<(bit_idx%32));
        }
 
        flag=0;
        for(i=0; i<len; ++i)
            if(str[i]!=0) {
                flag = 1;
                break;
            }
            ++bit_idx;
    } // end of whlie
}

這份粗略的原始碼只修細項的話 (如修掉贅變數、乘除法以 Bitwise 取代)，大概可再加快 10% ~ 20% 左右。事實上以這份碼而言，有很多重算的地方。

減少不必要的計算 : 修正起始位址

我們以 "1123" 為例。

"1123" 做連除法時，LEN = 0~3，消掉得到 "0561"；
"0561" 做連除法時，LEN = 0~3，消掉得到 "0280"； (! 注意這裡開始有問題 )
....
"0004" 做連除法時，LEN = 0~3，消掉得到 "0002"；

注意到，前面的 0 事實上都是多做的，我們可以直接跳到「第一個非零」的位址直接做即可。故在程式碼中，若新增了一變數 pos ，是專門儲存「第一個非零」位置變數，可省下一堆空計算時間 ( 對長字串之處理尤為明顯 )。

Code Snippet
typedef unsigned int big_[2];
void str2big(char * str, big_ big)
{
    size_t i, len;
    size_t pos , bit_idx=0;
 
    for(len=0; str[len]!=0; ++len) str[len]&=0xf;
    for(pos=0; str[pos]==0 && pos < len; ++pos);
    big[0] = big[1] = 0;
 
    while( pos != len){
        const int Divisor = 2;
        int Remainder = 0;
        int Quotient  = 0;
        int Dividend  = 0;
        int R         = 0;
 
        for(i=pos; i<len ; ++i){
            Dividend  = str[i] + R         ;
            Quotient  = Dividend / Divisor ;
            Remainder = Dividend % Divisor ;
            R         = 10 * Remainder     ;
            str[i]    = Quotient           ;
        } // end of for
 
        if(Remainder==1)
            big[bit_idx / 32] |= (1U <<(bit_idx % 32));
        ++bit_idx;
 
        // find next start position
        while(str[pos]==0 && pos<len) ++pos;
    }
}

2^n 進位

事實上最後筆者留了一段伏筆，上面這段效能雖比第一次所撰效能高了，但它是「逐一 bit 」慢慢轉、慢慢判斷。如果一次能轉拿 2 bits、3 bits 這樣慢慢轉的話，效能應該會比較好才對。鑑於此想法，我們將該 ASCII String array，以 65536 進位方式轉換，一次就處理了 16 bits。

最後完整的程式碼如下所示。

Code Snippet
typedef unsigned int big_[2];
void str2big(char * str, big_ big)
{
    size_t i, len;
    size_t pos , bit_idx=0;
    int    num[200];
 
    for(len=0; str[len]!=0; ++len) str[len]&=0xf;
    for(pos=0; str[pos]==0 && pos < len; ++pos);
    big[0] = big[1] = 0;
 
    while( pos != len){
 
        const unsigned int Divisor = 65536;
        int Remainder = 0;
        int Quotient  = 0;
        int Dividend  = 0;
        int R         = 0;
 
        for(i=pos; i<len ; ++i){
            Dividend  = str[i] + R         ;
            Quotient  = Dividend / Divisor ;
            Remainder = Dividend % Divisor ;
            R         = 10 * Remainder     ;
            str[i]    = Quotient           ;
        } // end of for
 
        if(Remainder!=0)//(!) 65536 = 0x00010000, bit(16) = 1
            big[bit_idx*16/32]|=(Remainder<<(bit_idx*16%32));
        ++bit_idx;
 
        // find next start position
        while(str[pos]==0 && pos<len) ++pos;
    }
}

對轉進二個 unsigned int 而言，這樣保證 4 次就可以轉完。

This code is not the best..

一些細節可討論的地方，如一開始要找，字串裡第一個不是 '0' 的位置

Code Snippet
// method 1
for(len=0; str[len]; ++len) str[i]&=0xf;
for(pos = 0; str[pos] && pos < len ; ++pos);
 
// method 2
for(first=1, len=0; str[len]; ++len) {
    if(first && str[len]!='0') first=0, pos=len;
    str[i]&=0xf;
}

還有 Dividend 那段

Code Snippet
// method1
const unsigned int Divisor = 65536;
for(i=pos; i<len ; ++i){
    Dividend  = str[i] + R         ;
    Quotient  = Dividend / Divisor ;
    Remainder = Dividend % Divisor ;
    R         = 10 * Remainder     ;
    str[i]    = Quotient           ;
}
// method2
const unsigned int Divisor = 65536;
for(i=pos; i<len ; ++i){
    Dividend  = str[i] + 10 * Remainder;
    str[i]    = Dividend >> 16 ;
    Remainder = Dividend & 65535 ;
}

還有 if(Remainder!=0) ，實際上是不需要做這判斷的，只會徒增 brach 負擔。

這些細節上的差異就不再討論與贅述。

Q & A

有二個 Q & A 倒是可再思考一下。

Q1 : 以此例而言，為何不挑用 Divisor = (1U << 31) ? 這樣只需要處理兩次就行了。

關鍵在 R = 10 * Remainder，挑用 2^32 進制，會導致計算過程中可能溢位之情況。

Q2 : 為何一般教學用的大數演算法不用此架構？

一般教學用的大數算法多以 10 進位或萬進位為例無誤，挑用 10000 進位 / 65536 進位，筆者認為要挑用萬進位或 65536 進位情形不一定。挑用萬進位好處是從字串轉大數、大數轉字串時速度較快，但計算卻沒 65536 進位來得快；挑用 65536 進位好處是所有運算都比萬進位快 ( 加、減、乘、除、取模、次方) ，原因是大多的運算都可用位元運算子與移位運算子完成，但缺點在於從字串轉大數、大數轉字串較麻煩。特別是大數轉字串會更花時間，同時 65536 進位大數轉字串，還必須多寫一份 10 進位大數演算法。

以一般工程計算上，個人認為確實挑 2^n 進位可能較佳，因計算的次數，大多大於輸出的次數。