2021q1 Homework1 (quize1)

contributed by < idoleat >

進度

• 解釋 Quiz1 程式運作原理，搭配 Graphviz，比照 Linked List 練習題 在 HackMD 筆記上視覺化展現
• 測試程式使用到 random，多執行幾次可發現輸出結果相仿，請修正，並引入其他 Pseudorandom number generator
• 參考 Optimized QuickSort — C Implementation (Non-Recursive) 並重寫上述 quick sort 程式碼，避免使用遞迴呼叫
• Linux 核心內部也有 linked list 實作，但是 circulr doubly-linked list，linux-list 仿效 Linux 核心的實作並予以簡化，在 examples/ 目錄提供 quick sort 實作，請探討 Linux 的 linked list 和上述程式碼的落差，並改寫 linux-list 的 quick sort 範例，避免使用遞迴呼叫
  • 參考資料: The Linux Kernel API - List Management Functions
• 研讀 Ching-Kuang Shene (冼鏡光) 教授撰寫的 A Comparative Study of Linked List Sorting Algorithms，思考高效率的 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

如果把表示 list 的 node_t **list 都改成 node_t *list 會有什麼問題？

你所不知道的 C 語言：指標篇 內有比較範例，及 list 實做上使用與不使用 pointer to pointer 的比較

引入其他 PNG 並修正

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

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

如果結果不如預期則思考哪裡實做不對，因為根據 別人做的實驗 他長期累積的亂數是足以 uniformly distributed 的

ACORN

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

亂數計算的方法如下

給定一個 order

$K$ 和 modulus

$M$（通常是 2 的次冪），讓種子碼

$Y_0^0$ 為一個正整數，滿足

$0<Y_0^0<M$，以及初始值

$Y_0^m$

$m=1,....,k$，每個皆滿足

$0\le Y_0^m<M$

則一個

$K$ order 的 Additive Congruential Random Number (ACORN) 被定義為

$$\begin{array}{rl}& Y_0^0=Y_{n-1}^{0}n\ge 1\\ & Y_n^m=[Y_n^{m-1}+Y_{n-1}^m]n\ge 1,m=1,...,k\\ & X_n^k=Y_n^k/Mn\ge 1\end{array}$$

$Y_n^k$ 的範圍為

$[0,M)$ 的亂數生成結果，而

$X_n^k$ 為

$[0,1)$ 的結果。

除了設定種子碼，還必須先設定 order

$K$ 、初始值

$Y_0^m$ 還有

$M$。通常累加的次數

$K$ 會大於 10，

$M$ 為 2 的次冪，因為種子必須與其互質，而選擇為 2 的次冪那種子的限制就只有必須是奇數。依據作者建議

$M=2^{30t},t\in Z^{+}$，可獲得較佳結果，2 以上最好。

Issue

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

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