# 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
```
### 效率比較
待完成
Sign in with Wallet
Connect another wallet