這問題還真不知怎麼下標題。原問題 是 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
  1. typedef unsigned int big_[2];
  2. void str2big(char * str, big_ big)
  3. {
  4.     size_t bit_idx = 0;
  5.     size_t big_idx = 0;
  6.     size_t i, len  = 0;
  7.     int    flag = 1;
  8.  
  9.     // trans ASCII array to number array, ++len is worst
  10.     for(i=0; str[i]; ++i, ++len) str[i] -= '0';
  11.     big[0] = big[1] = 0;
  12.  
  13.     // trans to big number struct
  14.     bit_idx = big_idx = 0;
  15.     while(flag){
  16.         const int Divisor = 2;
  17.         int Remainder = 0;
  18.         int Quotient  = 0;
  19.         int Dividend  = 0;
  20.         int R         = 0;
  21.         for(i=0; i<len ; ++i){
  22.             Dividend  = str[i] + R ; // 被除 = str[i] + R
  23.             Quotient  = Dividend / Divisor ; // 求商
  24.             Remainder = Dividend % Divisor ; // 求餘
  25.             R         = 10 * Remainder; // 餘數影響下個被除
  26.             str[i]    = Quotient           ;
  27.         } // end of for
  28.         if(Remainder==1) {
  29.             big_idx = bit_idx / 32;
  30.             big[big_idx] |= (1U<<(bit_idx%32));
  31.         }
  32.  
  33.         flag=0;
  34.         for(i=0; i<len; ++i)
  35.             if(str[i]!=0) {
  36.                 flag = 1;
  37.                 break;
  38.             }
  39.             ++bit_idx;
  40.     } // end of whlie
  41. }

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

 

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

 

我們以 "1123" 為例。

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

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

 

Code Snippet
  1. typedef unsigned int big_[2];
  2. void str2big(char * str, big_ big)
  3. {
  4.     size_t i, len;
  5.     size_t pos , bit_idx=0;
  6.  
  7.     for(len=0; str[len]!=0; ++len) str[len]&=0xf;
  8.     for(pos=0; str[pos]==0 && pos < len; ++pos);
  9.     big[0] = big[1] = 0;
  10.  
  11.     while( pos != len){
  12.         const int Divisor = 2;
  13.         int Remainder = 0;
  14.         int Quotient  = 0;
  15.         int Dividend  = 0;
  16.         int R         = 0;
  17.  
  18.         for(i=pos; i<len ; ++i){
  19.             Dividend  = str[i] + R         ;
  20.             Quotient  = Dividend / Divisor ;
  21.             Remainder = Dividend % Divisor ;
  22.             R         = 10 * Remainder     ;
  23.             str[i]    = Quotient           ;
  24.         } // end of for
  25.  
  26.         if(Remainder==1)
  27.             big[bit_idx / 32] |= (1U <<(bit_idx % 32));
  28.         ++bit_idx;
  29.  
  30.         // find next start position
  31.         while(str[pos]==0 && pos<len) ++pos;
  32.     }
  33. }

 

2^n 進位

 

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

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

 

Code Snippet
  1. typedef unsigned int big_[2];
  2. void str2big(char * str, big_ big)
  3. {
  4.     size_t i, len;
  5.     size_t pos , bit_idx=0;
  6.     int    num[200];
  7.  
  8.     for(len=0; str[len]!=0; ++len) str[len]&=0xf;
  9.     for(pos=0; str[pos]==0 && pos < len; ++pos);
  10.     big[0] = big[1] = 0;
  11.  
  12.     while( pos != len){
  13.  
  14.         const unsigned int Divisor = 65536;
  15.         int Remainder = 0;
  16.         int Quotient  = 0;
  17.         int Dividend  = 0;
  18.         int R         = 0;
  19.  
  20.         for(i=pos; i<len ; ++i){
  21.             Dividend  = str[i] + R         ;
  22.             Quotient  = Dividend / Divisor ;
  23.             Remainder = Dividend % Divisor ;
  24.             R         = 10 * Remainder     ;
  25.             str[i]    = Quotient           ;
  26.         } // end of for
  27.  
  28.         if(Remainder!=0)//(!) 65536 = 0x00010000, bit(16) = 1
  29.             big[bit_idx*16/32]|=(Remainder<<(bit_idx*16%32));
  30.         ++bit_idx;
  31.  
  32.         // find next start position
  33.         while(str[pos]==0 && pos<len) ++pos;
  34.     }
  35. }

 

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

 

This code is not the best..

 

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

 

Code Snippet
  1. // method 1
  2. for(len=0; str[len]; ++len) str[i]&=0xf;
  3. for(pos = 0; str[pos] && pos < len ; ++pos);
  4.  
  5. // method 2
  6. for(first=1, len=0; str[len]; ++len) {
  7.     if(first && str[len]!='0') first=0, pos=len;
  8.     str[i]&=0xf;
  9. }

 

還有 Dividend  那段

Code Snippet
  1. // method1
  2. const unsigned int Divisor = 65536;
  3. for(i=pos; i<len ; ++i){
  4.     Dividend  = str[i] + R         ;
  5.     Quotient  = Dividend / Divisor ;
  6.     Remainder = Dividend % Divisor ;
  7.     R         = 10 * Remainder     ;
  8.     str[i]    = Quotient           ;
  9. }
  10. // method2
  11. const unsigned int Divisor = 65536;
  12. for(i=pos; i<len ; ++i){
  13.     Dividend  = str[i] + 10 * Remainder;
  14.     str[i]    = Dividend >> 16 ;
  15.     Remainder = Dividend & 65535 ;
  16. }

 

還有  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 進位可能較佳,因計算的次數,大多大於輸出的次數。

edisonx 發表在 痞客邦 PIXNET 留言(0) 人氣()