# 2024q1 Homework1 (lab0)
contributed by < `lintin528` >
### Reviewed by `mervin0102`
關於 `q_merge` 的實作，我的作法是使用 `q_sort` 中所使用的 merge 來將不同的佇列合併，這樣作的好處是， `q_sort` 在排序的過程中，仍會把佇列拆開再排序合併，然而 `q_merge` 中，已知每個佇列都是以排序的狀況，因此只需要注重排序合併就好，有此可知，呼叫 `q_sort` 較沒有效率。
但是我的作法仍有一些缺點，當需要合併的佇列數量龐大時，由於實作方法是將所有佇列與第一個佇列作合併排序，因此當第一個佇列長度越來越長時，合併會越來越沒有效率，改進方法可以參考 linux/list_sort.c ，將合併長度控制在 2 的冪次可以達到最佳的合併效率。
> 你的洞見呢？與其談「心法」，不如設想「如果我是你」，我會怎麼做，示範一次給同學看，而且檢討自己哪裡沒做好，從而呼應原本學員的不足處。
> [軟體工程師要學會說故事](https://ruddyblog.wordpress.com/2016/06/18/)，本作業要求學員從良性詳盡的批評開始。繼續檢討！
> :notes: jserv
## 開發環境
```xml
$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.2) 9.4.0
$lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 12
On-line CPU(s) list: 0-11
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 151
Model name: 12th Gen Intel(R) Core(TM) i5-12400
Stepping: 2
CPU MHz: 2500.000
CPU max MHz: 4400.0000
CPU min MHz: 800.0000
BogoMIPS: 4992.00
Virtualization: VT-x
L1d cache: 288 KiB
L1i cache: 192 KiB
L2 cache: 7.5 MiB
L3 cache: 18 MiB
NUMA node0 CPU(s): 0-11
```
## 針對佇列操作的程式碼實作
### `q_new`
:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
><s>已修正!</s>
> 認真檢視下方內容，你真的修正了嗎？不要急著假裝自己有做事，誠實面對自己！ :notes: jserv
:::
功能為建立一個新的"空"佇列，因此僅宣告一個新的指標指向 `list_head` ，並不需要做element_t之初始化。
首先利用 `malloc` 配置記憶體空間，並且檢測是否發生記憶體配置失敗產生 `NULL` 佇列，後使用 "list.h" 定義的 `INIT_LIST_HEAD` 完成佇列之初始化。
:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
:::
```c
struct list_head *q_new()
{
struct list_head *new_queue = malloc(sizeof(struct list_head));
if (new_queue == NULL)
return NULL;
INIT_LIST_HEAD(new_queue);
return new_queue;
}
```
> commit [f04e991](https://github.com/sysprog21/lab0-c/commit/f04e9919b56c572e663924f7ca4d04ab2369a89a)
>(這裡因為用實驗室電腦 push 且忘記登出原有 github 導致由不同 user 進行 commit)
:::danger
列出對應 commit 的 GitHub 超連結
:::
### q_insert_head and q_insert_tail
#### q_insert_head
首先檢查兩個 `struct` 指標是否都不為 `NULL`，之後透過在 "queue.h" 定義好的`list_add` 進行 `list_head` 的雙向連結，之後使用 `strdup` 建立副本後 ，配置給 `element_t->value` ，因為這裡有新配置記憶體，需要再做一次 `if (new_value == NULL)` 檢查是否成功。
```c
bool q_insert_head(struct list_head *head, char *s)
{
element_t *new_element = malloc(sizeof(element_t));
if (new_element == NULL || head == NULL)
return 0;
list_add(&new_element->list, head);
char *new_value = strdup(s);
if (new_value == NULL)
return 0;
new_element->value = new_value;
return true;
}
```
#### q_insert_tail
此部分大抵與 `q_insert_head` 相同，唯一的差異在於使用 `list_add_tail` 插入在佇列的尾端。
```c
bool q_insert_tail(struct list_head *head, char *s)
{
element_t *new_element = malloc(sizeof(element_t));
if (new_element == NULL || head == NULL)
return 0;
list_add_tail(&new_element->list, head);
char *new_value = strdup(s);
if (new_value == NULL)
return 0;
new_element->value = new_value;
return true;
}
```
> commit [9516360](https://github.com/sysprog21/lab0-c/commit/95163601b814d9787d144b218c630d3c280443ba)
考慮到若使用者插入一個空字串有可能會導致 `'\0'` 字元出現在 list 內，將有可能使 `'\0'` 後的字元遺失，因此加入 input char *s 是否為空字串的檢測。
```diff
element_t *new_element = malloc(sizeof(element_t));
- if (new_element == NULL || head == NULL)
+ if (new_element == NULL || head == NULL || s == NULL)
return 0;
```
> commit [bbbaf7e](https://github.com/sysprog21/lab0-c/commit/bbbaf7e14f0f1ec167021bbb936c32e7fccb01ad)
改變執行順序以些微改善效能
> commit [d7fe98b](https://github.com/sysprog21/lab0-c/commit/d7fe98b7c0eec97841c92baaafe1f268db8a71c4)
:::danger
你如何證明這項變更得以改善效能？又，改善幅度有多大？工程人員說話要精準，拿出客觀事實來佐證。
:::
:::info
考慮發生 `malloc failed` 的情況下，某些動作可以放到 `== NULL` 的檢測之後，以避免像是 `list_add(&new_element->list, head);` 結束後，才發現 `s == NULL` 變成多餘的指令，效能的改善根據發生 `malloc failed` 的多寡決定。
:::
:::warning
既然與`q_insert_head`相似，能否將兩函式整合，使程式更加精簡
:notes: marvin0102
:::
### q_free
:::danger
- [ ] traverse (動詞) 和 traversal (名詞)
根據 Dictionary.com 的[解釋](https://www.dictionary.com/browse/traverse
): (作為及物動詞和不及物動詞都有類似的意思，以下列出作為及物動詞的寓意)
* to pass or move over, along, or through.
* to go to and fro over or along.
其實這意思很好懂，就像我們「走過」/「穿越」校園一般，於是 traverse a linked list 就會是「(用某種手段) 存取多個鏈結串列的節點」，但這裡卻沒有必要「所有」的範圍：英語的 "move over/through" 用於某個區域時，根本沒有這樣的隱含意義。如果將 traverse 翻譯為「遍歷」，就會導致「超譯」，也就是跳脫「直譯」和「意譯」。
當我們回頭看 "traverse" 所在的技術描述內容，例如 "traverse every node"，若翻譯為「遍歷每個節點」，那麼既然都「遍」(意即「全面」、「到處」)，又何來「每個」節點呢？於是，合理的翻譯應改為「逐一走訪每個節點」 —— 差異在哪？在 "traverse every node" 的應用場景中，可能是我們嘗試在鏈結串列尋找特定的節點內含的資料，一旦找到就停止，或者我們要偵測給定的鏈結串列是否包含環狀 (circular) 結構 ，並沒有真的要「遍」(到處/全面)「歷」(意即「經過」) 每個節點。在我們的用語中，要區分「意圖」(intention) 和「實際作用」(reaction)，濫用「遍歷」會使得語意不清，從而難以推測英語原文的訴求。
還有個更重要的原因是，「遍歷」這詞已在理工領域存在，且廣泛使用，即「遍歷理論」(Ergodic theory)，後者是研究具有不變測度 (invariant measure) 的動力系統及其相關問題的一個數學分支。 遍歷理論研究遍歷變換，由試圖證明統計物理中的遍歷假設 (Ergodic hypothesis) 演進而來。
在統計學中，若單一個物理系統在不同時間內重複相同的實驗 (如丟擲一枚硬幣)，其取樣數據所得的統計結果 (如硬幣出現正面的機率) 和極多個完全相同的物理系統的系集 (如丟極多個相同的硬幣) 在同時作相同的實驗取樣數據的統計結果假設為相同時，此種假設即稱為「遍歷性假設」或「遍歷假設」。基於這個假設，對時間平均的統計方式及結果，便可由對系集的平均及統計方式得到。在一般物理系統中，尤其在統計力學範圖中，均採用此遍歷性假設為基本的假設。在流體力學中對亂流的實驗分析，亦是採用此假設。
遍歷 (Ergodic) 源於以下二個希臘詞：
* ergon (對應英語的 work)
* odos (對應英語的 path 或 way)
最初這是由奧地利物理學家波茲曼 ([Ludwig Boltzmann](https://en.wikipedia.org/wiki/Ludwig_Boltzmann)) 於統計力學領域 (statistical mechanics) 提出的概念，其一廣為人知的結果是：在經過長時間後，時間平均將會趨近空間平均。此事實在動力系統扮演極重要的角色，在隨機分析領域亦然。
因此，若貿然將 traverse 翻譯為「遍歷」，一來語意不清，二來增加和理工多項領域專業人員的溝通成本，實在得不償失。
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::
使用 "list.h" 中的 `list_for_each_safe` <s>遍歷</s> 拜訪該佇列的每個 `element_t` 並使用 "queue.h" 中的 `q_release_element` 將其釋放後，最終釋放 `head of queue` 的記憶體。
其中 `node, safe` 作為 `list_for_each_safe` 的暫存變數使用。
```c
void q_free(struct list_head *head)
{
if (head == NULL)
return;
struct list_head *node;
struct list_head *safe;
list_for_each_safe (node, safe, head) {
element_t *next_elem = list_entry(node, element_t, list);
q_release_element(next_elem);
}
free(head);
}
```
這邊遇到的問題是當初使用 `while` 遍歷整個佇列時，在 qtest 中會發生以下錯誤：
```c
//while ...
element_t *node = list_entry(next_head, element_t, list);
q_release_element(node);
next_head = next_head->next;
```
```
cmd> free
Segmentation fault occurred. You dereferenced a NULL or invalid pointerAborted
(core dumped)
```
後來看到 "list.h" 實作的 `list_for_each_safe ` 才發現 `safe` 這個暫存變數的必要性。
> commit [d2932a0](https://github.com/sysprog21/lab0-c/commit/d2932a036d2472a093aee81ca2bb86a4bd0a9ca9)
主要修正記憶體未完全釋放的問題，在 `new_element` 記憶體配置成功但 `new_value` 配置失敗的情況下， 需要將 `new_element` 釋放；此外些微修改 tasks 的執行順序以求減少錯誤時 `malloc` 與 `free` 的次數。
```diff
- if (head == NULL || s == NULL) {
- return 0;
- }
element_t *new_element = malloc(sizeof(element_t));
- if (new_element == NULL)
+ if (new_element == NULL || head == NULL || s == NULL)
return 0;
+ list_add(&new_element->list, head);
+
char *new_value = strdup(s);
- if (new_value == NULL) {
- free(new_element);
+ if (new_value == NULL)
return 0;
- }
```
>second commit : d7fe98b
### q_remove_head and q_remove_tail
在進行實作的時候，一開始儲存 string 的方式如下：
```c
element_t *removed = list_entry(head, element_t, list);
char *saved_value = strdup(removed->value);
if (sp && saved_value)
sp = saved_value;
```
用這個方式寫的話，會發生 `Segmentation fault occurred.` 與 `ERROR: Failed to store removed value` 的問題。
發現不該使用 `list_entry` 應該使用 `list_first_entry`，解決 `Segmentation fault occurred.`。
更改 string 的儲存方式：
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (head == NULL)
return NULL;
element_t *removed = list_first_entry(head, element_t, list);
if (sp){
memcpy(sp, removed->value, bufsize);
sp[bufsize - 1] = '\0';
}
list_del(&removed->list);
return removed;
}
```
比較兩者差異，先前使用的方式將配置一塊新的記憶體空間複製原有 `removed->value` 指向的內容，並改變 `sp` 指標位址為新配置記憶體空間之位址，猜想原先出現的錯誤 `ERROR: Failed to store removed value` 可能為偵測到 `sp` 被更改 (不確定)；後者為將原有 `removed->value` 指向的內容複製到 `sp` 指向的記憶體空間內。另外先前的使用方式需要釋放 `sp` 原有的記憶體空間
> commit [43bf04a](https://github.com/sysprog21/lab0-c/commit/43bf04a3fbef2e0ac80b3b7b15f682f0e590f304)
:::warning
兩函式功能相似，能否將兩函式整合，使程式更加精簡
:notes: marvin0102
:::
### q_size
首先處理佇列為空及 NULL queue 的情形，將 return 0，其餘情況則使用簡單的計數器及 "list.h" 中定義的 `list_for_each` 去遍歷每一個節點。
```c
int q_size(struct list_head *head)
{
if (head == NULL || head->next == head)
return 0;
struct list_head *node;
int count = 0;
list_for_each (node, head) {
count++;
}
return count;
}
```
> commit [aff7c93](https://github.com/sysprog21/lab0-c/commit/aff7c93fd3bd6744126f2ee1b147a6a1bb876ed2)
### q_delete_mid
透過 `q_size` 的實作取得佇列長度後取得位於中點的 `list_head` ，並透過 `list_entry` 取得 `element_t` 後進行節點的釋放。
```c
bool q_delete_mid(struct list_head *head)
{
int size = q_size(head);
int count = 0;
struct list_head *mid = head->next;
size /= 2;
while (count <= size - 1) {
mid = mid->next;
count++;
}
element_t *mid_element = list_entry(mid, element_t, list);
list_del(mid);
q_release_element(mid_element);
return true;
}
```
> commit [8803593](https://github.com/sysprog21/lab0-c/commit/8803593452d9d881f3ff609694392974a2ea367e)
>
更新後：改以快慢指標尋找佇列中位數。
```diff
+ int size = q_size(head);
+ int count = 0;
struct list_head *mid = head->next;
- struct list_head *fast = head->next->next;
- while (fast != head && fast->next != head) {
+ size /= 2;
+ while (count <= size - 1) {
mid = mid->next;
- fast = fast->next->next;
+ count++;
}
```
>second commit [3aa4d57](https://github.com/sysprog21/lab0-c/commit/3aa4d57fd5be44261f557c4c220c763d15e6f149)
:::danger
1. 改進你的漢語表達
2. 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
:::
### q_delete_dup
遍歷每一個節點時查看右方所有節點，若有相同者先將右方所有重複節點刪除，跳出迴圈後再將原本重複的節點也刪除。
這裡遇到過許多次的 `segmentation fault` ，對於鏈結串列的釋放以及 `safe` 的更改需要多加注意，才能不產生迴圈執行過程指向錯誤目標的問題。
```c
while (safe != head) {
node_e = list_entry(node, element_t, list);
safe_e = list_entry(safe, element_t, list);
safe = safe->next;
if (strcmp(node_e->value, safe_e->value) == 0) {
list_del(safe->prev);
q_release_element(safe_e);
dup_flag = true;
} else {
break;
}
}
safe = node->next;
if (dup_flag) {
list_del(node);
q_release_element(node_e);
dup_flag = false;
}
```
> commit [9c88029](https://github.com/sysprog21/lab0-c/commit/9c88029d558479e2967ed2361e9b5c8080d549e9)
### q_swap
根據佇列的實作特性，僅需要交換 `list_head` 的指標而不需要去對 `element_t` 做交換位址的動作，因為 `element_t` 的位址透過 `list.h` 定義的巨集 `list_entry` 完成，而非直接造訪。
原本想另外配置一新的記憶體 `struct list_head *tmp = malloc(sizeof(struct list_head));` 發現若不給他賦值會出現 `FATAL ERROR: Calls to malloc disallowed`，因此決定更換一種交換方式。
```c
tmp->prev = odd->prev;
odd->next = even->next;
odd->prev = even;
even->next = odd;
even->prev = tmp->prev;
```
**更改為**
```c
odd->next = even->next;
even->prev = odd->prev;
even->next = odd;
odd->prev = even;
even->prev->next = even;
odd->next->prev = odd;
odd = odd->next;
even = odd->next;
```
考慮到目前僅有： `odd, even` 兩個指標，必須先做 `odd->prev, even->prev` 的修改，否則將會導致丟失相鄰節點的指標。
> commit [e3f6629](https://github.com/sysprog21/lab0-c/commit/e3f662974583dc803abbb3557563f9f9764abf38)
:::danger
善用 List API 撰寫更精簡的程式碼。
:::
### q_reverse
透過<s>遍歷</s> 拜訪每一個節點後將其放置於第一個位置，以達成反轉的目的。
```c
struct list_head *current = head->next;
while (current != head) {
struct list_head *tmp;
tmp = current;
current = current->next;
list_move(tmp, head);
}
```
> first commit [3e53ce5](https://github.com/sysprog21/lab0-c/commit/3e53ce55fdd09e03a064dfc076a6e5fa2ab51c35)
### q_reverseK
大抵與 `q_reverse` 相同，改良了多餘的變數 `tmp` 使用，且發現可以運用 `list.h` 的 `list_for_each_safe`，除此之外僅多了一計數器去做大小為 `K` 的分區動作。
```c
list_for_each_safe (first, safe, head) {
int count = 0;
while (count < k - 1 && safe != head) {
safe = safe->next;
list_move(safe->prev, first->prev);
first = first->prev;
count++;
}
}
```
> commit [5e5ecae](https://github.com/sysprog21/lab0-c/commit/5e5ecae0e9e2aef876221bda447d53918b402415)
### q_ascend
原本會引發 bus error。
:::danger
出處呢？能否用你對作業系統認知來解釋？能否用更精簡的程式碼重現 (reproduce)？
access 的翻譯是「存取」，而非「訪問」
:::
<s>經查詢</s> ， bus error 發生在嘗試<s>訪問</s> 位於非對齊地址上的資料時，或者嘗試<s>訪問</s> 不存在的記憶體位置時，在我原本的這段程式碼中，問題發生在 `safe = node->next;` 之前，若將最後一個節點刪除，將會在這一行引發 bus error ，因為此處的 `node` 已被刪除。
```c
list_for_each_safe (node, safe, head) {
all_nodes++;
while (safe != head && node != head) {
node_e = list_entry(node, element_t, list);
safe_e = list_entry(safe, element_t, list);
safe = safe->next;
if (strcmp(node_e->value, safe_e->value) >= 0) {
safe = node->next;
list_del(node);
q_release_element(node_e);
del_nodes++;
break;
}
}
safe = node->next;
}
return all_nodes - del_nodes;
```
後來又想過先以 `safe` 保存 `node->prev` ，當節點被釋放後此時的 `safe->next` 將會是原本的 `node->next` 以繼續遍歷整個佇列，但若是該次的節點並沒有被刪除， `safe` 會是原本的 `node`。
```diff
safe_e = list_entry(safe, element_t, list);
- safe = safe->next;
+ safe = node->prev;
- safe = node->next;
+ safe = safe->next;
}
return all_nodes - del_nodes;
```
功能部分完成 (問題紀錄)：
```c
list_for_each_safe (node, safe, head) {
all_nodes++;
while (safe != head && node != head) {
node_e = list_entry(node, element_t, list);
safe_e = list_entry(safe, element_t, list);
safe = safe->next;
if (strcmp(node_e->value, safe_e->value) >= 0) {
safe = node->next;
list_del(node);
q_release_element(node_e);
del_nodes++;
del = true;
break;
}
}
if (!del)
safe = node->next;
}
return all_nodes - del_nodes;
```
錯誤紀錄
>更新：發現改為不嚴格遞增/遞減就不會跑出錯誤訊息
```
l = [1 1 2]
cmd> ascend
l = [1 ... ]
ERROR: Queue has more than 1 elements
```
> commit [4c28e6c](https://github.com/sysprog21/lab0-c/commit/4c28e6c1219acb9ddaf2499ae74999ecfe29100d)
最終版，修改判斷式
```diff
- strcmp(node_e->value, safe_e->value) >= 0
+ strcmp(node_e->value, safe_e->value) > 0
```
>second commit [30e8bd5](https://github.com/sysprog21/lab0-c/commit/30e8bd52ca64132cd1b15e7d35224c35d098bdea)
### q_descend
與 `q_ascend` 大抵相同，僅有 `strcmp` 之判斷式改變。
```diff
- strcmp(node_e->value, safe_e->value) > 0
+ strcmp(node_e->value, safe_e->value) < 0
```
### q_sort
使用merge sort <s>實現</s> 排序，做的過程中發現升、降序最好能在 `void merge` 內做調整，因為若要再進行 `q_sort` 後反轉還需要多餘的判斷式，比較沒有效率。
實作透過快慢指標求得佇列的中間位置後使用 `list.h` 內定義的 `list_cut_position` 將中點之前的所有節點取出並移至 `left` 內，而 `list_splice_init` 將原本 `head` 剩餘的節點全部移至 `right` ，這麼做是為了在之後的 `merge` 可以直接合併回原本的 `head`。
```c
LIST_HEAD(left);
LIST_HEAD(right);
list_cut_position(&left, head, mid);
list_splice_init(head, &right);
q_sort(&left, descend);
q_sort(&right, descend);
merge(head, &left, &right, descend);
```
#### merge
比較兩個佇列中第一個元素，並將較大的拼接回 `head` ，當一個佇列為空時，將另一個佇列拼接回 `head` ，由此完成最終的排序。
```c
if (strcmp(left_first_node->value, right_first_node->value) >= 0)
list_move(left->next, head->prev);
else
list_move(right->next, head->prev);
...
if (left->next == left)
list_splice_tail(right, head);
else
list_splice_tail(left, head);
```
> commit [6de00de](https://github.com/sysprog21/lab0-c/commit/6de00defc66f7b107a213811d27fc8c84732d8ce)
### q_merge
透過 `list_entry(node, queue_contex_t, chain)` 去尋找 `chain` 之上級結構後將全部的佇列拼接到 `head->next` 的佇列裡，最後進行 `q_sort` 完成排序。
```c
list_for_each_safe (node, safe, head) {
// skip first iteration
if (node != head->next) {
queue_contex_t *next_block =
list_entry(node, queue_contex_t, chain);
total_elements += next_block->size;
list_splice_init(next_block->q, first_queue);
}
}
q_sort(first_queue, descend);
```
> commit [2308658](https://github.com/sysprog21/lab0-c/commit/23086584dd97f5b805b1d60671b2fdf5a6be106f)
---
## 研讀論文〈Dude, is my code constant time?〉後改進 lab0-c
文中介紹了一款稱做 `dudect` 的工具，用以在平台上透過程式執行時間的分布去判斷他是否在常數時間內進行，以防止 `Timing attacks` 導致一些敏感訊息被透過密碼學的方式反向推導。
這個工具的執行過程大概可以分為以下三個部分：
1. 根據 `fix-vs-random` 類別定義，對執行時間進行多次採樣，模擬不同的測試環境下，執行時間的分布情形。
2. 透過 `prepare_percentiles` 去統計執行時間的分布，計算出設定的閾值，並對執行時間的樣本做修剪，以消除那些執行時間較長的極端情況，從而提高測試的準確性。
3. 在 `update_statistics ` 中，透過 `Welch's t-test` 去判斷修剪前後執行時間的平均值差異，將產生一個預估值 't' ，若得到的 't' 超過設定的臨界值即判斷程式的執行時間不是常數時間。
### student's t-distribution
student's t-distribution 通常用於樣本數小或是標準差未知的情形，型態接近於常態分布，根據自由度，越大會越接近常態分布，在 `lab0-c` 中，我們使用 `is_insert_tail_const()` 與 `is_size_const()` 進行採樣，而就我的理解， `is_insert_tail_const()` 的執行時間應是固定的，因此並不符合 `t-distribution` ，但在 `fix-vs-random` 測試資料中的佇列長度屬於隨機分布， `is_size_const()` 因此屬於連續的隨機操作，即符合 `t-distribution`。
當我們得到 `t-distribution` 的樣本後，即可透過上述的步驟三去進行 `Welch's t-test` 以檢驗執行時間是否為常數時間。
### 改善 lab0-c 中關於 percentile 的處理
在 `dudect` 專案中，對於一些不可靠的樣本(可能因為執行時被OS中斷)，會去做一些 `post-processing` 將其去除，而在目前的實作中缺少了 `percentile` 的設定，這部分對應到作者提供的專案中的 `prepare_percentiles`，因此在實作中的 `dudect/fixture.c` 補上以下 :
```diff
- differentiate(exec_times, before_ticks, after_ticks);
- update_statistics(exec_times, classes);
- ret &= report();
+ bool first_time = percentiles[DUDECT_NUMBER_PERCENTILES - 1] == 0;
+ if (first_time) {
+ prepare_percentiles(exec_times, percentiles);
+ } else {
+ differentiate(exec_times, before_ticks, after_ticks);
+ update_statistics(exec_times, classes);
+ ret &= report();
+ }
```
:::danger
指出論文和程式碼實作的出入。
:::
---
## 研讀 Linux 核心原始程式碼的 lib/list_sort.c 並嘗試引入到 lab0-c 專案
### list_sort.c 原始程式碼閱讀
| count 變化 | count 二進位 | merge | pending 上的節點 |
| ----------- | ------------------- | ----------- | ----------------------------------------- |
| 0 $\to$ 1 | 0000 $\to$ 0001 | no（$2^0$） | 1 |
| 1 $\to$ 2 | 0001 $\to$ 0010 | no（$2^1$） | 1 $\gets$ 1 |
| 2 $\to$ 3 | 0010 $\to$ 001==1== | yes | (2) $\gets$ 1 |
| 3 $\to$ 4 | 0011 $\to$ 0100 | no（$2^2$） | 2 $\gets$ 1 $\gets$ 1 |
| 4 $\to$ 5 | 0100 $\to$ 010==1== | yes | 2 $\gets$ (2) $\gets$ 1 |
| 5 $\to$ 6 | 0101 $\to$ 01==1==0 | yes | (4) $\gets$ 1 $\gets$ 1 |
| 6 $\to$ 7 | 0110 $\to$ 011==1== | yes | 4 $\gets$ (2) $\gets$ 1 |
| 7 $\to$ 8 | 0111 $\to$ 1000 | no（$2^3$） | 4 $\gets$ 2 $\gets$ 1 $\gets$ 1 |
| 8 $\to$ 9 | 1000 $\to$ 100==1== | yes | 4 $\gets$ 2 $\gets$ (2) $\gets$ 1 |
| 9 $\to$ 10 | 1001 $\to$ 10==1==0 | yes | 4 $\gets$ (4) $\gets$ 1 $\gets$ 1 |
| 10 $\to$ 11 | 1010 $\to$ 101==1== | yes | 4 $\gets$ 4 $\gets$ (2) $\gets$ 1 |
| 11 $\to$ 12 | 1011 $\to$ 1==1==00 | yes | (8) $\gets$ 2 $\gets$ 1 $\gets$ 1 |
| 12 $\to$ 13 | 1100 $\to$ 110==1== | yes | 8 $\gets$ 2 $\gets$ (2) $\gets$ 1 |
| 13 $\to$ 14 | 1101 $\to$ 11==1==0 | yes | 8 $\gets$ (4) $\gets$ 1 $\gets$ 1 |
| 14 $\to$ 15 | 1110 $\to$ 111==1== | yes | 8 $\gets$ 4 $\gets$ (2) $\gets$ 1 |
| 15 $\to$ 16 | 1111 $\to$ 10000 | no（$2^4$） | 8 $\gets$ 4 $\gets$ 2 $\gets$ 1 $\gets$ 1 |
根據這張圖，可以看到當本次 count 增加為 2 的冪次時都不會有 merge 的動作，這部分也可以在原始碼的核心部分看到，如下：
```c
do {
size_t bits;
struct list_head **tail = &pending;
/* Find the least-significant clear bit in count */
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
/* Do the indicated merge */
if (likely(bits)) {
struct list_head *a = *tail, *b = a->prev;
a = merge(priv, cmp, b, a);
/* Install the merged result in place of the inputs */
a->prev = b->prev;
*tail = a;
}
/* Move one element from input list to pending */
list->prev = pending;
pending = list;
list = list->next;
pending->next = NULL;
count++;
} while (list);
```
可以看到 `if (likely(bits))` 不會被觸發的情況，只有在 `count` 為 `2^k - 1` 時，這邊有個巧妙的設計，考慮到鏈結串列的分區方式，如 `2 ← 2 ← 1` 也就是 `count = 5` 時，可以發現每一區都是透過 `prev` 去連接，所以這邊透過
```c
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
```
來取得要執行 `merge` 的兩個節點，這邊對應到的是表格中的 `count 4-5, 0101` 中，在 `count` 的二進位中，後面有幾個 `1` 即代表 `merge` 的起點需要往前幾個節點，像這一步就是要往前一個節點，起點為 `2 ← (2) ← 1` ，並與他的 `prev` 也就是 `(2) ← 2 ← 1` 做 `merge`。
再來就是所有的節點都移至 `pending` 之後，將會執行以下，將所有的區塊合併成最後剩下兩個區塊，如在 `4 ← 2 ← 1` 結束時，將從尾端開始，合併為 `4 ← 3` 的區間，然而此時 `next` 指向頭部的 `prev` ，即 `NULL` ，而停止。
```c
list = pending;
pending = pending->prev;
for (;;) {
struct list_head *next = pending->prev;
if (!next)
break;
list = merge(priv, cmp, pending, list);
pending = next;
}
```
最後，做最後的 `merge_final` ，這裡不同於先前的 `merge` ，還會進行雙向鏈結串列的重建，將所有的分區合併為同一個整體。
```c
merge_final(priv, cmp, head, pending, list);
```
---
### 於 lab0-c 實作 List_sort 與 Tim_sort
參考 [yu-hisennn](https://hackmd.io/@yuu907/r1gnvsn93a#%E5%BC%95%E5%85%A5-liblist_sortc)。
在 [Linux 核心的鏈結串列排序](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-e) 中提供的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 中，可以觀察到在串列的結構上與我們本次實作內容是相同的 (都是來自Linux 核心原始程式碼) ，但在導入本次實作的過程中發現了因為這個專案本身是執行在 Linux 的 kernal space ，因此有些導入的函式庫在我們的實作中就不能使用了，也導致有些巨集或是型態需要我們自己去定義，如下的 `unlikely` 原本在 <linux/compiler.h> 中被定義，但在我們的實作中需要去 "list_sort.h" 中透過 GCC 的內建函數 `builtin_expect` 去定義 `#define unlikely(x) __builtin_expect(!!(x), 0)` ；另外也知道了 `__attribute__((nonnull(2,3)))` 是為了讓某些函式的參數不為 NULL 而設定的。
```bash
list_sort.c:86:7: error: implicit declaration of function ‘unlikely’ [-Werror=implicit-function-declaration]
86 | if (unlikely(!++count))
| ^~~~~~~~
list_sort.c: In function ‘list_sort’:
list_sort.c:219:7: error: implicit declaration of function ‘likely’ [-Werror=implicit-function-declaration]
219 | if (likely(bits)) {
| ^~~~~~
```
接下來需要在 "qtest.c" 中實作 `do_sort_list` ，這邊是直接參考 `do_sort` 的流程，然後作些許修改，基本上差異只在原本呼叫 `q_sort` 改變為 `list_sort` ，並調整輸入參數。
```diff
if (!current || !current->q)
report(3, "Warning: Calling sort on null queue");
else
- cnt = q_size(current->q);
+ list_sort(NULL, current->q, list_cmp);
error_check();
```
>這裡還可以改進，加入 ascend 及 descend 的參數
最後在 `console_init` 的部分加上 `ADD_COMMAND(list_sort, "Use list_sort in Linux to sort the queue in ascending order", "");` 完成改動，從這邊也去觀察了 `console.h` 中 `#define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param)` 將剛剛定義的 `do_list_sort` 加入 `console_init` 內，然後在 "driver.py" 中就可以透過讀取 traces <s>資料夾</s> 目錄的<s>指令</s> `.cmd` 檔去執行，大概理解了 `qtest` 是如何被執行的。
:::danger
diretory 的翻譯是「目錄」，而非「資料夾」(folder)
:::
最終在 `make` 後執行 `./qtest`
```bash
l = [2 4 2 3 1]
cmd> list_sort
l = [1 2 2 3 4]
```
> commit [0f77419](https://github.com/sysprog21/lab0-c/commit/0f7741980cda5563588268bf081c7b2651baea3a)
:::warning
可以加入原始 `q_sort` 與 `list_sort` 之間的效能比較
:notes: `marvin0102`
:::
### 效能比較與分析
為了使用 perf 效能測試工具寫了兩個檔案 `sort_test.c` 與 `qsort_test.c` 用以測試 `timsort, list_sort` 與 `qsort` 的效能，其中在資料的設計中，透過 `create_sample` 可以產出完全隨機或是以排序好的資料集，透過註解的方式去調整。
```c
// elem->val = rand();
elem->val = i;
```
除此之外，在排序好的資料集中，又另外做了兩個函式以產生不同的分布情形
#### q_create_runs
在一個已排序好的資料裡，分成多個區間，且每隔一個個區間就反轉，如
`0 1 2 3 4 8 7 6 5 9 10 11 12` ，此為為了適配 `timsort` 特性的資料集。
```c
void q_create_runs(struct list_head *head)
{
if (head == NULL || head->next == head)
return;
struct list_head *first;
struct list_head *safe;
list_for_each_safe (first, safe, head) {
int count = 0;
while (count < rand() % 3 + 3 - 1 && safe != head) {
safe = safe->next;
list_move(safe->prev, first->prev);
first = first->prev;
count++;
}
}
}
```
#### shaffle_partially
每隔幾個節點，將目前的節點與尾端節點互換，並將目前位置設定為尾端，這樣的結果會是類似 `0 8 2 3 4 1 6 7 5` ，部分被打亂，較無法從資料集看出效能的關聯，暫時廢棄。
```c
static void shaffle_partially(struct list_head *head)
{
int offset = 0;
int limit;
struct list_head *tail = head->prev;
struct list_head *current = tail;
struct list_head *tmp;
while(current != head && current->prev != head) {
limit = rand() % 3 + 3;
offset = 0;
while (offset <= limit) {
if(current->prev == head) {
break;
}
current = current->prev;
offset++;
}
tmp = current->prev;
list_move(current, tail);
list_move(tail, tmp);
current = tail;
}
}
```
#### 在 "`SAMPLES 1000`"、"資料集為 `sorted` "、"套用 `q_create_runs` "的情況：
這裡令人疑惑的點是 `timsort cache-misses` 的表現竟然是這邊最差的，檢查過後資料集的分布與預想也相同，另外在比較次數的方面來觀察 `timsort, list_sort` ，可以看到 `timsort` 的比較次數竟然較多，這點不符合他創建 `runs` 以避免多次比較的特性。
>更新：
>在改變測試次數後，雖然還是有一定的浮動範圍，但明顯可以觀察出 `timsort` 出現的範圍會較其他兩者較小許多。
>對於 `timsort` 比較次數較高的情形，我給出的解釋是在實作中 `find_run` 過程中的比較也會記錄在此 `Comparisons` 內，但在上述的討論中，比較次數可能僅限於 merge 的過程中，所以這裡才無法良好的反映出 `timsort` 比較次數較少的這個特性。
`timsort` 的表現為
Comparisons 約在 (9000, 10000) 範圍區間
```
==== Testing tim_sort ====
Comparisons: 9250
List is sorted
Performance counter stats for './sort_test' (1000 runs):
2,376 cpu_core/cache-misses/ ( +- 2.99% )
20,762 cpu_core/cache-references/ ( +- 0.40% )
1,783,135 cpu_core/instructions/ ( +- 0.03% )
1,211,219 cpu_core/cycles/ ( +- 0.28% )
74 page-faults ( +- 0.04% )
0.0012438 +- 0.0000219 seconds time elapsed ( +- 1.76% )
```
`list_sort` 的表現為
Comparisons 約在 (8600, 8800) 範圍區間
```
==== Testing list_sort ====
Comparisons: 8726
List is sorted
Performance counter stats for './sort_test' (1000 runs):
3,305 cpu_core/cache-misses/ ( +- 1.99% )
23,908 cpu_core/cache-references/ ( +- 0.34% )
1,795,388 cpu_core/instructions/ ( +- 0.03% )
1,167,131 cpu_core/cycles/ ( +- 0.28% )
72 page-faults ( +- 0.04% )
0.0014723 +- 0.0000206 seconds time elapsed ( +- 1.40% )
```
`q_sort` 的表現為
```
Performance counter stats for './qsort_test' (1000 runs):
4,364 cpu_core/cache-misses/ ( +- 1.43% )
23,055 cpu_core/cache-references/ ( +- 0.35% )
1,958,077 cpu_core/instructions/ ( +- 0.03% )
1,173,050 cpu_core/cycles/ ( +- 0.26% )
72 page-faults ( +- 0.05% )
0.0013430 +- 0.0000217 seconds time elapsed ( +- 1.61% )
```
#### 在 "`SAMPLES 1000`"、"資料集為 `sorted` " 的情況：
出現了一個令人費解的情況，根據 `timsort` 的特性，可以確定的是他從頭到尾只會產生一個 `run` ，由比較次數為 999 也可以看出他一次就做完排序了，但不知道為什麼 `timsort cache-misses` 還是這裡面最高的，且 `list_sort` 的 `bottom up` 特性較傳統 `merge_sort` ，即此處的 `q_sort` 對 cache 較為友善，但在這邊測試出來的表現中，卻發現 `q_sort` 相較於 `list_sort` 的 `cache misses` 更低。
>更新：
>後來發現原本的 `sort_test.c` 中，另外還有 `Warm up` 的動作，所以相對於 `q_sort` ，共是三倍的執行量，推測原本的 `warm up` 是為了在實際執行前將 `cache` 使用狀態初始化，讓測量結果浮動值相對減少，實際上當註解掉 `Warm up` 之後多次使用 `perf stat --repeat 100` 的結果確實有很大的浮動範圍， `cache-misses` 從 `1000-9000` 都有可能出現，因此在這裡將測量次數改為 `1000` ，以取代原本的 `Warm up` 功能，以前幾次的測量作為初始化 cache 的角色。
>回頭測試當有 `Warm up` 時的執行效能，發現浮動值依然巨大， `cache-misses` 也約是 `1000-9000` 的範圍，**不知道 `Warm up` 使否實際對 cache 的使用統計有幫助**
>上面所提到 `timsort cache-misses` 是這裡面最高，後來測試改為 1000 次後，發現他的浮動範圍整體會低於其他兩者，另外 `q_sort` 表現將會是最差的，較符合預期結果。
`timsort` 的表現為
```
==== Testing tim_sort ====
Comparisons: 999
List is sorted
Performance counter stats for './sort_test' (1000 runs):
2,089 cpu_core/cache-misses/ ( +- 2.91% )
21,309 cpu_core/cache-references/ ( +- 0.36% )
1,557,116 cpu_core/instructions/ ( +- 0.03% )
1,162,575 cpu_core/cycles/ ( +- 0.29% )
73 page-faults ( +- 0.04% )
0.0014325 +- 0.0000177 seconds time elapsed ( +- 1.24% )
```
`list_sort` 的表現為
```
==== Testing list_sort ====
Comparisons: 5036
List is sorted
Performance counter stats for './sort_test' (1000 runs):
2,282 cpu_core/cache-misses/ ( +- 2.93% )
20,830 cpu_core/cache-references/ ( +- 0.39% )
1,705,274 cpu_core/instructions/ ( +- 0.03% )
1,092,431 cpu_core/cycles/ ( +- 0.33% )
73 page-faults ( +- 0.04% )
0.0011818 +- 0.0000218 seconds time elapsed ( +- 1.84% )
```
`q_sort` 的表現為
```
Performance counter stats for './qsort_test' (1000 runs):
3,955 cpu_core/cache-misses/ ( +- 1.64% )
23,143 cpu_core/cache-references/ ( +- 0.36% )
1,870,709 cpu_core/instructions/ ( +- 0.03% )
1,230,617 cpu_core/cycles/ ( +- 0.28% )
72 page-faults ( +- 0.05% )
0.0011824 +- 0.0000195 seconds time elapsed ( +- 1.65% )
```
#### 在 "`SAMPLES 1000`"、"資料集為 `random` " 的情況：
在這個情況中 `timsort, list_sort` 這兩個 `bottom up` 的 `merge sort` 演算法中， `cache-misses` 的差異不大，但 `q_sort` 的 `cache-misses` 相對來說就比較多。
`timsort` 的表現為
Comparisons 約在 (9000, 10000) 範圍區間
```
==== Testing tim_sort ====
Comparisons: 9474
List is sorted
Performance counter stats for './sort_test' (1000 runs):
3,148 cpu_core/cache-misses/ ( +- 2.17% )
21,937 cpu_core/cache-references/ ( +- 0.37% )
1,871,182 cpu_core/instructions/ ( +- 0.03% )
1,320,028 cpu_core/cycles/ ( +- 0.25% )
74 page-faults ( +- 0.04% )
0.0015920 +- 0.0000204 seconds time elapsed ( +- 1.28% )
```
`list_sort` 的表現為
Comparisons 約在 (8600, 8800) 範圍區間
```
==== Testing list_sort ====
Comparisons: 8725
List is sorted
Performance counter stats for './sort_test' (1000 runs):
3,195 cpu_core/cache-misses/ ( +- 2.27% )
22,494 cpu_core/cache-references/ ( +- 0.40% )
1,844,444 cpu_core/instructions/ ( +- 0.03% )
1,280,199 cpu_core/cycles/ ( +- 0.27% )
73 page-faults ( +- 0.04% )
0.0016114 +- 0.0000207 seconds time elapsed ( +- 1.29% )
```
`q_sort` 的表現為
```
Performance counter stats for './qsort_test' (1000 runs):
3,727 cpu_core/cache-misses/ ( +- 1.61% )
22,137 cpu_core/cache-references/ ( +- 0.40% )
1,957,399 cpu_core/instructions/ ( +- 0.03% )
1,258,764 cpu_core/cycles/ ( +- 0.26% )
74 page-faults ( +- 0.05% )
0.0015677 +- 0.0000200 seconds time elapsed ( +- 1.28% )
```
> commit [0caab3b](https://github.com/sysprog21/lab0-c/commit/0caab3bc0639cc22c5aea6cd0edf97f1fbd93e98)
:::warning
目前僅有二種資料集，能否針對 Timsort (及其變種演算法) 提出更通用的測試資料產生器？
:notes: jserv
:::
---
## 亂數 + 論文閱讀
### 在 qtest 提供新的命令 shuffle
利用 Fisher–Yates shuffle 演算法來實作洗牌（shuffle）
```
for i from n−1 down to 1 do
j ← random integer such that 0 ≤ j ≤ i
exchange a[j] and a[i]
```
## tic-tac-toe
### 蒙地卡羅搜尋 ( Monte Carlo tree search )
MCTS 為前段時間裡火紅的 AlphaGo 中使用的主體演算法，被廣泛運用在多個選擇中找出模擬過程中最為恰當的一個，像是 tic-tac-toe 、棋類競賽，更不同的甚至是自走車導航，都可以看見 MCTS 的身影。
而 MCTS 的評估過程，主要可以分為三個部分：
1. **select**
選擇下一步模擬的節點，而每一次的選擇都會透過 UCB 去計算出較適當的節點，此處為了讓選擇能夠同時兼顧不同路線的可能性以及最佳策略的準確性，也就是要同時有 `exploration` 與 `exploitation` ，最終的搜尋樹才有機會探索更多路徑且保持良好的效率。
$$
UCB = \cfrac{w_{i}}{n_{i}} \times C\sqrt{\cfrac{ ln(N_{i})}{n_{i}}}
$$
其中 ${w_{i}}$ 為經過此節點後獲勝的次數、${n_{i}}$ 為選擇該節點的總次數、$N_{i}$ 為該點的 `parent` 被選擇的總次數。
從 $UCB$ 可以看出，透過左項與右項的相互對抗，在選擇節點上就是在探索與偏好勝率較高這兩點做平衡。
2. **expand** **or** **rollout**
根據選擇到的節點，若該節點已被選擇過，則將進行 `expand` ，生成新的子節點以模擬更多樣的情況，若沒被選擇過，會進行 `rollout` ，也就是一直隨機進行選擇直至出現結果，這邊的過程其實也可以透過計算 $UCB$ 而看出何時會進行 `expand` 或 `rollout`。
3. **backpropagate**
當我們選擇到一個全新的節點時，將一直重複的 `rollout` 直到產出結果，而根據這個結果去更新所有經過節點的 ${n_{i}}$ 、 ${w_{i}}$ 即為 `backpropagate` ，一般來說若是分成 "勝利、平手、落敗" 的三種結果，會以 (-1, 0, 1) 去更新 ${w_{i}}$ 的數值。
最後，根據這三點去更新完搜尋樹之後，實際上在選擇下一步時，會去選擇 $win\_rate = \cfrac{w_{i}}{n_{i}}$ 最高者。
僅以 (1, 0) 去表示輸贏，且沒有平手的狀況，展示 MCTS 的圖像化過程 (C = $\sqrt{2}$)：
- [ ] initial
```graphviz
digraph Tree {
node [shape=circle];
A [label="0/0"]
B [label="0/0"]
C [label="0/0"]
A -> B;
A -> C;
}
```
- [ ] first select
```graphviz
digraph Tree {
node [shape=circle];
A [label="1/1" style=filled]
B [label="1/1" style=filled]
C [label="0/0"]
win [label="win!" color=transparent]
A -> B -> win;
A -> C;
}
```
- [ ] second select
```graphviz
digraph Tree {
node [shape=circle];
A [label="1/2" style=filled]
B [label="1/1"]
C [label="0/1" style=filled]
lose [label="lose!" color=transparent]
A -> B [label = 1];
A -> C [label = "inf"];
C -> lose
}
```
- [ ] third select
```graphviz
digraph Tree {
node [shape=circle];
A [label="2/3" style=filled]
B [label="2/2" style=filled]
C [label="0/1"]
D [label="1/1" style=filled]
E [label="0/0"]
win [label="win!" color=transparent]
A -> B [label = 2.177];
A -> C [label = 1.177];
B -> D -> win;
B -> E;
}
```
建立完蒙地卡羅搜尋樹後，將會去選擇 $win\_rate = \cfrac{w_{i}}{n_{i}}$ 最高者做為下一步，因此在在第一步，將選擇左邊節點。
觀察 MCTS 的模擬過程之後，我發現越遠的節點，因為 $UCB$ 中若節點未被選擇過，將會是無限大的關係，他被選擇的次數必然會較低，反之越接近 `root` 的節點將有較多種的可能性，這可能導致若 MCTS 的迭代次數過少，在樹的某一層 (第 n 次選擇節點) 後，將來的路線將有很大的侷限性，或許可以透過 $UCB$ 中 `exploration` 與 `exploitation` 的調整去做取捨。
:::warning
提出更系統的討論，解釋 MCTS 的局限和對運算的要求。
:::
### fixed_power_int 簡記
基本的功能可以拆解成兩部分，這個部分是為了檢測 $x^{2^n}$ 項是否為一，其中的 n 為次方樹，以 $x^5$ 為例， $n = 101_2$ ，因此在第一次、第三次的遞迴都會進入這個判定內。
```c
if (n & 1) {
result *= x;
result += 1UL << (frac_bits - 1);
result >>= frac_bits;
}
n >>= 1;
```
另一部分則是為了在檢查 $n$ 的每個二進位 `bits` 後，讓 $x$ 的次方項乘二，即為了配合 $n$ 的二進位表示方式， $n = 101_2 = 1 \cdot 2^0 + 0 \cdot 2^1 + 1 \cdot 2^2$ ，
舉例來說在檢查 $n$ 的第一個 bits 時， $x$ 相對應的就是 ${x^2}^0$ ，檢查第三個 bits 的時候 $x$ 相對應的就是 ${x^2}^2 = x^4$ ，這邊在做的就是更新 $x$ 的次方。
```c
x *= x;
x += 1UL << (frac_bits - 1);
x >>= frac_bits;
```
這裡有一個疑惑是為何在每次的乘法過後都要進行無條件進位，這樣的做法與我做無條件捨去在精度上會有很大的差異嗎。
:::warning
上面的推理已有答案，你應該自行計算。
:notes: jserv
:::
### 定點數 log2 計算
> 參考 [Shawn531](https://hackmd.io/@Shawn531/linux2024-homework1#%E5%AE%9A%E9%BB%9E%E6%95%B8)
為了計算 $log_2(x)$ ，首先以二進位科學記號的方式將 $x$ 的冪次與剩餘部分分離為 ${x_m} , x_n$ ，若 $x = 11$ ，則分離為 $2^3 * 1.375$ 在取 log2 時 $2^3$ 將不納入計算中，且 $y_m = 3$ ，此處即對應到 "log2_fix" 中的：
```c
while (x < 1U << precision) {
x <<= 1;
y -= 1U << precision;
}
while (x >= 2U << precision) {
x >>= 1;
y += 1U << precision;
}
```
前處理後，設定
$$
y_n =log_2(x_n) $$ $$x_n=2^{y_n}
$$
因 $1\leq x_n\leq 2$， $0\leq y_n\leq 1$，$y_n$ 的值將可以表示為:
$$
y=y_1\cdot 2^{-1} + y_2\cdot 2^{-2}+y_3\cdot 2^{-3}+y_4\cdot 2^{-4}+...
$$
整理過後
$$
y = 2^{-1}(y_1+2^{-1}(y_2+2^{-1}(y_3+2^{-1}(y_4+...))))
$$
將 $y_n$ 帶入 $x_n=2^{y_n}$
$$
x = 2^{2^{-1}(y_1+2^{-1}(y_2+2^{-1}(y_3+2^{-1}(y_4+...))))}
$$
為了求得 $y_n$ 之近似值，將兩側平方
$$
x^2 = 2^{y_1}\cdot2^{2^{-1}(y_2+2^{-1}(y_3+2^{-1}(y_4+...)))}
$$
且這裡已知 ${2^{-1}(y_2+2^{-1}(y_3+2^{-1}(y_4+...)))}$ 必小於 1，即 $1 \leq 2^{2^{-1}(y_2+2^{-1}(y_3+2^{-1}(y_4+...)))} \leq 2$ ，因此可以透過 $x^2$ 是否大於 2 來判斷 $y_n$ 部分第一項 $y_1$ 是否為 0。
為以下兩種情況：
$x^2 \le 2 , y_1 = 1$ or $x^2 > 2 , y_1 = 0$
完成後，將 $x'$ 設定為 $\cfrac{x^2}2$ ，如此是為了繼續執行
$$
x' = 2^{2^{-1}(y_2+2^{-1}(y_3+2^{-1}(y_4+...)))}
$$
進行多次逼近後，即可得 $y_n$ 各個位數的值，已求得完整的 $y = y_m.y_n$ ，即程式碼中這一部分：
```c
for (size_t i = 0; i < precision; i++) {
z = z * z >> precision;
if (z >= 2U << precision) {
z >>= 1;
y += b;
}
b >>= 1;
}
```
此處的 `z` 即 $x^2$ ，並在每次的迭代後 `z >>= 1` 即將下一次的 $x'$ 設定為 $\cfrac{x^2}2$ ，而 `b` 則為更新目前的 $y_n$ ，在這裡是直接在本體 $y$ 進行運算，沒有分離成 $y = y_m.y_n$。
#### 在不同精度下，與原本浮點數運算的 $log_2$ 比較圖：
可以看到在 `fraction bit` 大於 8 之後，基本上與浮點數在精度的差距就不會到太大。
> commit [71d0120](https://github.com/sysprog21/lab0-c/commit/71d0120c98e3812613e4c6cf9923be9d1d9d70d1)
:::warning
TODO: ttt 的引入，定點數與浮點數運算的效能分析、log2_lshift16 之改進。
:::
Sign in with Wallet
Connect another wallet