# 2020q1 Homework2 (fibdrv)
contributed by < `fwfly` >
## 修改錯誤數值
可以看到在 92 之後的數字都是一樣 7540113804746346429.
因為 ssize_t 的關係，只能讀到 92
```
Reading from /dev/fibonacci at offset 92, returned the sequence 7540113804746346429.
Reading from /dev/fibonacci at offset 93, returned the sequence 7540113804746346429.
...
````
實作 bigN
upper 是大於 64bit 的數字
lower 則是小於 64bit 的數字
```cpp
struct BigN {
unsigned long long lower, upper;
};
static inline void addBigN(struct BigN *out, struct BigN x, struct BigN y)
{
out->upper = x.upper + y.upper;
unsigned long long lower = ~x.lower;
if (y.lower > lower) {
out->upper++;
}
out->lower = x.lower + y.lower;
}
```
中間的 :
```c
~x.lower
```
可以理解成距離 unsigned long long 最大數還有多少
```c
y.lower > Maxnum - x.lower
```
所以如果 y.lower 大於這個數字，就表示會 overflow
需要進行進位．
其中跟原始文件不同的是這個部分, 如果在 if 做 bitwise 操作
程式會先做 if 然後才做 bitwise 的操作，這樣會造成每次運算都需要進位
所以做 if 之前先把直取出來再來做運算．
細節為何會這樣跑，則還要再研究
```cpp
unsigned long long lower = ~x.lower;
```
## BigN_to_int function
因為 BigN 的進位方式跟一般 10 進位不太一樣，所以直接印出來
其實看不太懂，也很難對照答案．
以下是把 BigN 轉成可讀的數字，當然這樣會有另外一個問題是
BigN 沒有 overflow, 但是轉成數字會造成 overflow
### 概念
假設我們用 unsigned short, 最大數會是 65535.
所以當 upper = 5, 最後結果會是 65535*5 + lower.
但是因為已經 overflow 了，所以根本沒辦法做這樣的運算，
那會變成沒有辦法印出 10進位 的數字．
### 解法
方法就是把 lower 中的最大位數取出來運算放到 upper, 然後剩下的餘數
去做進位運算．因為已經取出最大位數，所以剩下的數字怎麼運算都不會 overflow.
比方說 : (為了方便解說，採用 short 而不是 long long)
BigN upper = 1, lower = 55858
那 upper 可以理解成有 1 個 65535
此時就會針對 65535 取出 6 然後拿到最大位數再減掉 60000 拿到餘數
就會變成兩個數字 6 跟 5535.
同理 55858 也可以分解成 5 跟 5858
再來把餘數相加 5858 + 5535 可以得到 11393
再把 11393 分解成 carry (1) 跟 1393
最後再把最大位數跟 carry 加起來放到 upper
就會是 6 + 5 + 1(carry) = 12
所以印出來就會是 12 1393
如果 upper 大於 1 則用迴圈重複跑以上步驟．就可以作轉換．
```c
void BigN_to_int(struct BigN *res, struct BigN x)
{
unsigned long long max10 = 10000000000000000000U;
unsigned long long idx = x.upper;
unsigned long long max_first = ULONG_MAX / max10;
unsigned long long max_mod = ULONG_MAX - max_first * max10;
res->lower = x.lower;
unsigned long long x_first = x.lower / max10;
unsigned long long x_mod = x.lower - x_first * max10;
while (idx) {
// Add mod
x_mod = x_mod + max_mod;
int carry = 0;
// count if it needs carry over.
if (x_mod > max10) {
carry = 1;
x_mod = x_mod - max10;
}
res->lower = x_mod;
// Add x_first , max_first, carry to find upper_dec
x_first = x_first + max_first + carry;
res->upper = x_first;
idx--;
}
}
```
### BigN_to_Int 的效能問題
在使用 BigN_to_Int 後，如果把轉換過的值 assign 給任何一個變數．
程式就會變得異常的慢，目前測試過後的結果，超過 fib 133 速度會到以秒計算甚至更久．但是如果拿掉這段，則可以算到 fib 250 依然不是問題．
在部分拿掉程式碼後發現這個地方可能是造成效能問題的部分
``` c
// count if it needs carry over.
// BUG :
// When this been executed, the process will become slow
// after assign result to other value.
if (x_mod > max10) {
carry = 1;
x_mod = x_mod - max10;
}
```
比如:
``` c
BigN a;
BigN_to_int( &res, *out );
a.upper = res.upper; // 這裡會變得異常的慢
```
## ktime 跟測試 (fib 150)
:::danger
請避免不精準的說法，例如「看不出」，學過機率統計的你，請用科學術語和手法來探討。
:notes: jserv
:::
基本上就是跟筆記上面的程式碼一樣，用 ktime 去包 fib 運算．
但是因為 100 其實看不出來時間差距, 就算是運算到 100 也只是到 2000+ns, 所以把數字條大到 150．
### fib && fast fib 數據
修改後的 fast fib 時間反而比原本的時間還要多出 n 倍 (在第 fib 100 時可以相差到 1億倍)
在測試過後發現是大數乘法出了問題．最原始的乘法概念是
乘法為加法加了 n 次得到的結果．
```c
static inline void multiBigN(struct BigN *out, struct BigN x, struct BigN y)
{
out->upper = 0;
out->lower = 0;
if (!y.upper && y.lower >= 1) {
out->upper = x.upper;
out->lower = x.lower;
}
while ((y.upper != 0) || (y.lower > 1)) {
while (y.lower > 1) {
addBigN(out, *out, x);
y.lower--;
}
if (y.upper) {
y.upper--;
y.lower = ULONG_MAX;
}
}
}
```
因為有兩個 while 包起來，所以會跑到 $O(N^2)$ , 因此當數字極大時，就會變得異常的慢，根據實測 fib 74 之後就可以以秒為單位．
```
74 120337537
...
...
99 48005296761
100 78421793687
```
### 乘法改進
乘法則是參考 [AndybnA](https://hackmd.io/@AndybnA/fibdrv) 同學的程式碼，發現裡面有使用 uint128_t ，再從文章中的提示找到 [recipes/basic/int128.h](https://github.com/chenshuo/recipes/blob/master/basic/int128.h) 乘法實作．產生以下程式碼
```c
static inline void multiBigN64to128(struct BigN *out, unsigned long long x, unsigned long long y)
{
uint32_t a = x & 0xFFFFFFFF;
uint32_t c = x >> 32;
uint32_t b = y & 0xFFFFFFFF;
uint32_t d = y >> 32;
uint64_t ab = (uint64_t)a * b;
uint64_t bc = (uint64_t)b * c;
uint64_t ad = (uint64_t)a * d;
uint64_t cd = (uint64_t)c * d;
uint64_t low = ab + (bc << 32);
uint64_t high = cd + (bc >> 32) + (ad >> 32) + (low < ab);
low += (ad << 32);
high += (low < (ad << 32));
out->lower = low;
out->upper = high;
}
static inline void multiBigN(struct BigN *out, struct BigN x, struct BigN y)
{
out->upper = 0;
out->lower = 0;
unsigned long long h = x.lower * y.upper + x.upper * y.lower;
multiBigN64to128(out, x.lower, y.lower);
out->upper += h;
}
```
乘法演算法是跟據 Hackers-Delight 這本書裡面提到的 Knuth's Algorithm 所實做出來的結果
目前已知的部分是這段程式碼先將 128bit 的數字分拆成 64bit * 64bit, 在 64bit 的部分可以再拆成 32bit * 32bit...以此類推.
主要原因是為了防止 overflow.
能夠這樣做的原因是因為 m bit 乘上 n bit, 最大數字會是 m+nbits
也就是 32bit * 32bit 最大會是 64bit.
因此在做 64bit 乘法時可以用 128bit size 的數字來接．這樣就不會造成 overflow
因為這中間沒有任何迴圈運算，所以速度上可以接近常數，就跟一般的乘法一樣
細節的運算部分還要再理解
### 乘法錯誤運算
在做 khttpd 的時候發現當 fib > 94 (開始處理 overflow) 就會出現錯誤結果，而且結果都只相差 1 或 2 或者其他小位數．
```
94: 19740274219868223166 Ans: 19740274219868223167 -1
95: 31940434634990099904 Ans: 31940434634990099905 -1
96: 51680708854858323070 Ans: 51680708854858323072 -2
```
原因是乘法上面出了問題，如果去比對[大數運算網站](https://defuse.ca/big-number-calculator.htm)，就會看到答案上有問題，而且單純計算也會發現 3*9 尾數絕對不會是 6
```
19740274219868223166 = 6643838879 * 2971215073
23112315624967704575 = 4807526976 * 4807526976
```
如果用 BigN 的方式表示稱法運算結果就會得到
```
1 9740274219868223166 = 6643838879 * 2971215073 差 1
1 4665571551258152960 = 4807526976 * 4807526976 差 1
....
...
```
可以看到一個規律是不足得數字剛好會是 bigN upper 的部分．目前還不確定真實原因，也不確定原作者的程式碼有沒有相同的問題(可以做實際驗證)．
但是由於以上規律，所以在乘法最後加上這一段，就可以得到正確答案
```
....
out->upper += h;
out->lower += out->upper; // 新加程式碼
```
To do :
* 驗證原作者程式碼
* 了解演算法
### 結果 (fib 100)
因為 fast fib 的結果放上去其他的結果會像常數，所以直接提除．
從這邊可以看到一班的 fib 是線性上升，透過 fast fib knuth 速度可以降到幾乎是常數．不過因為這只運算到 fib 100，所以可以拉高到 200 以上來看看 fast fib kunth 的 結果
#### 瓶頸
* BigN_to_Int 無法使用超過 fib 135 (效能問題)
* 128 bit 大約只能計算到 fib 180 = 1.854e+38 , 再上去需要用不同的資料型態
#### 發現
再回頭 review 其他人的作品時，發現一個 bignum 的 repository.
https://github.com/sysprog21/bignum
經過實測，這個 fib 可以達到 700 以上並且輸出正確的值．
可能可以參考實作，但是這個架構跟目前程式架構有很大的差別．
## Reference
int128 乘法運算
https://github.com/chenshuo/recipes/blob/master/basic/int128.h
128 Multiplication 實作
https://www.codeproject.com/Tips/618570/UInt-Multiplication-Squaring
參考自書籍 Hackers Delight ch8
中文解釋 Knuth's Algorithm
https://pansci.asia/archives/162365
Integer multiplication in time O(n log n)
https://hal.archives-ouvertes.fr/hal-02070778/document
Multiplication algorithm
https://en.wikipedia.org/wiki/Multiplication_algorithm#Fast_multiplication_algorithms_for_large_inputs
## To do
* 調整 CPU 後的效能
* copy to user : 可以直接輸出 bigN ?
* 測量 user mode 的效能
* 測量 只做 kernel mode 的效能
* clz/ctz 改寫後的效能
* 採用不同的 bigN 演算法 [Bignum Arithmetic](http://dl.fefe.de/bignum.pdf)
* BigN to Int 表示法
Sign in with Wallet
Connect another wallet