# 2025q1 Homework2 (quiz1+2)
> contributed by < Potassium-chromate >
## 第一周
### 測驗一
#### 程式碼運作原理
`list_insert_before` 的具體用途為將 `item` 插入到 `before` 前面。具體方式為持續遍歷鍊結串列直到遇到 `before` ，接著把 `before` 前一個節點的 `next` 指向 `item`。
```c
static inline void list_insert_before(list_t *l,
list_item_t *before,
list_item_t *item)
{
list_item_t **p;
for (p = &l->head; *p != before; p = &(*p)->next)
;
*p = item;
item->next = before;
}
```
#### 合併排序操作
本次實作為 Top-Down 的方式，其中尋找中間節點的作法為利用快慢指標 (slow and fast pointers)。
1. 尋找中間節點 - `get_middle()`
在 `get_middle()` 函數中，我們使用快慢指標 (slow and fast pointers) 來找到鏈結串列的中間節點：
- `slow` 指標每次移動一步。
- `fast` 指標每次移動兩步。
- 當 `fast` 到達鏈結串列的末端時，`slow` 剛好位於中間位置。
2. 合併兩個已排序的鏈結串列 - `merge()`
其實做方式為利用遞迴函數來合併兩個已排序的鏈結串列，並返回排序後的新鏈結串列的第一個節點。
- 若 `left` 的值較小，則 `left->next` 指向遞迴合併後的結果，返回 `left`。
- 若 `right` 的值較小，則 `right->next` 指向遞迴合併後的結果，返回 `right`。3
```c
static inline list_item_t *merge(list_item_t *left, list_item_t *right) {
if (!left) return right;
if (!right) return left;
if (left->value <= right->value) {
left->next = merge(left->next, right);
return left;
} else {
right->next = merge(left, right->next);
return right;
}
}
```
3. 實作 Merge Sort - `merge_sort()`
本次是以遞迴式的方式來實做 Merge Sort 主函數：
- 當 `head` 為空或僅有一個節點時，直接返回 `head`。
- 使用 `get_middle()` 找到中間節點。
- 將鏈結串列分成兩部分，並遞迴地對左右兩部分進行 Merge Sort。
- 使用 `merge()` 合併已排序的左右兩部分，並返回排序後的鏈結串列頭部。
```c
list_item_t* middle = get_middle(head);
list_item_t* next_to_middle = middle->next;
middle->next = NULL;
list_item_t* left = merge_sort(head);
list_item_t* right = merge_sort(next_to_middle);
```
### 測驗二
#### 程式碼運作原理
由於目的是要找到左子樹的最右節點，因此需要持續遍歷 `(*pred_ptr)->r` 直到遇到 `NULL`。因此 `EEEE` 為 `(*pred_ptr)->r`， `FFFF` 為 `(*pred_ptr)->r`。
```c
while ((*pred_ptr)->r) // EEEE
*pred_ptr = (*pred_ptr)->r; // FFFF
```
其刪除節點的邏輯如下：
**情況 1：節點有兩個子節點**
- 需找到該節點 **左子樹中最大值的節點（前驅節點，Predecessor）** 來替換它。
- 若前驅節點為該節點的左子節點，可直接用它來替換目標節點。
- 若前驅節點位於左子樹深處，則需先移除前驅節點，並妥善接回其左子樹，最後才用前驅節點替換目標節點。
具體過程如下：
**步驟 1：尋找前驅節點**
- 50 的左子樹存在最大值節點 40（即前驅節點）。
```
50
/ \
30 70
/ \ / \
10 40 60 80
/
35
```
**步驟 2：移除 40，並將其左子節點 35 接回**
- 由於 40 尚有左子節點 35，若直接用 40 替換 50，則 35 可能會丟失，因此須先將 40 替換為 35。
```
50
/ \
30 70
/ \ / \
10 35 60 80
```
**步驟 3：使用 40 替換 50**
- 最後，將 40 取代 50 的位置，並保留其原本的左右子樹結構。
```
40
/ \
30 70
/ \ / \
10 35 60 80
```
**情況 2：節點只有一個子節點**
- 如果該節點有一個子節點，我們用其子節點取代目標節點。
以下為用 graviz 視覺化刪除過程的範例：
移除節點 654
移除節點 284
程式碼細節可以參考 [Commit 3c697d6](https://github.com/Potassium-chromate/2025_lab_1/commit/3c697d63c50080025e6eb3aecdf6ea572d74294f)
#### 參閱 memory-allocators
參考 [memory-allocators](https://github.com/mtrebi/memory-allocators)，可以得知 allocators 分為以下四種：
**1. Linear Allocator:**
- **記憶體管理策略**
- 以連續區塊的方式管理記憶體的最簡單的分配器。
- 透過增加指標（bump pointer）來線性分配記憶體
- 不允許釋放特定位置，只能一次釋放全部記憶體。
- **工作原理**
- 將一個指標保留在記憶體區塊的第一個記憶體位址上開始。
- 每次分配都會使指針向前移動來表示最後分配的位置。
**2. Stack Allocator**
- **記憶體管理策略**
- 工作方式類似於**堆疊資料結構（LIFO—後進先出）**。
- 分配從堆疊頂部進行。
- 釋放必須按照分配的相反順序進行。
- **工作原理**
- 堆疊指標追蹤分配記憶體的頂部。
- 每次新的分配都會將指針向堆的頂端。
- 僅允許最近的分配的記憶體進行釋放。
**3. Pool Allocator**
- **記憶體管理策略**
- 管理固定大小的記憶體區塊。
- 使用鍊結串列來追蹤可用的區塊。
- **工作原理**
- 預先分配一大塊內存，並將其分成固定大小的區塊。
- 維護一個儲存空閒區塊的鍊結串列。
- 每當請求新的記憶體空間時，就會從空閒區塊的鍊結串列分配一塊出來。
- **實做方式**
以下為[memory-allocators](https://github.com/mtrebi/memory-allocators) 的實做方式。
**1. 初始化 - 分配一個大記憶體區域**
```cpp
void PoolAllocator::Init() {
m_start_ptr = malloc(m_totalSize);
this->Reset();
}
```
**2. 建立自由列表 - 初始化可用區塊**
```cpp
void PoolAllocator::Reset() {
m_used = 0;
m_peak = 0;
// Create a linked-list with all free positions
const int nChunks = m_totalSize / m_chunkSize;
for (int i = 0; i < nChunks; ++i) {
std::size_t address = (std::size_t) m_start_ptr + i * m_chunkSize;
m_freeList.push((Node *) address);
}
}
```
**4. Free list allocator**
- **記憶體管理策略**
- 有兩種常見的實作：一種使用連結列表，一種使用紅黑樹。
- 當請求分配時，它會在連結列表中搜尋可以容納資料的區塊。
- 它從鍊結串列(或是紅黑數)中刪除元素，並在資料之前放置一個 allocation header 以紀錄該區塊的大小。
- 在鍊結串列(或是紅黑數)中也會持續合併連續的記憶體區塊以創建更大的區塊。
- **工作原理**
- 預先以鍊結串列(或是紅黑數)來儲存記憶體中每個空閒連續區塊的起始位址及其大小
- 在紅黑數的結構中，可以將複雜度降低到$O(log(N))$
#### 效能評比
在作業提供的資料結構中，二元搜尋樹 (BST) **沒有自平衡機制**，這可能導致插入與刪除節點時出現樹的高度不均問題，影響搜尋與操作效率。
因此，我本次實作紅黑樹 (Red-Black Tree, RBT)，並比較：
1. **BST vs. RBT** 在插入的效能
2. **BST vs. RBT** 在刪除的效能
參考 [Linux 核心的紅黑樹](https://hackmd.io/@sysprog/linux-rbtree#Insert-%E5%AF%A6%E4%BD%9C)，可以得知紅黑數的基本性質為：
1. 每個節點都是紅色或黑色。
2. 根節點必為黑色。
3. 紅色節點的子節點必為黑色，即不能有連續的紅色節點。
4. 從根節點到所有葉節點的黑色節點數相同。
5. 新插入的節點預設為紅色，並透過 **旋轉** 與 **顏色調整** 來維持紅黑樹性質。
紅黑數的實做細節可以參考 [Commit 50e822e
](https://github.com/Potassium-chromate/2025_lab_1/commit/50e822ebcb965aa358d86e6b12e7cce5da88e608)
下圖是隨機插入 1 到 30 的結果並使用 Graphviz 視覺化的結果：
```graphviz
digraph G {
subgraph red {
node [color="red", style="filled", group="red"]
21
28
25
24
22
17
20
18
16
14
11
9
5
7
2
0
}
subgraph black {
node [color="black", style="filled", group="black", fontcolor="white"]
8
27
29
26
23
13
19
15
12
10
3
6
4
1
}
8->21
21->27
27->29
29->28
27->25
25->26
25->23
23->24
23->22
21->13
13->17
17->19
19->20
19->18
17->15
15->16
15->14
13->11
11->12
11->10
10->9
8->3
3->5
5->6
6->7
5->4
3->1
1->2
1->0
}
```
刪除 10 個節點 **(13, 16, 24, 11, 25, 27, 10, 12, 19, 21)** 後，結果如下：
```graphviz
digraph G {
subgraph red {
node [color="red", style="filled", group="red"]
22
26
17
18
5
7
2
0
}
subgraph black {
node [color="black", style="filled", group="black", fontcolor="white"]
8
28
29
23
14
20
15
9
3
6
4
1
}
8->22
22->28
28->29
28->26
26->23
22->14
14->17
17->20
20->18
17->15
14->9
8->3
3->5
5->6
6->7
5->4
3->1
1->2
1->0
}
```
下方為 RBT 與 BST 於插入 3000 個節點與 刪除 1500 節點的時間：
測量方式為使用 Linux 內建效能分析工具： **Perf**。
紅黑數：
```c
eason@eason-System-Product-Name:~/2025_lab_1/memory_allocators$ sudo perf stat -r 100 ./RBtree
Performance counter stats for './RBtree' (100 runs):
16.65 msec task-clock # 0.987 CPUs utilized ( +- 0.99% )
0 context-switches # 0.000 /sec
0 cpu-migrations # 0.000 /sec
91 page-faults # 5.466 K/sec ( +- 0.09% )
<not counted> cpu_atom/cycles/ ( +-100.00% ) (0.00%)
6743,6385 cpu_core/cycles/ # 4.050 GHz ( +- 0.29% )
<not counted> cpu_atom/instructions/ ( +-100.00% ) (0.00%)
9391,3135 cpu_core/instructions/ # 128.96 insn per cycle ( +- 0.01% )
<not counted> cpu_atom/branches/ ( +-100.00% ) (0.00%)
2030,7443 cpu_core/branches/ # 1.220 G/sec ( +- 0.01% )
<not counted> cpu_atom/branch-misses/ ( +-100.02% ) (0.00%)
7,8665 cpu_core/branch-misses/ # 37.70% of all branches ( +- 0.16% )
TopdownL1 (cpu_core) # 65.4 % tma_backend_bound
# 2.0 % tma_bad_speculation
# 3.2 % tma_frontend_bound
# 29.4 % tma_retiring ( +- 0.29% )
0.016874 +- 0.000169 seconds time elapsed ( +- 1.00% )
```
二元搜尋樹：
```c
eason@eason-System-Product-Name:~/2025_lab_1/memory_allocators$ sudo perf stat -r 100 ./BST
Performance counter stats for './BST' (100 runs):
58.54 msec task-clock # 0.995 CPUs utilized ( +- 0.49% )
0 context-switches # 0.000 /sec
0 cpu-migrations # 0.000 /sec
106 page-faults # 1.811 K/sec ( +- 0.06% )
<not counted> cpu_atom/cycles/ ( +- 32.80% ) (0.00%)
2,5534,4994 cpu_core/cycles/ # 4.362 GHz ( +- 0.28% )
<not counted> cpu_atom/instructions/ ( +- 32.91% ) (0.00%)
5,2419,1360 cpu_core/instructions/ # 29.97 insn per cycle ( +- 0.11% )
<not counted> cpu_atom/branches/ ( +- 32.96% ) (0.00%)
1,0172,8554 cpu_core/branches/ # 1.738 G/sec ( +- 0.10% )
<not counted> cpu_atom/branch-misses/ ( +- 34.71% ) (0.00%)
79,0093 cpu_core/branch-misses/ # 14.99% of all branches ( +- 1.56% )
TopdownL1 (cpu_core) # 23.0 % tma_backend_bound
# 10.0 % tma_bad_speculation
# 29.5 % tma_frontend_bound
# 37.6 % tma_retiring ( +- 0.30% )
0.058839 +- 0.000291 seconds time elapsed ( +- 0.49% )
```
可以發現 RBT 快了 BST 約 4 倍。並且理論上 BST 的刪除節點的時間複雜度為$O(n)$， BRT 刪除節點的時間複雜度為$O(lon(n))$
:::warning
TODO: 比較在不同數量節點的情況下，**BST** 與 **RBT** 的效能表現。
:::
### 測驗三
#### 程式碼運作原理
判斷式 `L != R` 代表當左右兩邊的linked list頭尾不相等時，表示該linked list不只包含一個節點；而在 `else` 內，則代表該linked list只剩一個節點，此時可以直接將該節點插入最終的要回傳linked list。
然後，還可以發現在`else`中會將`i`減1，再搭配上面提到的部分。可以發現當`right`只剩一個節點並執行`i--`後，`begin[i]`就會退回pivot，然而pivot必定只有一個節點，因此又會再做一次`i--`，然後`begin[i]`又會退回`left`的部分，最後便可以持續分割原本的`left`並對其做排序。
```c
while (i >= 0) {
node_t *L = begin[i], *R = end[i];
if (L != R) {
...
i += 2;
} else {
if (L)
list_add(&result, L);
i--;
}
}
```
最後，我們可以用Graphviz來觀察一下quick_sort中`right`, `left`與`pivot`的變化。
這是最一開始的狀態。共10個節點。
一開始一定是取第一個節點作為pivot，也就是`8`。因此我們可以發現`right`, `left`與`pivot`會變成以下狀態。
之後，`9`和`8`就會被併入最終的要回傳linked list。
之後再對原本的那條left做排序即可。可以發現，==整結構其實就是一個stack==。
實做細節可以參考 [Commit c9912d7](https://github.com/Potassium-chromate/2025_lab_1/commit/c9912d759f9440c24cb9c03a571c6b7183502a4f)
#### 研讀論文
>For quick sort, Hoare's original algorithm [3] cannot
be used since this algorithm "bums a candle from
both ends".
在論文中，對於在雙向鍊結串列上使用 Hoare's 快速排序的主要擔憂是，霍爾原始的分區演算法 "bums a candle from both ends" ，同時從前面和後面進行遍歷。雖然這在陣列上很簡單（透過索引隨機存取很容易），但在鍊錶上卻很麻煩，特別是在單向的鍊結串列上。
>However, since quick sort is not stable (Sedgewick
[6]), it is not included. Instead, an algorithm which
was originally designed to make quick sort stable
and to handle equal keys is selected for this study.
This algorithm was first proposed by Motzkin [5]
and then analyzed by Wegner [7].
隨後論文指出了第二個缺點：傳統的快速排序不穩定，這代表具有相同鍵值的節點在排序後可能不會保持其原始順序。由於這種不穩定性，作者選擇放棄傳統的快速排序，而採用一種變體（由 Motzkin 提出並由 Wegner 分析），結合以上兩點，就成為作業利用堆疊來實做快速排序演算法的方式。
## 第二周
### 測驗一
#### 程式碼運作原理
首先來看 getnum 函式，其實作上是利用了 線性同餘生成器（Linear Congruential Generator, LCG） 的原理來產生偽隨機數。
> 參考： [Linear congruential generator – Wikipedia](https://en.wikipedia.org/wiki/Linear_congruential_generator)
LCG 的基本公式如下：
$N_{j+i}=(A\times N_j+B)\ mod\ m$
其中 $A$,$B$ 為常數，且 $B$ 與 $M$ 必須互質。這種方式能有效產生統計上看似隨機的數字，但因為內部狀態容易從輸出推導，因此它屬於偽隨機數產生器（PRNG）。
```c
static inline uint8_t getnum(void)
{
static uint16_t s1 = UINT16_C(2);
static uint16_t s2 = UINT16_C(1);
static uint16_t s3 = UINT16_C(1);
s1 *= UINT16_C(171);
s1 %= UINT16_C(30269);
s2 *= UINT16_C(172);
s2 %= UINT16_C(30307);
s3 *= UINT16_C(170);
s3 %= UINT16_C(30323);
return s1 ^ s2 ^ s3;
}
```
- 使用了三個不同參數的 LCG (`s1`, `s2`, `s3`)。
- 每次呼叫 `getnum()` 時，這三個狀態會根據各自的乘數與模數進行更新。
- 因為變數是 `static`，它們只在第一次呼叫時初始化，之後會保留上次的狀態，形成一個持續變化的序列。
- 最後透過 XOR (`^`) 結合三個數值，以增加隨機性與分佈品質。
```c
static inline void random_shuffle_array(uint16_t *operations, uint16_t len)
{
for (uint16_t i = 0; i < len; i++) {
/* WARNING biased shuffling */
uint16_t j = get_unsigned16() % (i + 1);
operations[i] = operations[j];
operations[j] = i;
}
}
```
可以發現以上程式碼有以下問題：
1. **無效洗牌**
- 當 `i==j` 時，可能會造成無效的洗牌。
2. **偏向分佈**
- 使用 `% (i + 1)` 可能會產生模數偏差，除非 `get_unsigned16()` 能均勻的生成 `1` ~ `i+1` 的變數。
**改進 `random_shuffle_array`:**
可以採用 **Fisher-Yates Shuffle** 的方式來洗牌，如下:
```c
#include <stdint.h>
#include <stdlib.h>
static inline void random_shuffle_array(uint16_t *operations, uint16_t len)
{
for (uint16_t i = len - 1; i > 0; i--) {
uint16_t j = rand() % (i + 1);
// Swap operations[i] and operations[j]
uint16_t temp = operations[i];
operations[i] = operations[j];
operations[j] = temp;
}
}
```
並且以熵的方式來衡量兩個洗牌算法之間的亂度：
| length of array | Original | Fisher Yate | Ideal entropy |
| -------- | -------- | -------- | -------- |
| 7 | 12.2954 | 12.2956 | 12.2922 |
| 8 | 15.2696 | 15.2700 | 15.2992 |
| 9 | 18.1794 | 18.1802 | 18.4691 |
可以發現 Fisher-Yates Shuffle 的效果其實比原本的演算法略好一點。
詳細的 python 腳本實做可以參考：[Commit bf5b69f
](https://github.com/Potassium-chromate/2025_lab_1/commit/bf5b69f6c661fbb111dc9a825496d3df353f2be0)
#### 為何將 `list_move_tail` 換為 `list_move`，會無法滿足 stable sorting?
當兩個元素具有相同的值時相當於 `cmpint() == 0`，`item->list` 會被放入 `list_greaterelse` 中。
- 如果使用 `list_move_tail()`，則兩個節點中的第一個會更早出現在 `list_greater`，從而保持順序。
- 如果我們使用 `list_move()`，則第二個節點反而會被插入到前面，這會反轉相等鍵值節點的原始順序。
#### 整合進 lab0-c
目前已經將命令整合進，qtest 中並且可以透過命令 `quicksort` 來執行排序。
```shell
eason@eason-System-Product-Name:~/lab0-c$ ./qtest
cmd> new
l = []
cmd> ih qwer
l = [qwer]
cmd> ih asd
l = [asd qwer]
cmd> ih ergk
l = [ergk asd qwer]
cmd> ih epoqwr
l = [epoqwr ergk asd qwer]
cmd> ih jua
l = [jua epoqwr ergk asd qwer]
cmd> quicksort
l = [asd epoqwr ergk qwer jua]
```
細節可以參考： [Commit f6de623
](https://github.com/Potassium-chromate/lab0-c/commit/f6de623cc33a32ca5ea873f74d6ac2cbe2b008f1)
#### 效能比較
### 測驗二
#### 程式碼解釋
從題目敘述來看，已知$N^2=a^{2}_{n}+[2P_n+a_{n-1}]a_{n-1}+[2P_{n-1}+a_{n-2}]a_{n-2}+...+[2P_1+a_0]a_0$
並且$P_m=a_n+...a_m$
例如: $P_1=a_n+...+a_1$
令$X_m=N^2-P_m^2$
$\rightarrow X_{m+1}=N^2-P_{m+1}^2$
又$P_{m+1}+a_m=P_m$
$\rightarrow X_{m}=N^2-P_{m+1}^2-(2P_{m+1}a_m+a_m^2)=X_{m+1}-(2P_{m+1}a_m+a_m^2)$
接下來，把$2P_{m+1}a_m+a_m^2$寫成$c_m + d_m$:
- $c_m=\{^{P_{m+1}2^{m+1}, a^m=2^m}_{0, a^m=0}$
- $d_m=a_m^2$
接著繼續往後推導:
$c_{m-1}+d_{m-1}=2P_{m}a_{m-1}+a_{m-1}^2$
- $c_{m-1}=P_m2^m=(P_{m+1}+a_m)2^m=P_{m+1}2^m+a_m2^m$
$$=
\begin{cases}
\frac{c_m}{2}+d_m,\ if\ \ a_m=2^m\\
P_{m+1}2^m,\ \ \ \ \ \ \ \ \ \ if\ \ a_m=0\\
\end{cases}
$$
- $d_{m-1}=\frac{d_m}{4}$
最後整理一下，$c_m+d_m=X_{m+1}-X_{m}=P_m^2-P^2_{m-1}$。
可以發現程式中的$d_m$就是`m`，$c_m$就是`z`，`b`對應的就是$P_m^2-P^2_{m-1}$
將上述的數學過程寫成程式碼後，如下：
```c
while (m) {
uint64_t b = y + m;
y >>= 1;
if (x >= b) {
x -= b;
y += m;
}
m >>= 2;
}
```
完整實做可以參考：[Commit d8aa128](https://github.com/Potassium-chromate/2025_lab_1/commit/d8aa1289c26abbb5b3a85623a6993c3b008360ad)
#### $\lceil \sqrt x \rceil$ 實做
參考 [從 √2 的存在談開平方根的快速運算](https://hackmd.io/@sysprog/sqrt#Digit-by-digit-Method) ，可以得知 $X_m=N^2-P^2_m$ 為差值表實際值與逼近值的誤差，所以當 $X$ 為完全平方數時， $X_m=0$。
完整實做可以參考：[Commit a061147](https://github.com/Potassium-chromate/2025_lab_1/commit/a061147b71f6b06628da6471eacc3856b8352673)
#### 不依賴除法指令的 `sqrtf`
參考 [反平方根快速演算法](https://zh.wikipedia.org/zh-tw/%E5%B9%B3%E6%96%B9%E6%A0%B9%E5%80%92%E6%95%B0%E9%80%9F%E7%AE%97%E6%B3%95)，可以得知其中的 **magic number** 是用於調整浮點數的指數項，來初步估算結果，最後再藉由 [牛頓法](https://zh.wikipedia.org/zh-tw/%E7%89%9B%E9%A1%BF%E6%B3%95) 來迭代出更精確的結果。所以我們可以先藉由藉由 [反平方根快速演算法](https://zh.wikipedia.org/zh-tw/%E5%B9%B3%E6%96%B9%E6%A0%B9%E5%80%92%E6%95%B0%E9%80%9F%E7%AE%97%E6%B3%95) 得到 $\frac{1}{\sqrt{x}}$，之後再利用 `0x7F000000` 作為其 **magic number** 來調整其指數項來初步估計結果值。最後，透過 [牛頓法](https://zh.wikipedia.org/zh-tw/%E7%89%9B%E9%A1%BF%E6%B3%95) 迭代即可得到較為精確的 $\sqrt{x}$。
具體的實作方式如下，其中影響結果精度的因素有兩項:
1. 計算平方根倒數的迭代次數
2. 計算倒數的迭代次數
```c
float Q_rsqrt(float number)
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y; // evil floating point bit level hacking
i = 0x5f3759df - ( i >> 1 ); // what the fuck?
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
return y;
}
float Q_sqrt(float number)
{
float rsqrt = Q_rsqrt(number);
float y = rsqrt;
int i = * ( int * ) &y;
i = 0x7F000000 - i; // Do the reciprocal to the exponent
y = * ( float * ) &i; // Convert the extimate value back to float
y = y * (2 - rsqrt * y);
return y;
}
```
下圖為 **平方根倒數的迭代==2==次** 與 **倒數的迭代==1==次** 的結果
下圖為 **平方根倒數的迭代==2==次** 與 **倒數的迭代==2==次** 的結果
下圖為 **平方根倒數的迭代==2==次** 與 **倒數的迭代==3==次** 的結果
從上圖的結果可以發現，**平方根倒數的迭代==2==次** 與 **倒數的迭代==3==次** 的結果是較為精確的。
具體實作細節可以參考 [Commit 61711be
](https://github.com/Potassium-chromate/2025_lab_1/commit/61711be3ad044722a7366793238c18da4310cbe2)
#### 比較不同手法的整數開平方根效能
以下是使用二分搜尋法來尋找平方根的實作，先將指數除以二以得到粗略的估計值 `i`。最後再將精確值限縮在 `i` 到 `2*i` 之間，搭配二分搜尋法即可找到精確值。
```c
int32_t Bi_sqrt(int n)
{
float y = n;
int32_t i = * ( int32_t * ) &y;
//printf("Before i: %x\n", i);
i >>= 23; // Do the reciprocal to the exponent
i = ((i - 127) >> 1) + 127; // Deivde the exponent by 2
i <<= 23;
//printf("After i: %x\n", i);
y = * ( float * ) &i;
i = (int32_t) y;
// Do the binary search to estimate value;
unsigned int head = i; // 2^i
unsigned int tail = (i + 1) << 1; // 2^(i+1)
unsigned int mid = (head + tail) >> 1; // same as (2^m + 2^(m+1)) / 2
while (1) {
if (n > (mid + 1) * (mid + 1)) {
head = mid;
mid = (head + tail) >> 1;
} else if (n < mid * mid) {
tail = mid;
mid = (head + tail) >> 1;
} else
break;
}
return mid;
}
```
完整實作細節可以參考: [Commit 2a318a8](https://github.com/Potassium-chromate/2025_lab_1/commit/2a318a8b51a67d2b8a98cf2c45cdced23887ef2f)
下圖為使用**二分搜尋法**與**作業提供**兩種演算法的效能表現。其原因是因為現代 CPU 都有將浮點數轉成整數的硬體。所以可以節省掉很大量的時間。並且二分法的迭代次數也比作業提供次數少。
### 測驗三
#### Theorem S
參考維基百科上關於 [Three-gap theorem](https://en.wikipedia.org/wiki/Three-gap_theorem) 的說明：
>The three-gap theorem can be stated geometrically in terms of points on a circle. In this form, it states that if one places $n$ points on a circle, at angles of $\theta,2\theta,\dots,n\theta$ from the starting point, then there will be at most three distinct distances between pairs of points in adjacent positions around the circle.
可以藉由下方的實驗來更直觀的了解。
以下是累加 **golden ratio** 10次的結果。
```=
0.6180339887498949
1.2360679774997898
1.8541019662496847
2.4721359549995796
3.0901699437494745
3.7082039324993694
4.326237921249264
4.944271909999159
5.562305898749054
6.180339887498949
```
再將上述的結果對 1 取模。相當於將 10 個點放置在同一個圓上。
```=
0.6180339887498949
0.2360679774997898
0.8541019662496847
0.4721359549995796
0.09016994374947451
0.7082039324993694
0.3262379212492643
0.9442719099991592
0.5623058987490541
0.18033988749894903
```
接著將各點由小到大排序，並計算各點的距離。可以發現其中只有三種距離: `0.090`, `0.055` 與 `0.145`。
```=
0.09016994374947451
0.05572809000084078
0.09016994374947451
0.1458980337503153
0.09016994374947451
0.05572809000084078
0.09016994374947451
0.1458980337503153
0.09016994374947451
```
了解了以上現象後，我們可以發現如果點間的距離很均勻，則各個 **bucket** 不會出現過度擁擠或是空閒的情況。
以下是 $\frac{\sqrt5-1}{2}$
以下是 $\frac{\sqrt6-1}{2}$
可以發現，$\frac{\sqrt{5}-1}{2}$的分佈較為均勻，`0.005` - `0.008` - `0.013`，間隔為 `0.003` 與 `0.005`。
而$\frac{\sqrt{6}-1}{2}$的間隔為 `0.025` 與 `0.008` 較不均勻。
#### Linux 核心中使用 hash table 的應用案例
Sign in with Wallet
Connect another wallet