# 2021q1 Homework1 (quize1)
contributed by < `idoleat` >

## 進度
- [ ] 解釋 Quiz1 程式運作原理，搭配 Graphviz，比照 [Linked List 練習題](https://hackmd.io/@sysprog/linked-list-quiz) 在 HackMD 筆記上視覺化展現
- [ ] 測試程式使用到 random，多執行幾次可發現輸出結果相仿，請修正，並引入其他 Pseudorandom number generator
- [ ] 參考 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) 並重寫上述 quick sort 程式碼，避免使用遞迴呼叫
- [ ] Linux 核心內部也有 linked list 實作，但是 circulr doubly-linked list，[linux-list](https://github.com/sysprog21/linux-list) 仿效 Linux 核心的實作並予以簡化，在 `examples/` 目錄提供 quick sort 實作，請探討 Linux 的 linked list 和上述程式碼的落差，並改寫 [linux-list](https://github.com/sysprog21/linux-list) 的 quick sort 範例，避免使用遞迴呼叫
* 參考資料: The Linux Kernel API - List Management Functions
- [ ] 研讀 Ching-Kuang Shene ([冼鏡光](https://zh.wikipedia.org/zh-tw/%E5%86%BC%E9%8F%A1%E5%85%89)) 教授撰寫的 [A Comparative Study of Linked List Sorting Algorithms](https://pages.mtu.edu/~shene/PUBLICATIONS/1996/3Conline.pdf)，思考高效率的 linked list 排序演算法，並落實於上述的程式碼中

## 解釋 Quiz1
`list_add_node_t(node_t **list, node_t *node_t)`
把傳入的 node 的 next 指向傳入的 list 的內容，再把 list 更新為該 node，亦即把 node 加入至 list 的最前端。

`list_concat(node_t **left, node_t *right)`
left 會指向一個 node，在 while 迴圈中他會一直往下指直到變成 NULL

`quicksort`

:::info
如果把表示 list 的 `node_t **list` 都改成 `node_t *list` 會有什麼問題？
> [你所不知道的 C 語言：指標篇](https://hackmd.io/@sysprog/c-pointer#%E6%B2%92%E6%9C%89%E3%80%8C%E9%9B%99%E6%8C%87%E6%A8%99%E3%80%8D%E5%8F%AA%E6%9C%89%E3%80%8C%E6%8C%87%E6%A8%99%E7%9A%84%E6%8C%87%E6%A8%99%E3%80%8D) 內有比較範例，及 list 實做上使用與不使用 pointer to pointer 的比較
:::

## 引入其他 PNG 並修正
在先前一個 nodejs 的專案中，我發現 nodejs 沒有內建的 Pseudorandom number generator，所以需要 [自己實做](https://github.com/idoleat/ACORN-Js) 一個。在 wikipedia 上我找了一個最容易理解及實做的 ACORN~\[1\]\[2\]~ 演算法來實做，就該專案的使用情形來說還行，但是其實都還沒實際測試過他是不是真的夠亂，這是一個很好的機會用 C 語言再實做一遍，並執行例如 Monte Carlo 等測試，並以圖表呈現。

\[1\] http://acorn.wikramaratna.org/concept.html
\[2\] https://www.sciencedirect.com/science/article/pii/S0377042709006931

如果結果不如預期則思考哪裡實做不對，因為根據 [別人做的實驗](http://acorn.wikramaratna.org/assets/ACORN_TestingWithTestU01_RoyalSociety_2019.pdf) 他長期累積的亂數是足以 uniformly distributed 的

### ACORN
Repository: https://github.com/idoleat/Linux2021_Quizzes/tree/master/Quiz1

亂數計算的方法如下
:::info
給定一個 order $K$ 和 modulus $M$（通常是 2 的次冪），讓種子碼 $Y^0_0$ 為一個正整數，滿足 $0 < Y^0_0 < M$，以及初始值 $Y^m_0$ $m=1,....,k$，每個皆滿足 $0 \leq Y^m_0 < M$

則一個 $K$ order 的 Additive Congruential Random Number (ACORN) 被定義為
$$
\begin{align*}
& Y^0_0 = Y^0_{n-1}\qquad n\geq1 \\
& Y^m_n = [Y^{m-1}_n + Y^m_{n-1}]\qquad n\geq1,m=1,...,k \\
& X^k_n=Y^k_n/M \qquad n\geq1
\end{align*}
$$
:::
$Y^k_n$ 的範圍為 $[0,M)$ 的亂數生成結果，而 $X^k_n$ 為 $[0,1)$ 的結果。

除了設定種子碼，還必須先設定 order $K$ 、初始值 $Y^m_0$ 還有 $M$。通常累加的次數 $K$ 會大於 10，$M$ 為 2 的次冪，因為種子必須與其互質，而選擇為 2 的次冪那種子的限制就只有必須是奇數。依據作者建議 $M=2^{30t} \quad ,t \in Z^+$，可獲得較佳結果，2 以上最好。

### Issue
* 生成結果前幾個數字都特別小：原因是累加的次數不夠多，最直接的方法就是增加 order 或是要求足夠大的 seed 或 initial value。我覺得 initial values 也是決定亂數品質的一個重要關鍵但是作者網站上沒什麼著墨，我再看一下 \[2\] 的分析看看是不是我誤會了什麼
* Seed 只能是奇數，意味只有 $M/2$ 個，目前碰到偶數 seed 的作法都是自動減一（加一可能會發生 overflow，但是減一可能會發生 underflow），直接除以二可能會是比較好的作法？那麼種子允許的輸入範圍就會是 $(0,2M)$ ，但是還是會有相鄰種子碰撞的問題 :shrug:
* 實做過程中發現

void foo(int *arr)
{
    // arr is an array passed to this function
    int size = sizeof(arr)/sizeof(int);
}

這樣 size 永遠都是 1，得不到 arr 的大小喔，所以可以理解各式函式庫會有「有 n」和「沒 n」的兩種函式，例如 `strcpy()` 和 `strncpy()`，前者不會也沒辦法判定字串陣列大小，後者則需要者用者明確指定大小來解決前者的缺陷。（以上說法待商榷）

### 測試
* Monte Carlo value for Pi
* Arithmetic mean value of data bytes
* Serial correlation coefficient
* 替換測試程式中的 `random()`

not yet