結構體與部份函式 續上篇

 

[0] 前言

 

 

(1) 這篇提的大數除大數效能也還不是最好的,但應算「可用」。之前看過的一種作法是:被除數一直去減除數,商慢慢加1。

(2) 這裡提的方法其實可以實作 3  種出來,但最好的我沒時間做出來。

 

 

[1] 直式除法說明

 

 

首先我們觀察位數關係。


9999/10 = 999...9    ---->  4 位數 / 2 位數 = 3 位數

1000/99 = 10 ...10 ---->   4 位數 / 2 位數 = 2 位數

 

所以我們可以得到的結果是: A / B ,得到的結果,最多是 (A 位數 - B 位數 + 1) 位數

我們再想一下 7163456(被除數) / 123(除數) ,一開始的位數會怎麼填?


       ?????
   ┌────────────
123│ 7163456 

 

由於 123 是 3 位數,所以我們一開始也在被除數的前三位數看做一組,做試乘。但如果第一次算完的時候想一下情況會變怎樣

 


       5????
   ┌────────────
123│ 7163456 
     615
   ──────────────
     1013

 

 這時候就變成了 4 位數為一組做除法。而後面我們也不確定到底該是有幾位數做除法,簡單一點的方法是,我們都假設是 123(除數,3位數) 的位數 + 1,統一一次以 4 位 數為一組做試乘。如此一來,就必須在被除數(7163456) 最前面補一個 0。


       ?????
   ┌────────────
12307163456  

 

下面才是真正開始做除法的細節。

我們令被除數 7163456 為 A,除數 123 為 B。

 

---------- (1)第一次迭代 A〔7:4〕 -------------

 


       ????
   ┌───────────
12307163456 



(1.1) 

 


N 從1開始猜到9,先找一個數滿足 >= A〔7:4〕之條件


 B    N    BN    A〔7:4〕
123 * 1 = 123  <  0716
123 * 2 = 246  <  0716
123 * 3 = 369  <  0716
123 * 4 = 492  <  0716
123 * 5 = 615  <  0716
123 * 6 = 738  >  0716

上面的 BN 就代表 B * N 之意思。這裡得到,

N =6
BN=738


(1.2)


N猜到6時,BN已滿足大於等於A〔7:4〕條件,故停下來。


(1.3)


BN=738 > A〔7:4〕,做回覆,

N = N-1

  = 6-1

  = 5

BN= B * N 

  = 0123 * 5 

  = 0615


表格變如下


       ????
   ┌────────────
123│07163456
   │0615
   ──────────────

  

(1.4)

 

這步是重點,注意運算對象。


A〔7:4〕= A〔7:4〕- BN

      = 0716 - 0615 
 
      = 0101


表格

       ????
   ┌────────
123│07163456
   │0615
   ───────────
    0101


再整理一下


       ????
   ┌───────────
123│01013456
   │
   

 

 

----------- (2)第二次迭代 A〔6:3〕 ---------

 


       5???
   ┌─────────
123│01013456

 


(2.1) 


N 從1開始猜到9,先找一個數滿足 >= A〔6:3〕之條件


 B    N    BN    A〔7:4〕
123 * 1 = 123  <  1013
123 * 2 = 246  <  1013
123 * 3 = 369  <  1013
123 * 4 = 492  <  1013
123 * 5 = 615  <  1013
123 * 6 = 738  <  1013
123 * 7 = 861  <  1013
123 * 8 = 984  <  1013
123 * 9 = 1107 >  1013

這裡得到,

N =9
BN=1107


(2.2)


N猜到9時,BN已滿足大於等於A〔6:3〕條件,故停下來。


(2.3)


BN=1107 > A〔6:3〕,做回覆

N = N-1

  = 9-1

  = 8

BN= B * N 

  = 0123 * 8

  = 0984


表格變如下

 

       5???
   ┌───────────
123│01013456
   │ 0984   
   ───────────


  

(2.4)


A〔6:3〕= A〔6:3〕- BN

      = 1013 - 0984 
 
      = 0029


表格


       5???
   ┌──────────
123│01013456
   │ 0984   
   ───────────
     0029


再整理一下


       5???
   ┌───────────
123│00029456
   │

 

------------ (n)第n次迭代 A〔3:0〕 ------------

....

 

[2] 重點流程 / 虛碼

 

說明示範兩個步驟應該可以知道規則是什麼,就不再畫下去。重點流程大致如下。


(0) 

 

判斷除數 B 是否為 0,是的話傳回 0 代表失敗。

 

(1) 

 

找被除數 A 之使用位數,a_len,記得在高位補一個零,所以 a_len 找到後還要再加1;

找除數 B 之使用位數,b_len;

我們還需要一個暫存器 BN,存 除數(B)*猜測值(N),其長度為 b_len+1;

再令商 C 之長度為 c_len,c_len = a_len - b_len+1

 

(2) 猜謎遊戲

 

直接看虛碼

 

Code Snippet
  1. /* 依序猜測每位數之 商,C[c_len:0] */
  2. for ( c_len = a_len - b_len ; c_len >=0 ; ++c_len) {
  3.  
  4.     // 1. 先將 BN 清成 0
  5.  
  6.     // 2. N 從 1 猜到 9, BN = B * N,
  7.     // 找出 BN >= A[c_len:c_len+r_len] 之最小 N
  8.     // (大數*=整數)
  9.  
  10.     /* 猜謎遊戲結束 ,準備填商 C[c_len] 和調整被除數 A */
  11.  
  12.  
  13.     // 3.1.
  14.     // 如果猜完 BN 還是小於 A[c_len:c_len+r_len],
  15.     // 就代表商是 9,填入 C[c_len] = 9,
  16.     // 直接進行 A[c_len:c_len+r_len]-=BN
  17.  
  18.  
  19.     // 3.2
  20.     // 如果找到的 BN 剛好等於 A[c_len:c_len+r_len],
  21.     // 不需做回覆,C[c_len] = N,不要呼叫減法,
  22.     // 直接將 C[c_len] 填入
  23.  
  24.     // 3.3
  25.     // 如果找到的 BN 大於 A[c_len:c_len+r_len],
  26.     // 需要做回覆,N=N-1,BN=B*N(大數乘整數),
  27.     // 再用 A[c_len:c_len+r_len]-=BN
  28.     // (大數-=大數)
  29. }

 

然.後.怎麼好像有點怪怪的?上面虛碼竟然有兩個怪怪的?網路上找的、這份 blog 講的大數演算法,大多都只是長這樣

 

Code Snippet
  1. void big_add( int * A , int * B , int *C); // C = A + B
  2. void big_sub( int * A , int * B , int *C); // C = A - B
  3. void big_mul( int * A , int * B , int *C); // C = A * B

 

沒辦法指定,A 從第 c_len 位置,連續 r_len 長度,和 B 做運算耶!

是的,正常來講,為了複用性, prototype 應該還要再加一個參數 : Size。如果是一般在調用的時候就長這樣

 

Code Snippet
  1. void big_add(int *A , int *B, int *C , int Size);
  2. /* do something */
  3.  
  4. const int BigSize = 200; /* VC 之 C 編譯只能用 #define 或 enum */
  5. int BigA[BigSize], BigB[BigSize], BigC[BigSize];
  6. /* do something */
  7.  
  8. big_add(A, B, C, BigSize); /* C = A + B (1) */
  9. big_add(A, B, A, BigSize); /* A = B + A, A+=B (2) */
  10.  
  11. big_add(A+a, B+b, C, op_size); /* (3) */
  12.  
  13. /*
  14. (3) C[0:op_size-1] = A[a:a+op_size-1] + B[b:b+op_size-1]
  15. */

 

在上述程式碼裡之 (1) 是常見的沒問題;(2) 的作法是想複用 C = A + B,達成 A = A + B 的作用,這手法在 C 語言裡一些場合裡面常見到,但筆者很不喜歡這樣用,一方面不是每個函式這樣塞進去都可以正確執行(甚至不少時候會出問題),另一方面是,其實直接再寫一個 A+=B ,裡面的程式碼會有更多優化的空間。

但相對的開發時程就拉長,這是對 C language 最嚴重的致命傷!今天要寫 A+=B,可能就代表著接寫下還要寫 A-=B, A*=B,大數 op 大數一份,大數 op 整數又一份,這樣下去沒完沒了,還是快跳 C++ 吧 ,不過 C++ 不熟的話,也只是從這個地嶽,跳到另一個 C++ 地嶽而已。

離題了,繼續講(3) 吧。

(3) 的作法對老手而言是常見,其代表意義從虛碼看比較清楚,

 

Code Snippet
  1. for(i = 0 ; i<op_size ; ++i)
  2.     C[i] = A[i+a] + B[i+b];



是的,沒看錯,所以如果當時在設計時,Prototype 有多一個 size,
可以省很多事。總之經過分析後,這裡決定不再改之前寫的 prototype,
而是直接再額外寫三個 function 出來。

然後筆者在 C 裡,函式本身有自我賦值(也就是賦合運算子)的,
習慣多一個 s(self)代表,C++ 就直接搞 operator +=。

 

Code Snippet
  1. // A*=numB
  2. void big_mul_int(Big * A , Big numB, int Size);
  3.  
  4. // A-=B
  5. void big_sub_parts(Big * A , Big * B , int Size);
  6.  
  7. // compare A and B
  8. int compare_parts(Big * A , Big * B , int Size);

 

當然,有興趣也可以把之前寫過的 fucntion prototype 全改過再調用。基於系列文之設計架構,以下是一份完整的大數除法範例。

 

Code Snippet
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. #define BIG_SIZE 100
  6. #define BIG_CAP  10     /* 10,100,1000,100000   */
  7. #define BIG_LEN  1      /* 10^BIG_LEN = BIG_CAP */
  8. #define BIG_CAP2 9      /* BIG_CAP - 1          */
  9.  
  10. #define BSIZE(n) ( sizeof(int) * (n))
  11.  
  12. typedef struct tagBig{
  13.     int arr[BIG_SIZE]; // 大數陣列
  14.     int dig;           // 使用位數
  15. }Big;
  16.  
  17. // 輸入
  18. void big_from_string(Big * big , const char * str)
  19. {
  20.     int i, j, len, pwr;
  21.     int * arr = big->arr;
  22.     // 去前導0
  23.     while(*str=='0' && *str!='\0') ++str;
  24.     // 轉入大數
  25.     len = strlen(str);
  26.     arr[0] = 0;
  27.     for(j=0, i=len-1; i>=0; ++j, arr[j]=0)
  28.         for(pwr=1; pwr!=BIG_CAP && i>=0; pwr*=10, --i)
  29.             arr[j]+=(str[i]-'0')*pwr;
  30.     // 計算位數
  31.     big->dig = j;
  32. }
  33.  
  34. // 輸出
  35. void big_print(Big * big)
  36. {
  37.     int i = big->dig;
  38.  
  39.     if(!i) printf("0");
  40.     else {
  41.         int *arr = big->arr;
  42.         printf("%d", arr[--i]); // 輸出第一位數字
  43.         for(--i; i>=0; --i) // 輸出其他數字
  44.             printf("%0*d", BIG_LEN, arr[i]);
  45.     }
  46. }
  47.  
  48. // 除法用,大數比較
  49. int big_compare_part(int * A , int * B , int size)
  50. {
  51.     int i;
  52.     for(i=size-1; i && A[i]==B[i]; --i);
  53.     return A[i] - B[i];
  54. }
  55.  
  56. // 除法用,大數*整數,不需考慮一次進位之 ov 問題
  57. void big_mul_int_part(int * A , int numB, int * C, int size)
  58. {
  59.     int i;
  60.     for(i = 0 ; i<size ; ++i)
  61.         C[i] = numB * A[i];
  62.     for(i = 0 ; i<size-1; ++i) {
  63.         C[i+1] += C[i] / BIG_CAP;
  64.         C[i]%=BIG_CAP;
  65.     }
  66. }
  67.  
  68. // 除法用,大數減法,A-=B
  69. void big_subs(int * A , int * B , int size)
  70. {
  71.     int i, borrow=0;
  72.     for(i=0; i<size; ++i){
  73.         A[i]-=(B[i]+borrow);
  74.         if(A[i] < 0) borrow=1, A[i]+=BIG_CAP;
  75.         else borrow = 0;
  76.     }
  77. }
  78.  
  79. //
  80. // 大數除大數
  81. // BigA : 被除數,執行完後變餘數
  82. // BigB : 除數
  83. // BigC : 餘數
  84. // return : 成功(1), 失敗(0)
  85. int big_div(Big * BigA , Big * BigB , Big * BigC)
  86. {
  87.     int i, N, cmp;
  88.     int * NB; // 存放 N * B
  89.     int * A = BigA->arr, * B = BigB->arr;
  90.     int * C = BigC->arr;
  91.  
  92.     // 算長度
  93.     int a_len = BigA->dig ; // 被除數位數, 高位補0, 故要+1
  94.     int b_len = BigB->dig ; // 除數位數
  95.     int c_len = a_len - b_len + 1; // 商數位數
  96.     int r_len = b_len + 1;  // 暫存位數
  97.  
  98.     if(b_len==0) {  // 除零錯誤
  99.         BigC->dig=0;
  100.         return 0;
  101.     } else if(b_len > a_len) { // B > A, 0
  102.         BigC->dig = 0;
  103.         return 1;
  104.     }
  105.  
  106.     NB = (int*)malloc(sizeof(int) * r_len);
  107.     BigC->dig = c_len, A[a_len++]=0; // A 前面補0
  108.  
  109.     /* 尋找 C[c_len:0] 之猜商遊戲 */
  110.     for( ; c_len >=0 ; --c_len){
  111.         for(N=1; N<BIG_CAP ; ++N) {
  112.             big_mul_int_part(B, N, NB, r_len);
  113.             cmp = big_compare_part(A+c_len, NB, r_len);
  114.             if(cmp<=0) break; // A >= NB 時結束
  115.         }
  116.         /* 依比較結果 cmp 調整 */
  117.  
  118.         if(cmp==0){ // 相等, 將商填入, A[...] 填入
  119.             memset( (void*)(A+c_len), 0, BSIZE(r_len));
  120.             C[c_len] = N;
  121.         } else if(cmp < 0) { // 猜太大, 變小, 回覆
  122.             C[c_len ] = --N;
  123.             big_mul_int_part(B, N, NB, r_len); // NB = N * B
  124.             big_subs(A + c_len, NB, r_len); // A -=NB
  125.         } else { // 唯一可能剛好情況, N=BIG_CAP, 不需再做回覆
  126.             big_subs(A+c_len, NB, r_len); // A-= NB
  127.             C[c_len] = BIG_CAP2;
  128.         }
  129.     }
  130.     free( (void*)NB);
  131.     // 更新 c_len
  132.     for(i=BigC->dig; i>0 && C[i]==0; --i);
  133.     if(i==0) BigC->dig = ( (C[i]==0) ? 0 : 1 );
  134.     else BigC->dig = i+1;
  135.  
  136.     // 更新 a_len, a_len < b_len
  137.     for(i=b_len; i>0 && A[i]==0 ; --i);
  138.     if(i==0) BigA->dig = ( (A[0]==0) ? 0 : 1);
  139.     else BigA->dig = i+1;
  140.  
  141.     return 1; 
  142. }
  143.  
  144. /////////////////////////////////////////
  145. int main()
  146. {
  147.     char * s1[] = {"7123456", "0", "7428571",
  148.         "999999999999999999999999999999999999999999999999999999999999"};
  149.     char * s2[] = {"123", "120", "7123745",
  150.         "1"};
  151.     Big A, B, C, R;
  152.     int i;
  153.     ///
  154.  
  155.     for(i=0; i<sizeof(s1) / sizeof(s1[0]) ; ++i){
  156.         big_from_string(&A, s1[i]);
  157.         big_from_string(&B, s2[i]);
  158.  
  159.         R = A ; // 除法會變更除數成餘數,故將除數先備份
  160.         big_print(&A), printf(" / "), big_print(&B),  printf(" = ");
  161.         big_div(&R, &B, &C);
  162.         big_print(&C), printf(" ... ");
  163.         big_print(&R), puts("\n");
  164.     }
  165.     getchar();
  166.     return 0;
  167. }

 

 

[3] 猜商策略

 

好了,上面的 code 其實效率很糟,今天是 10 進位所以最多算 10 次,若是 萬進位、65536 進位,最多不就要算 65536 次了嗎?是的,有幾種改善方式。一種是整個把大數 * 整數拿掉,直接以加、減法方式慢慢做。

 

去掉一些拉哩拉喳的東西,大致如下。

 

Code Snippet
  1. //
  2. // 除法用, 大數自身加法, A+=B
  3. void big_adds(int * A , int * B , int size)
  4. {
  5.     int i,c=0;
  6.     for(i=0; i<size; ++i){
  7.         A[i]+=B[i]+c;
  8.         c = A[i]/BIG_CAP;
  9.         A[i]%=BIG_CAP;
  10.     }
  11. }
  12. //
  13. // 大數除大數
  14. // BigA : 被除數,執行完後變餘數
  15. // BigB : 除數
  16. // BigC : 餘數
  17. // return : 成功(1), 失敗(0)
  18. int big_div2(Big * BigA , Big * BigB , Big * BigC)
  19. {
  20.     // 前面全略...
  21.      
  22.     NB = (int*)malloc(sizeof(int) * r_len);
  23.     BigC->dig = c_len, A[a_len++]=0; // A 前面補0
  24.  
  25.     /* 尋找 C[c_len:0] 之猜商遊戲 */
  26.     for( ; c_len >=0 ; --c_len){
  27.         memset( (void*)NB, 0, sizeof(int)*r_len);
  28.         for(N=1; N<BIG_CAP ; ++N) {
  29.             big_adds(NB, B, r_len); // NB+=B, 取代乘法
  30.             cmp = big_compare_part(A+c_len, NB, r_len);
  31.             if(cmp<=0) break; // A >= NB 時結束
  32.         }
  33.         /* 依比較結果 cmp 調整 */
  34.  
  35.         if(cmp==0){ // 相等, 將商填入, A[...] 填入
  36.             memset( (void*)(A+c_len), 0, BSIZE(r_len));
  37.             C[c_len] = N;
  38.         } else if(cmp < 0) { // 猜太大, 變小, 回覆
  39.             C[c_len ] = --N;
  40.             big_subs(NB, B, r_len); // NB-=B, 取代乘法
  41.             big_subs(A + c_len, NB, r_len); // A -=NB
  42.         } else { // 唯一可能剛好情況, N=BIG_CAP, 不需再做回覆
  43.             big_subs(A+c_len, NB, r_len); // A-= NB
  44.             C[c_len] = BIG_CAP2;
  45.         }
  46.     }
  47.     free( (void*)NB);
  48.     // 後面一堆也略 ... 
  49.     return 1;
  50. }

 

[4] 二分搜尋法

 

 

另一種猜商策略是用二分搜尋法,若是 65536 進位時,猜一個商最多需要 16 次。為留參,這份  code 有些長,盡可能縮。只有部份變動,有興趣從 for 開始看便可。

 

Code Snippet
  1. // 大數除大數
  2. // BigA : 被除數,執行完後變餘數
  3. // BigB : 除數
  4. // BigC : 餘數
  5. // return : 成功(1), 失敗(0)
  6. int big_div3(Big * BigA , Big * BigB , Big * BigC)
  7. {
  8.     int i, N, cmp, low, up;
  9.     int * NB; // 存放 N * B
  10.     int * A = BigA->arr, * B = BigB->arr, * C = BigC->arr;
  11.     
  12.     // 算長度
  13.     int a_len = BigA->dig, b_len=BigB->dig;
  14.     int c_len = a_len - b_len + 1 , r_len = b_len+1;
  15.  
  16.     if(!b_len) {    BigC->dig=0;return 0;}
  17.     else if(b_len > a_len) { BigC->dig = 0;return 1;}
  18.  
  19.     if(! (NB = (int*)malloc(BSIZE(r_len)))) return 0; // fail
  20.     BigC->dig = c_len, A[a_len++] = 0;
  21.  
  22.     /* 尋找 C[c_len:0] 之猜商遊戲 */
  23.     for( --c_len; c_len >=0 ; --c_len){
  24.         low = 0 , up = BIG_CAP-1;
  25.         while(low<=up){
  26.             big_mul_int_part(B , N = (low + up) >>1 , NB, r_len);
  27.             if(!(cmp = big_compare_part(A+c_len, NB, r_len))) break;
  28.             else if(cmp>0)  low = N+1; // 猜太小
  29.             else up =  N-1;
  30.         }
  31.         /* 依比較結果 cmp 調整 */
  32.         if(cmp==0){ // 相等, 將商填入, A[...] 填入
  33.             memset( (void*)(A+c_len), 0, BSIZE(r_len));
  34.             C[c_len] = N;
  35.         } else if(cmp < 0) { // 猜太大, 變小, 回覆
  36.             C[c_len ] = --N;
  37.             big_subs(NB, B, r_len); // NB-=B
  38.             big_subs(A + c_len, NB, r_len); // A -=NB
  39.         } else {
  40.             big_subs(A+c_len, NB, r_len); // A-= NB
  41.             C[c_len] = N;
  42.         }
  43.     }
  44.     free( (void*)NB);
  45.     // 更新 c_len
  46.     for(i=BigC->dig-1; i>0 && C[i]==0; --i);
  47.     if(i==0) BigC->dig = ( (C[i]==0) ? 0 : 1 );
  48.     else BigC->dig = i+1;
  49.  
  50.     // 更新 a_len, a_len < b_len
  51.     for(i=b_len; i>0 && A[i]==0 ; --i);
  52.     if(i==0) BigA->dig = ( (A[0]==0) ? 0 : 1);
  53.     else BigA->dig = i+1;
  54.  
  55.     return 1;
  56. }

 

 

 

[5] 有更好的猜商策略嗎?

 

 

上面的二分法和比較,其實寫在一起,效率會較高,乘的時候先乘高位數部份,可以同時做比較,細節留下不贅述!

 

另一種猜商方式,假設是 56789012345 除以  123456,capacity 為 10 進位,商可以先「大致猜一下」,示意如下。

 

              ????
       ┌────────────────
 23456│056789012345
       │

直接先把被除數的前兩位合併成一個數字,變 05,

除數取出最高位,變1,而5/1=5,發現用 5 太大,但往下降 1 變 4 後就剛好。

 

              ??
       ┌────────────────
 23456│056789012345
       │0493824
       -------------
        0074066

 

              ??
       ┌────────────────
 23456│0740662345
       │

 

一樣繼續拿 07 除以 1,得到 7,依此類推,但這次實際拿到的商是 5 了。不過記得的是,最大只能猜到 BIG_CAP-1 便是。拿到初始的商後,接下來的策略變化就個人發輝吧,像是把它拿來當作是二分法的 upper 初值,或是直接拿下來做遞減等等 ( 猜 7 太大 -> 變 6 -> 變 5 ),這些都可拿來當作策略。

 

另一種猜商策略,忘了在哪看到這手法,出處不詳。用到的是牛頓法,求 A / B 時,相當於使用 A * (1/B), 1/B 怎來的?

 

由於牛頓法一開始只是需要初值,所以即使用 double 勉強接進來也行,算完 double 轉一次大數,稱 x,再來就是迭代公式了

xn+1 = (2 - xn * B) * xn。

 

舉個例子, 求 7123456(A) / 123(B),先算 1/123

 

(1) 1 / 123,抓個大概,算 x1 = 0.01 就好。

(2)  x2 = (2-x1*B) * x1 = (2 - 0.01 * 123) * 0.01 = 0.0077

(3)  x3 = (2-x2*B) * x2 = (2-0.0077 * 123) * 0.0077 = 8.10733 e-3

(4)  x4 = 8.130017633 e-3

(5) x5 = 8.1300813e-3

 

由於被除數是 7123456 (A , 7位數),到這裡誤差已小於 1e-7,就可以停下來了,最後再把這兩個答案相乘得 Y,Y 取整數部份,就是商 C;餘數 R = A - B * C。

 

有幾個 note 可以再想想。

 

(1) 如果乘法沒有降到 nlogn ,沒意義。

說到底除法效能還是相依於乘法(吧?),依上述方式,最耗時的應是在最後 兩個答案相乘(A, 1/B) 的乘法部份,因前面一開始取的精度可以不用那麼高 (偷懶)。

(2) 萬一,B 本身就超過 DBL_MAX 的時候,該怎辦??

oh 這問題好解決,如果是 100 進位的話,假設 B = 71 23 45 60 ,第一個非零是在 B[4-1],先用 1/71 = 0.01428,再放到小數後第 4 個百位就行,也就是 0.00 00 00 01 43 當初值。然後小數點的移位的話.. 嗯,看來還有多一個變數做紀錄。

(3) 萬一,實作的是 65536 進位的話,那不是等於要先將大數轉成 10 進位,求完之後再轉成 65536 進位?速度整個慢了?

這問題推起來卡卡,就沒真的實作不敢給結論了。初步想法是,其實 65536 進位也可以用 shift 方式完成,用上述的原理也沒必要再做轉換;再糟的話,就 KK IEEE754吧 Orz。

 

 

 

[6] 效率 Note

 

這篇寫很多了,下次有空再把知道的一些技巧做 note 。目前就我所知的算法效率

 

(1) 大數 + - 大數 : O(n) , 這怎麼做都是 O(n)

(2) 大數 * 大數 : O( nlogn) , FFT

(3) 大數 / % 大數 : O(nlogn) , 牛頓法 + FFT 乘法

(4) 字串轉 16 / 65536 進位大數 : O(nlogn) , 用連除法效率是 O(n^2)

(5) 大數階乘 : O(???)

 

大數階乘其實筆者也不確定是 O(??) ,比較快的一種做法是先對各數做質因式分解,再做相乘。

 

怪不得不少論壇都說這是一個「永遠的挑戰」,就算 C 寫好,C++ 考慮 copy constructor 所帶來效能問題應也不會太好搞,除了 open soruce ( ex, gmp) 外,目前似乎還沒人在講這部份的東西。

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


留言列表 (1)

發表留言
  • @@
  • "完整的大數除法範例"

    93 int a_len = BigA->dig ; // 被除數位數, 高位補0, 故要+1

    95 int c_len = a_len - b_len + 1; // 商數位數

    107 BigC->dig = c_len, A[a_len++]=0; // A 前面補0

    似乎應該為

    93 int a_len = BigA->dig+1 ; // 被除數位數, 高位補0, 故要+1

    95 int c_len = a_len - b_len ; // 商數位數

    107 BigC->dig = c_len, A[a_len]=0; // A 前面補0

    也許是否是作者不小心改錯?
  • 沒錯啊,補完零後,a_len 要加一,要分二段寫也行啦
    A[a_len] = 0 ; a_len++;

    edisonx 於 2016/11/19 23:16 回覆

您尚未登入,將以訪客身份留言。亦可以上方服務帳號登入留言

請輸入暱稱 ( 最多顯示 6 個中文字元 )

請輸入標題 ( 最多顯示 9 個中文字元 )

請輸入內容 ( 最多 140 個中文字元 )

請輸入左方認證碼:

看不懂,換張圖

請輸入驗證碼