# 2020q1 Homework2 (fibdrv)
contributed by < [Hsuhaoxiang](https://github.com/Hsuhaoxiang/fibdrv) >

:::warning
2020q1 表示 2020 年的第 1 季，即春季班課程的意思
:notes: jserv
:::

## 自我檢查清單
<!-- 花了非常久的時間才了解作業該如何開始，我想，仔細看完每一個連結後，才能夠迅速進入狀況
真心佩服才花幾天就能做出成果的修課同學，另外要不參考其他人的想法做出東西真的好難，到底有多少東西是我所學到的，雖然只是旁聽但還是覺得時間真短，希望能繼續堅持下去2020/03/19。
-->

- [ ] 研讀上述 ==Linux 效能分析的提示== 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗;
- [x] 研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 [clz / ctz](https://en.wikipedia.org/wiki/Find_first_set) 一類的指令對 Fibonacci 數運算的幫助。請列出關鍵程式碼並解說
- [ ] 複習 C 語言 [數值系統](https://hackmd.io/@sysprog/c-numerics) 和 [bitwise operation](https://hackmd.io/@sysprog/c-bitwise)，思考 Fibonacci 數快速計算演算法的實作中如何減少乘法運算的成本;
- [ ] `lsmod` 的輸出結果有一欄名為 `Used by`，這是 "each module's use count and a list of referring modules"，但如何實作出來呢？模組間的相依性和實際使用次數 ([reference counting](https://en.wikipedia.org/wiki/Reference_counting)) 在 Linux 核心如何追蹤呢？
- [ ] 注意到 `fibdrv.c` 存在著 `DEFINE_MUTEX`, `mutex_trylock`, `mutex_init`, `mutex_unlock`, `mutex_destroy` 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題

---

## 研讀上述費氏數列相關材料
### 費氏數列有公式解
$$
a_{n+1} = a_n + b_n \\ b_{n+1} = a_n
$$
$$
\begin{pmatrix}
a_{n} \\ b_{n}
\end{pmatrix}
=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}
\begin{pmatrix}
a_0 \\ b_0
\end{pmatrix}
$$
方法是將前面的 `Q-metrix` 進行對角化，得到 `eigenvalue` $\lambda_{1}=(\frac{1+\sqrt{5}}{2})$ ,$\lambda_{2}=(\frac{1-\sqrt{5}}{2})$
$$
\begin{pmatrix}
a_{n} \\ b_{n}
\end{pmatrix}
=
(\frac{1}{\lambda_{1}-\lambda_{2}})
\begin{pmatrix}
\lambda_{1} & \lambda_{2} \\
1 & 1
\end{pmatrix}
\begin{pmatrix}
\lambda_{1}^n & 0 \\
0 & \lambda_{2}^n
\end{pmatrix}
\begin{pmatrix}
1 & -\lambda_{2} \\
-1 & \lambda_{1}
\end{pmatrix}
\begin{pmatrix}
1 \\ 0
\end{pmatrix}
$$
$a_{0}=1$ , $b_{0}=0$最後寫成上式，將上面右式的矩陣乘開便得到$\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^n-\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^n$
* 用的個公式算看似只需要常數時間便能求出答案，但其實浮點數的精確度是有限的，因此 $\frac{1±\sqrt{5}}{2}$ 的次方數越大就會有更大的誤差

### [Fast Doubling](https://chunminchang.github.io/blog/post/calculating-fibonacci-numbers-by-fast-doubling) 手法
$$
\begin{split}
\begin{bmatrix}
F(2n+1) \\
F(2n)
\end{bmatrix} &=
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^{2n}
\begin{bmatrix}
F(1) \\
F(0)
\end{bmatrix}\\ \\ &=
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^n
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^n
\begin{bmatrix}
F(1) \\
F(0)
\end{bmatrix}\\ \\ &=
\begin{bmatrix}
F(n+1) & F(n) \\
F(n) & F(n-1)
\end{bmatrix}
\begin{bmatrix}
F(n+1) & F(n) \\
F(n) & F(n-1)
\end{bmatrix}
\begin{bmatrix}
1 \\
0
\end{bmatrix}\\ \\ &=
\begin{bmatrix}
F(n+1)^2 + F(n)^2\\
F(n)F(n+1) + F(n-1)F(n)
\end{bmatrix}
\end{split}
$$

因此可得:
$$
\begin{split}
F(2k) &= F(k)[2F(k+1) - F(k)] \\
F(2k+1) &= F(k+1)^2+F(k)^2
\end{split}
$$
我們便可以由 $F(k)$ 和 $F(k+1)$ 算出 $F(2k)$ 和 $F(2K+1)$，需 $O(\log{n})$ 次計算，但$F(50)$ 已經是 11 位數了，兩個大數相乘計算時間又會變得更長!

### 使用 Fast Doubling 加快計算費氏數列
* 原本的寫法所花的時間為 $O(n)$

static long long fib_sequence(long long k)
{
    long long f[k + 2];
    f[0] = 0;
    f[1] = 1;
    for (int i = 2; i <= k; i++) {
        f[i] = f[i - 1] + f[i - 2];
    }
    return f[k];
}

* Fast doubling ，從 MSB 開始計算 $F(k)$ 和 $F(k+1)$ 必須判斷目前的 bit 是否為 1，
為了先算出他的二進位表示，我先跑了一次 `while` 同時算出他有幾位，這裡之後還要改成 `clz / ctz` 指令就不用先跑一次 $O(log(n))$

static long long fib_fast_doub(long long k)
{
    int bin_k[10];
    int count = 0;
    while (k) {
        bin_k[count] = k % 2;
        k = k >> 1;
        count++;
    }
    long long int a = 0, b = 1;
    for (int i = count - 1; i >= 0; i--) {
        a = a * ((2 * b) - a);
        b = b * b + a * a;
        if (bin_k[i] == 1) {
            long long tmp;
            tmp = a + b;
            a = b;
            b = tmp;
        }
    }
    return a;
}

* 在 user space 進行[實驗](https://github.com/Hsuhaoxiang/fibdrv/blob/master/add_fastdouble.c)並將實驗的數據以 gnuplot 繪製成圖表

在40項之後可以看出兩種演算法所花的時間差距會越來越大

### 增加 $Fib(n)$ 的數值範圍
* 因為超過 long long 所能表示的資料範圍就會溢位，原本的程式 $Fib(93)=-6246583658587674878$ 必須更改儲存數值的方式

* 目前正在參考 [bignum](https://github.com/sysprog21/bignum) 的做法

---
## 複習 C 語言 數值系統 和 bitwise operation，思考 Fibonacci 數快速計算演算法的實作中如何減少乘法運算的成本

* 大數乘法可以用 Karatsuba 演算法加速