# 2021q1 Homework3 (fibdrv) contributed by < `tigger12613` > ## 大數運算 ### 資料結構 用陣列去儲存數字的分割，因為要印出十進位的數字，所以對陣列的每一格最大數字為 \$10^{19} - 1\$，超出最大數字就進位，這樣才可以印出十進位的數字。 ```cpp // 1e19 - 1; the max power of 10 - 1 of 64 bit unsigned interger #define MaxDecimal 999999999999999999 // the long that bigNum can carry in decimal #define MaxbigNumlen 90 // bigNumArrSize = 5 #define bigNumArrSize MaxbigNumlen / 18 typedef struct bigNum { unsigned long long data[bigNumArrSize]; } bigNum; ``` ### 給定數字 將字串轉成數字。 ```cpp // set the number by string, if success return true, if too large return false. bool set_num(bigNum *num, char *s) { size_t slen = strlen(s); if (slen > MaxbigNumlen) { return false; } unsigned long long tmp = 0; int i = 0; int offset = 0; while (slen) { char char_value = (s[slen - 1] - '0'); if (char_value < 0 || char_value > 9) { return false; } tmp += char_value * (bigNum_pow_10(i)); i++; slen--; if (i == 18) { i = 0; num->data[bigNumArrSize - 1 - offset] = tmp; tmp = 0; offset++; } } num->data[bigNumArrSize - 1 - offset] = tmp; return true; } ``` ### 加法 相加兩個 `bigNum` ，超出最大值回傳 `false` 。 ```cpp // des = a + b // return true if success, return false if overflow // it will still add to des when overflow bool add_bignum(bigNum *des, bigNum *a, bigNum *b) { unsigned long long carry = 0; for (int i = bigNumArrSize - 1; i >= 0; i--) { unsigned long long int tmp = a->data[i] + b->data[i] + carry; if (tmp <= MaxDecimal) { des->data[i] = tmp; carry = 0; } else { des->data[i] = tmp - MaxDecimal - 1; carry = 1; } if (i == 0 && carry == 1) { return false; } } return true; } ``` ### 印出數字 印出十進位的數字。 ```cpp void printDecimal(bigNum *num) { bool is_printed = false; for (int i = 0; i < bigNumArrSize; i++) { if (is_printed) { printf("%018llu", num->data[i]); } else { if (num->data[i]) { printf("%llu", num->data[i]); is_printed = true; } } } if (is_printed == false) { printf("0"); } } ``` ### 測試大數加法 使用 `bigNum` 計算 `fibonacci serious` 在 `f(433)` 產生溢出。 ``` ... f(425) = 29529908689737440719341867053506936071765074245955118399664162441967250186097733500962925 f(426) = 47780395944676052274416277690031248729785923474969864327823043828116713025492002771430968 f(427) = 77310304634413492993758144743538184801550997720924982727487206270083963211589736272393893 f(428) = 125090700579089545268174422433569433531336921195894847055310250098200676237081739043824861 f(429) = 202401005213503038261932567177107618332887918916819829782797456368284639448671475316218754 f(430) = 327491705792592583530106989610677051864224840112714676838107706466485315685753214360043615 f(431) = 529892711006095621792039556787784670197112759029534506620905162834769955134424689676262369 f(432) = 857384416798688205322146546398461722061337599142249183459012869301255270820177904036305984 overflow: f(433) = 387277127804783827114186103186246392258450358171783690079918032136025225954602593712568353 ``` :::warning TODO: 學習 [第 6 週測驗題](https://hackmd.io/@sysprog/linux2021-quiz6) 的大數運算實作 :notes: jserv ::: ## 運用 clz/ctz 指令搭配 Fast Doubling 手法計算費氏數列 首先需要增加幾個計算 ### 大數減法 ```cpp= //des = a - b bool bigNum_minus(bigNum *des, bigNum *a, bigNum *b){ init_bigNum(des); int carry = 0; for (int i = bigNumArrSize - 1 ; i >=0; i--){ if(a->data[i] >= b->data[i] + carry){ des->data[i] = a->data[i] - b->data[i] - carry; carry = 0; }else{ des->data[i] = a->data[i] + (MaxDecimal - b->data[i] + 1 - carry); carry = 1; } } return true; } // a--, if <0 return false, else return true bool bigNum_minus_1(bigNum *a) { for (int i = bigNumArrSize - 1; i >= 0; i--) { if (a->data[i] > 0) { a->data[i]--; return true; } else { a->data[i] = MaxDecimal; } } return false; } ``` ### 比較兩個數字 ```cpp= // return -1 if a<b, 0 if a=b, 1 if a>b. int bigNum_cmp(bigNum *a, bigNum *b) { for (int i = bigNumArrSize - 1; i >= 0; i--) { if (a->data[i] < b->data[i]) { return -1; } else if (a->data[i] > b->data[i]) { return 1; } } return 0; } ``` ### 複製一個變數的數值到另一個變數上 ```cpp= // copy value from src to des void bigNum_copy(bigNum *des, bigNum *src) { for (int i = bigNumArrSize - 1; i >= 0; i--) { des->data[i] = src->data[i]; } } ``` ### 乘法 因為 `bigNum` 的陣列已經用了 64bit ，所以無法用一般乘法去實作大數乘法，只能用加法實作，這將導致運行速度緩慢。 ```cpp= // des = a * b bool bigNum_mul(bigNum *des, bigNum *a, bigNum *b) { bigNum d; bigNum m; init_bigNum(des); bigNum_set_num(des, "0"); if (bigNum_cmp(a, b)) { bigNum_copy(&d, b); bigNum_copy(&m, a); } else { bigNum_copy(&d, a); bigNum_copy(&m, b); } bigNum zero; bigNum_set_num(&zero, "0"); while (bigNum_cmp(&d, &zero)) { if (!bigNum_add(des, des, &m)) { return false; } bigNum_minus_1(&d); } return true; } ``` ### Fast Doubling 對照虛擬碼實作 ```cpp= Fast_Fib(n) a = 0; b = 1; // m = 0 for i = (number of binary digit in n) to 1 t1 = a*(2*b - a); t2 = b^2 + a^2; a = t1; b = t2; // m *= 2 if (current binary digit == 1) t1 = a + b; // m++ a = b; b = t1; return a; ``` 實作 ```cpp= bigNum fib_sequence(int k) { bigNum a,b,t1,t2,two,tmp,tmp2,tmp3; init_bigNum(&tmp); init_bigNum(&tmp2); init_bigNum(&tmp3); bigNum_set_num(&two,"2"); bigNum_set_num(&a,"0"); bigNum_set_num(&b,"1"); for (int i = 32 - __builtin_clz(k)-1; i >= 0 ; i--){ //t1 = a*(2*b - a) bigNum_mul(&tmp,&two,&b); bigNum_minus(&tmp2,&tmp,&a); bigNum_mul(&t1,&a,&tmp2); //t2 = b^2 + a^2 bigNum_mul(&tmp,&b,&b); bigNum_mul(&tmp2,&a,&a); bigNum_add(&t2,&tmp,&tmp2); //a=t1;b=t2 bigNum_copy(&a,&t1); bigNum_copy(&b,&t2); if((k>>i)&1){ bigNum_add(&t1,&a,&b); bigNum_copy(&a,&b); bigNum_copy(&b,&t1); } } return a; } ``` ### 測試輸出 與預期相符，但是效率非常糟糕。 ```shell= ... F(90): 2880067194370816120 F(91): 4660046610375530309 F(92): 7540113804746346429 F(93): 12200160415121876738 F(94): 19740274219868223167 F(95): 31940434634990099905 F(96): 51680708854858323072 F(97): 83621143489848422977 ``` ### 效率比較 待完成