2025q1 Homework2 (quiz1+2)

contributed by < CodeStone1125 >

作業書寫規範:

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
避免使用不必要的 emoji 字元

開發環境

$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0

$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   46 bits physical, 48 bits virtual
CPU(s):                          28
On-line CPU(s) list:             0-27
Thread(s) per core:              2
Core(s) per socket:              20
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           183
Model name:                      Intel(R) Core(TM) i7-14700 ＠ 1.50 GHz
Stepping:                        1
CPU MHz:                         1100.3190
CPU max MHz:                     5400.0000
CPU min MHz:                     800.0000
BogoMIPS:                        4224.00  
Virtualization:                  VT-x
L1d cache:                       768 KiB
L1i cache:                       1 MiB
L2 cache:                        28 MiB
L3 cache:                        33 MiB 
NUMA node0 CPU(s):               0-27

Quiz 1-1

單向鏈結串列

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

digraph foo {
	rankdir=LR;
	node [shape=record];
	a [shape=none, label="list_t"] 
	b [label="<name> list_item_t |{ <data> 99 | <ref> }"];
	c [label="<name> list_item_t |{ <data> 37 | <ref>  }"];
	d [shape=none, label="NULL"];
	a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both,  arrowsize=1.2];
	b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
	c:ref:c -> d      [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}

研讀完成程式碼和示意圖得知這題屬於單向鏈結串列的插入，因此和 lab0-c/queue.c 最主要的差別是不用管理 prev 指標也沒有 circular。

assert

研讀測試程式碼時我發現 my_assert 使用 do{...} while(0) 但明明只執行一次，所以我特別針對這部分蒐集了一些資料：

my_assert 為何使用 do{...} while(0)

先講結論，#define assert 即使時執行一次卻使用 do{...} while(0) 是因為強制該區塊始終作為單一語句即使是在多行程式碼的情況下，並且希望可以把宏定義的用法和一般函式一致。

以 my_assert 使用 do{...} while(0)舉例：

#define my_assert(test, message) \
    do {                         \
        if (!(test))             \
            return message;      \
    } while (0)

以及如果定義 my_assert 不使用 do{...} while(0)：

#define my_assert(test, message) if (!(test)) return message;

my_assert 在測試程式展開後，會出現 x 在 0~10 的區間無法正確顯示 x is non-positive。：

#define my_assert(test, message) if (!(test)) return message;

const char* check_value(int x) {
    if (x > 0)
-        my_assert(x > 10, "x is too small");
+        if (!(x > 10)) return "x is too small";  // <-- 這個 if 來自 my_assert macro
    else
        printf("x is non-positive\n");  // <-- 這個 else 與 my_assert 內的 if 錯誤匹配
    return "OK";
}

原因是基於 C99 6.8.4.1p3 中敘述 else 會最近的 if 配對，因此 my_assert 導致 if-else 區塊判斷錯誤:

An else is associated with the lexically nearest preceding if that > is allowed by the
syntax. [C99 6.8.4.1p3]

my_assert 為何不使用 {...}

使用 {...} 在上述例子中可以解決 if-else 問題但處理包含多行語句的情況會有額外的操作，以下假設 my_assert 變成多行語句：

define my_assert(test, message) \
    {                            \
        if (!(test))             \
            return message;      \
+        printf("ok");             \
    }

你在使用宏定義時就必需省略 ; 而無法像一般的函式一樣呼叫：

const char* check_value(int x) {
    if (x > 0)
-        my_assert(x > 10, "x is too small");
+        my_assert(x > 10, "x is too small")
    else
        printf("x is non-positive\n");  // <-- 這個 else 與 my_assert 內的 if 錯誤匹配
    return "OK";
}

以上討論偏向語法正確性方面並且提供 C99 的出處，還有更多關於程式品味的原因可見參考資料。

參考資料：

Why use do { } while (0) in macro definition? [duplicate]

list_insert_before

#include <stddef.h>
typedef struct list_item {
    int value;
    struct list_item *next;
} list_item_t;

typedef struct {
    struct list_item *head;
} list_t;

資料結構如下:

list_t	list_item_t
Image Not Showing Possible Reasons The image was uploaded to a note which you don't have access to The note which the image was originally uploaded to has been deleted Learn More →	Image Not Showing Possible Reasons The image was uploaded to a note which you don't have access to The note which the image was originally uploaded to has been deleted Learn More →

測試程式如下：

for (size_t i = 0; i < N; i++)
    list_insert_before(&l, l.head, &items[i]);

將所有的 list_reset 初始化的節點利用 list_insert_before 插入鏈結串列最後用 my_assert 確認鏈結串列長度正確，因此插入會面對兩種情況：

空鏈結串列
非空鏈結串列
Image Not Showing Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →

以下是list_insert_before 要求操作：

根據要求 list_insert_before 可以看到 @before：

If @before is the head of list, the new item is inserted at the front.

head 就是被 list_t->head 所指向的 list_item_t

graphviz (4)
代表 list_t 不屬於 head 當 @before 指向 head 時就是在鏈結串列起點插入。
graphviz (7)
插入新的 item 後 item 變成新的 head
graphviz (9)

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;
-   *p->next = before;
+   (*p)->next = before;
}

The syntax specifies the precedence of operators in the evaluation of an expression, which is the same
as the order of the major subclauses of this subclause, highest precedence first[C99 6.5 footnote 74]

C99 規格書中 6.5 註腳 74 提出表達式的運算子優先級和子標題順序一致故可知優先級 & > -> > *。所以以上寫法並不等價。

延伸題目

程式運作

程式的運作如下圖所示:
graphviz (15)
首先建立一個指標的指標指向 list_t 的 head。
graphviz (18)
如果 head 指向的 list_item_t 就是 @before 所指
graphviz (19)
則使用解引用操控 head 指向要加入的 item，然後操作 item 的 next 指向 @before 所指的 list_item_t。
graphviz (20)
如果指標的指標指向還未指向 @before 所指的 list_item_t，則利用迴圈使指標的指標指向目前 item 的 next 所指的 item 的next 直到遇到 @before 所指的 list_item_t。

撰寫合併排序操作

以 list_insert_before 為基礎撰寫合併排序操作，合併排序主要利用分治法來操作，q_sort 利用遞迴將整個鏈結串列分成多個鏈結串列，mergeTwoList 再兩兩合併直到合併成一個完整的鏈結串列。

將 mergeTwoList 改為使用 list_insert_before 操作。

void mergeTwoList(list_t result, 
                    list_t *left,
                    list_t *right)
{
    result->head = NULL;
    
    while (!left->head && !right->head) {
        if (left->head->value <= right->head->value) {
            list_item_t *item = left->head;
            left->head = item->next;

        } else {
            list_item_t *item = right->head->next;
            right->head = item->next;
        }
        item->next=NULL;
        list_insert_before(&result, result->head, item);
    }
    
    while (!left->head) {
        list_item_t *item = left->head;
        left->head = item->next;
        item->next=NULL;
        list_insert_before(&result, result->head, item);
    } 
    
    while (!right->head) {
        list_item_t *item = right->head->next;
        right->head = item->next;
        item->next=NULL;
        list_insert_before(&result, result->head, item);
    }
    
    return;
}

以升序排序為例：首先當合併 left 和 right 兩者都還有 list_item_t 時就要比較 head->value 的大小並取出 head->value。
graphviz (22)

比較 head->value 的大小並取出 head->value 較小的作為 item，然後使用 list_insert_before 將 item 插入暫存結果的 result 的尾端。
graphviz (23)

當 left 和 right 兩者其中之一已經為空則將剩下的所有元素依序插入 result 的尾端。
graphviz (25)

Quiz 1-2

基於註解說明可知道這一段程式碼希望找到左子樹的:

        /* Find the in-order predecessor:
         * This is the rightmost node in the left subtree.
         */
        block_t **pred_ptr = &(*node_ptr)->l;
        while (EEEE)
            pred_ptr = FFFF;

graphviz (27)

首先我參考指標的指標的概念填寫答案，主要希望是可以找到上圖中黃色虛線的左子樹最右的節點：

EEEE = (*pred_ptr)->r
FFFF = &(*pred_ptr)->r

程式運作

remove_free_tree 的運作主要是為了找到 malloc 時所需的 free chunk (節點)這些節點由二元樹 free_tree 管理

首先使用 find_free_tree 找到符合我們的目標也就是尺寸符合需求的節點並且使用指標的指標 node_ptr 操作該節點。
remove_free_tree 希望移除該節點，所以針對該節點的狀態決定操作：
- 節點沒有子樹，直接移除該點
- 節點只有左右子樹其一，該子樹的根直接變成 node_ptr
- 節點左右子樹要先利用 find_predecessor_free_tree 確保 predecessor 正確並進一步針對 predecessor 的狀態來做不同的操作
  - predecessor 是子樹的根
  - predecessor 在更深的位置

針對節點左右子樹都有，移除操作需要找到該節點 in-order 走訪順序的前者來代替該節點的位置稱為 predecessor。

針對 predecessor 是子樹的根：

首先利用 old_right 指標紀錄原本的右子樹，並將要移除的節點移除，然後讓新的根也就是舊的左子樹的右子樹指標指向old_right：
針對 predecessor 在更深的位置：

分別保存舊有的左右子樹

並且將 predecessor 移出原本的位置

再將 predecessor 左右子樹的指標指向 old_right 和 old_left，並用 assert 確認左右子樹正確鏈結。

延伸題目

補齊獨立測試程式嗎

因為在程式運作中已經補齊程式碼並講解運作流程，此處提供以下 assert 測試所需的測試程式碼。

block_t **find_free_tree(block_t **root, block_t *target);
block_t *find_predecessor_free_tree(block_t **root, block_t *node);

以下是測試程式碼的實作。

block_t **find_free_tree(block_t **root, block_t *target)
{
    if(*root == NULL) return NULL;
    block_t **ptr = root;

    if((*ptr)->size == target->size) 
        return ptr;
    else if ((*ptr)->size > target->size) 
        return find_free_tree(&(*ptr)->l, target);
    else if ((*ptr)->size < target->size) 
        return find_free_tree(&(*ptr)->r, target);
    

    return NULL;
}

block_t *find_predecessor_free_tree(block_t **root, block_t *node)
{
    block_t **ptr = find_free_tree(root, node);

    if (ptr == NULL || *ptr == NULL) {
        return NULL;
    }
    
    if ((*ptr)->l) {
        ptr = &(*ptr)->l;
        while((*ptr)->r){
            ptr = &(*ptr)->r;
        }
    }
    return *ptr;
}

測試程式線上運作以下是運行了 remove_free_tree(&root, root) 後的結果：

Level 0:           4
Level 1:          2    5
Level 2:         1  3null  6
Level 3:        nullnullnullnullnullnull

Level Order Traversal with Spacing:
Level 0:           3
Level 1:          2    5
Level 2:         1nullnull  6
Level 3:        nullnullnullnull

我額外撰寫了 create_tree 和 print_level_order_with_spacing 來輸出和方便建立二元搜尋樹。

記憶體配置器

我參考 Custom memory allocators 製作自訂記憶體配置器，內容資訊存放在 Custom memory allocators 研讀筆記這邊只擷取用到的資訊。

首先我最擔心的即是整個記憶體配置器的複雜度，但研讀完文章發現其實現在記憶體配置器的分工十分明確，所謂的自訂記憶體配置器只是在記憶體配置器的階層中插入一個元件，這個元件負責接收上一層的記憶體配置器元件並作操作：

allocate：預定子分區的地址範圍
deallocate：釋放子分區的地址範圍
resize：可選項，用於調整已 allocate 的子分區的地址範圍大小，較難作的有效率。
目標是針對特地的應用製作專屬的自訂記憶體配置器，而非製作通用的記憶體配置器。

實作設計

我目前在這個 repo 實作了 c_alloc, c_free

custom-memory-allocator

以下是我設計的配置器結構 free_root 用指向保存可用區塊的二元搜尋樹：

typedef struct my_allocator {
    size_t total_size;
    size_t peak_size;
    size_t used_size;
    block_t *free_root;
} my_allocator_t;

並且我會在已分配的區塊額外分配一個標頭用來存放區塊資訊，例如：區塊大小，因此在 c_free 執行後就可以利用區塊資訊建立 block_t 插入 free_root。一開始實作的效果並不好和 malloc 的延遲差了100倍

100000 1.204823 0.012557
200000 8.246375 0.025077
300000 23.978644 0.037554
400000 48.674694 0.050032
500000 83.996539 0.062554
600000 134.000926 0.075077
700000 205.729124 0.087639
800000 308.384980 0.100142
900000 452.965177 0.112667
1000000 646.330178 0.125187

待辦
需要進一步改善效能然後再次測量

Quiz 1-3

GGGG = head->prev=prev
HHHH = list_entry(pivot,node_t,list)->value
IIII = list_entry(n,node_t,list)->value
JJJJ = pivot
KKKK = right

延伸題目

程式運作

graphviz 改自 Quiz 1-3

list_head 常用於維護雙向鏈結串列的結構，使用方法是在宣告一格結構 list_head 包含來管理鏈結，並利用 list_entry 來取得包含 node_t 的物件才可以取得物件的其他值。

struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

考慮到 list_head 是雙向鏈結串列而 quick_sort，初始化 begin[0] pivot L R end[0] 等指標，並斷開鏈結串列尾端的鏈結讓他暫時變成單向鏈結串列，

list->prev->next = NULL;

在 quick_sort 中不會維護 prev 鏈結直到排序完成，所以為了方便呈現在圖片先移出，並且 pivot 所在的節點斷開。

p 從 pivot->next 走訪到尾端的所有的節點，將 value 大於 pivot->value 放在 R，value 小於 pivot->value 放在 L

並且個別的 begin end 指向 L R pivot，並把 L R 指向 NULL

right 代表的是比 pivot 大的節點，然後下一個迴圈從比 pivot 大的節點作相同操作，直到找到只剩一個節點(L == R)代表這節點是最大的，將該節點加入 result。

因為 begin[0] 不只有一個元素，所以重複上述的動作。

再次將節點加入 result，即可的到排序完成的結果，並將 list 接回來。

rebuild_list_link(list)
利用兩個指標 prev _node 將 _node 的 prev 指回 _prev(節點)

直到 _node 指到 NULL ，代表 _prev 到最後一個節點，將最後一個節點的 prev 指向 list，list 的 next 指向最後一個節點。

研讀〈A comparative study of linked list sorting algorithms〉

Two doubly linked list sorting algorithms are included in this study, the sediment sort and the tree sort. There is no need to repeat the sediment sort here and the interested reader should refer to [2] for the details.

基於文中提到雙向鏈結串列的排序演算法有 sediment sort 和 tree sort 所以我會針對這兩個演算法利用 Linux 核心風格的 List API 予以實作。

sediment sort

Commit f9f1493

在這個 commit 中我實作了 sediment sort：

首先考慮到 list_head 是雙向鏈結串列斷開鏈結串列尾端的鏈結讓他暫時變成單向鏈結串列，因此同樣的 prev 先省略已簡化圖片。
初始化 __prev 用於交換節點，new_tail 用於設定新的迭代結束邊界
接下來執行迴圈執行多次迭代，直到一整次迭代中也沒有交換發生。

當迭代中交換發生時 __next 指向 __node->next->next，接下來交換節點。

Commit e9b58b4

原本設計每次迭代有交換發生該迭代結束 new_tail 向前一個代表最後一個元素不用再檢查代這樣不符合 sediment sort 定義且會增加無謂的檢查次數。這次提交修改設計每次迭代有交換發生該次迭代用 last_swapped 指向 __next 代表最後交換發生的地方。

重複上述動作直到，迭代結束 new_tail 指向 last_swapped 所在位置代表這是新的結束邊界，走訪到那裏即可結束。

重複以上動作直到整個鏈結串列在一次迭代中走訪完全沒有交換發生，代表排序完成即可用 rebuild_list_link 將鏈結串列回復成雙向。

tree sort

Commit 25eab72

利用 list_head 的 prev next 指標作為二元搜尋樹的左右指標，建立空二元搜尋樹，使用 list_each_safe 將每個節點加入插入二元搜尋樹，再利用參考 A comparative study of linked list sorting algorithms 提供中序走訪法將所有節點依序插入原本佇列的 head。

Quiz 2-1

AAAA = list_first_entry
BBBB = list_del
CCCC = list_move_tail
DDDD = list_add
EEEE = list_splice
FFFF = list_splice_tail

延伸題目

程式運作

尋常的快速排序程式碼運作在前述內容已提到，這裡主要說明探討 list_for_each_entry_safe 建構的迴圈中，若將 list_move_tail 換為 list_move，為何會無法滿足 stable sorting。這邊已兩個相同值的元素為例：

將 list_move_tail 換為 list_move 主要影響的就是 right 中的排序。

這邊再次作拆分直到只剩一個元素，然後再將每個元素合併。

right 中的排序會影響到整理排序階段的插入順序導致錯誤。

    list_add(&pivot->list, head);
    list_splice(&list_less, head);
    list_splice_tail(&list_greater, head);

改進 random_shuffle_array

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;
    }
}

參考統計方法驗證 shuffle 使用 Pearson's chi-squared test 驗證 shuffle 遵守 Uniform distribution。以下是 random_shuffle_array 針對三個元素打亂的測量結果： demo

Expectation: 166666.666667
Observation:
123: 206345
132: 126985
213: 150798
231: 182539
312: 206343
321: 126990
Chi-square sum: 40807.197944

這是測量 1000000 次後的到的結果：

	觀察到的頻率	期待的頻率	$\frac{(O_{i} - E_{i})^{2}}{E_{i}}$
[1, 2, 3]	206345	166666	83960.92890363692
[2, 1, 3]	126985	166666	84324.3907689059
[2, 3, 1]	150798	166666	16395.24420533537
[1, 3, 2]	182539	166666	14804.05225658245
[3, 1, 2]	206343	166666	83961.07771676397
[3, 2, 1]	126990	166666	84324.47782047899
Total			40807.197944

從卡方分布表找合適的 P value，我們的自由度為 5，

X^{2}

為 40807.197944，因為 20.52 < 40807.197944，於是 P value 小於 0.001 。

因為 P value（0.01）< alpha（0.05），統計檢定的結果拒絕虛無假說（

H_{0}

）
也就是樣本資料拒絕 shuffle 的結果遵循 Uniform distribution。

改進方法是使用 Fisher–Yates shuffle 以下實作及驗證內容我放在 Fisher–Yates shuffle 實作。

將程式碼整合進 lab0 提及的 `qtest`

我將這部分內容整合到環狀雙向鏈結串列的排序效能。

Quiz 2-2

Digit-by-digit Method

研讀 Digit-by-digit Method，重新整理成方便自己理解的推論脈絡：
我們想要找到數字

N^{2}

的平方根而

N

就是我們要找到的答案是很多個位數組成的，例如：

1000 = 1 * 1000 + 0 * 100 + 0 * 10 + 0 * 1

，所以核心思想就是透過公式一個個位數逐步逼近找處接近

N

的值。

N^{2} = (a_{n} + a_{n - 1} + \dots + a_{1} + a_{0})^{2}

而

m

元平方和可藉由

1

到

m - 1

元平方和總和，同時加上一項兩平方和的差值

Y_{m}

：

(a_{m} + a_{m - 1} + \dots + a_{1} + a_{0})^{2} - (a_{m - 1} + \dots + a_{1} + a_{0})^{2} = Y_{m}

Y_{m}

的公式如下：

Y_{m} = [(2 \sum_{i = m + 1}^{n} a_{i}) + a_{m}] a_{m} = (2 P_{m + 1} + a_{m}) a_{m}

Y_{m}

的公式是透過以下推導：
三元平方和

\begin{aligned} (a + b + c)^{2} & = ((a + b) + c)^{2} \\ = (a + b)^{2} + (a + b) c + c (a + b) + c^{2} \\ = (a + b)^{2} + (2 (a + b) + c) c \\ = a^{2} + (2 a + b) b + (2 (a + b) + c) c \end{aligned}

四元平方和

\begin{aligned} (a + b + c + d)^{2} & = ((a + b + c) + d)^{2} \\ = (a + b + c)^{2} + (a + b + c) d + d (a + b + c) + d^{2} \\ = (a + b + c)^{2} + (2 (a + b + c) + d) d \\ = a^{2} + (2 a + b) b + (2 (a + b) + c) c + (2 (a + b + c) + d) d \end{aligned}

四元平方和 - 三元平方和

\begin{aligned} (a + b + c + d)^{2} - (a + b + c)^{2} & = ((a + b + c) + d)^{2} - (a + b + c)^{2} \\ = (a + b + c) d + d (a + b + c) + d^{2} \\ = (2 (a + b + c) + d) d \\ = (2 P_{1} + a_{0}) a_{0} \\ = Y_{0} \end{aligned}

其中

P_{m + 1} = a_{n} + a_{n - 1} + \dots + a_{m + 2} + a_{m + 1}

(最高位到低位)而

P_{0} = N

（最高位到第 0 位）且

P_{m} = P_{m + 1} + a_{m}, for 1 \leq m < n

總結上述兩個觀察，可知：

$n$ 元平方和可以藉由
$1$ 到
$n - 1$ 元平方和總和，再加一項
$Y_{n}$
$Y_{n} = (2 P_{n - 1} + a_{n}) a_{n}$ 其中
$P_{n - 1} = P_{n - 2} + a_{n - 1}$

上述提到的是十進位，但其實延伸到二進位（數值系統）也是同樣的道理：

b_{0}

為最高位為

1

之位元，二進位轉十進位如下：

\sum_{i = 0}^{n} a_{i} = \sum_{i = 0}^{n} b_{i} \times 2^{n - i}

假設

N^{2}

可以用二進位系統逼近：

\begin{aligned} N^{2} & \approx (b_{n} \times 2^{0} + b_{n - 1} \times 2^{1} + \dots b_{1} \times 2^{n - 1} + b_{0} \times 2^{n})^{2} \\ = (a_{n} + a_{n - 1} + \dots a_{1} + a_{0})^{2} \end{aligned}

所以如果在數值系統中，假設是從最高的位數為

1

是第

n

位元，所以套用以下公式從最高位決定每個位元的值，如果已確定

n

到

m + 1

位元則判斷

m

位元是否加入逼近值

N

P_{m} = {\begin{cases} P_{m + 1} + 2^{m}, & if P_{m}^{2} \leq N^{2}, \\ P_{m + 1}, & otherwise. \end{cases}

舉例來說，設

N^{2} = 10

則

N^{2} = (10)_{10} = (1010)_{2} = (b_{3} \times 2^{3} + b_{1} \times 2^{1})

，最高位元

b_{3}

從

m = 3

開始計算。

$m = 3$ 時
$(P_{3})^{2} = (a_{3})^{2} = (2^{3})^{2} = 64 > 10 = N^{2}$ ，因此
$P_{3} = P_{4}$ 且
$a_{3} = 0$ 。
$m = 2$ 時
$(P_{2})^{2} = (a_{3} + a_{2})^{2} = (2^{2})^{2} = 16 > 10 = N^{2}$ ，因此
$P_{2} = P_{3}$ 且
$a_{2} = 0$
$m = 1$ 時
$(P_{1})^{2} = (a_{3} + a_{2} + a_{1})^{2} = (2^{1})^{2} = 4 < 10 = N^{2}$ ，因此
$P_{1} = P_{2} + 2^{1}$ 且
$a_{1} = 2^{1}$
$m = 0$ 時
$(P_{0})^{2} = (a_{3} + a_{2} + a_{1} + a_{0})^{2} = (2^{1} + 2^{0})^{2} = 3^{2} = 9 \leq 10 = N^{2}$ ，因此
$P_{0} = P_{1} + 2^{0}$ 且
$a_{0} = 2^{0}$

故

N = P_{0} = a_{1} + a_{0} = 2^{1} + 2^{0} = 3

，因此

10

的整數平方根為

3

。

令

X_{m} = N^{2} - (P_{m})^{2}

為差值表實際值與逼近值的誤差，其中

Y_{m} = (2 P_{m + 1} + a_{m}) a_{m}

運用以下性質可以縮減上述計算過程：

$X_{m} = N^{2} - (P_{m})^{2} = X_{m + 1} - Y_{m}$
$Y_{m} = (P_{m})^{2} - (P_{m + 1})^{2} = (2 P_{m + 1} + a_{m}) a_{m}$

研讀後發現以下段落看不懂

X_{m} = N^{2} - Y_{m}

且

X_{m} = N^{2} - P_{m}^{2}

那不就代表

P_{m}^{2} = Y_{m}

，這和上述的推論

Y_{m} = P_{m}^{2} - P_{m + 1}^{2}

矛盾而且後面的推導都沒有用到這個設定，因此我判斷此處是筆誤所以對 Digit-by-digit Method 做了修改。

因為

Y_{m} = (2 P_{m + 1} + a_{m}) a_{m}

而且

a_{m} = 2^{m}

，因此

Y_{m} = (2 P_{m + 1} + 2^{m}) 2^{m} = 2^{m + 1} P_{m} + (2^{m})^{2}

令

c_{m} = 2 a_{m} P_{m + 1} = P_{m + 1} 2^{m + 1}

與

d_{m} = a_{m}^{2} = (2^{m})^{2}

。

重新將

Y_{m}

表示為

Y_{m} = {\begin{cases} c_{m} + d_{m}, & if a_{m} = 2^{m}, \\ 0, & if a_{m} = 0. \end{cases}

利用

P_{m} = a_{m} + P_{m + 1}

\begin{aligned} c_{m} & = 2 a_{m} P_{m + 1} \\ = 2 a_{m} (P_{m} - a_{m}) \\ = 2 a_{m} P_{m} - 2 a_{m}^{2} \\ = 2 c_{m - 1} - 2 a_{m}^{2} \end{aligned}

同時

d_{m} = (2^{m})^{2} = (2 \times 2^{m - 1})^{2} = 4 (2^{m - 1})^{2}

則

d_{m - 1} = d_{m} / 4

。

所以可推論

if a_{m} \neq 0

c_{m - 1} = c_{m} / 2 + a_{m}^{2}

同時

d_{m} = a_{m}^{2} = (2^{m})^{2}

所以

c_{m - 1} = c_{m} / 2 + d_{m}

總結迭代關係為

c_{m - 1} = {\begin{cases} c_{m} / 2 + d_{m}, & if a_{m} \neq 0, \\ c_{m} / 2, & if a_{m} = 0. \end{cases}

與

d_{m - 1} = d_{m} / 4

帶入

m = 0

和

c_{m} = 2 a_{m} P_{m + 1}

則可以藉由

c_{- 1}

得知平方根為

c_{- 1} = P_{0} 2^{0} = P_{0} = N .

程式運作

在程式運作中需要找到最高的非

0

位元，因此需要有一個計算 leading zero，例如在

8

位元系統中：

(10)_{10} = (00001010)_{2}

，leading zero 為

4

。

#define clz32(x) clz2(x, 0)

首先 clz32 就是找出32位元的 leading zero 是利用遞迴呼叫 clz2 實作。
將此數值等分為兩部分：較高位（upper）與較低位（lower）。

Upper	Lower
0000 0000 0000 0001	1111 0000 0000 0000

如果 Upper == 0 代表只要判斷 Lower的 leading zero 加上 Upper 的位元數即可
如果 Upper != 0 代表要判斷 Upper 的 leading zero

直到遞迴切割到 Upper 和 Lower 都只剩兩個位元就可以利用查表的方式來得到 leading zero 的值。clz2(uint32_t x, int c) 中的 c 用來表示遞迴次數，因為

32 = 2^{5}

，所以在對半切三次即可得到終止條件。

static const int magic[] = {2, 1, 0, 0};

if (c == 3)
    return upper ? magic[upper] : 2 + magic[lower];

magic 用來查表 leading zero 的值，

十進位	0	1	2	3
二進位	00	01	10	11
leading zero	2	1	0	0

mask 是用來控制切割位元大小用來得到該次 lower。

static const int mask[] = {0, 8, 12, 14};
uint32_t lower = (x & (0xFFFF >> mask[c]));

接下來利用 clz32 得到最高位元的索引即可開始利用 Digit-by-digit Method 計算逼近平方根

/* clz64(x) returns the count of leading zeros in x.
 * (total_bits - 1 - clz64(x)) gives the index of the
 * highest set bit. Rounding that index down to an even 
 * number ensures our starting m is a power of 4.
 */
 
int shift = (total_bits - 1 - clz64(x)) & ~1;
m = 1ULL << shift;

為了確保 m 是 power of 4 代表 shift 必須是偶數：

shift	m
0	1
1	2 不是 power of 4
2	4
3	8

這不是個很難的操作以下兩種都可以得到一樣的效果，難的是要用最精簡的方式寫

- int shift = (total_bits - 1 - clz64(x)) & (0x1f<<1);
+ int shift = (total_bits - 1 - clz64(x)) & ~1;

關於 ~ 根據 C99，6.5.3.3 Unary arithmetic operators：

The result of the ~ operator is the bitwise complement of its (promoted) operand.
If the promoted type of the operand is unsigned, the result is computed by subtracting the value from the largest value representable in the type plus 1.

意思是：

~x 會對 x 的每一位元執行 1 → 0 和 0 → 1 的翻轉（補數運算）。
如果 x 是無符號型別 (unsigned)，結果等同於 UINT_MAX - x。
如果 x 是有符號型別 (signed)，則是二補數的位元反轉。

while (m) {
    uint64_t b = y + m;
    y >>= 1;
    if (x >= b) {
        x -= b;
        y += m;
    }
    m >>= 2;
}

總結迭代關係為

$c_{m - 1} = {\begin{cases} c_{m} / 2 + d_{m}, & if a_{m} \neq 0, \\ c_{m} / 2, & if a_{m} = 0. \end{cases}$
與

$d_{m - 1} = d_{m} / 4$
帶入
$m = 0$ 和
$c_{m} = 2 a_{m} P_{m + 1}$ 則可以藉由
$c_{- 1}$ 得知平方根為

$c_{- 1} = P_{0} 2^{0} = P_{0} = N .$

這迴圈就是利用了以上的迭代關係：
我們已知

c_{m} = a_{m + 1} P_{m + 1} = P_{m + 1} 2^{m + 1}

與

d_{m} = (2^{m})^{2}

。

\begin{aligned} Y_{m} & = 2^{m + 1} P_{m + 1} + (2^{m})^{2} \\ = c_{m} + d_{m} \end{aligned}

x 代表當前的剩餘數值

N - Y_{m}

又

Y_{m} = (P_{m})^{2} - (P_{m + 1})^{2}

，所以所求的

\begin{aligned} N^{2} & = (P_{0})^{2} \\ = (P_{1})^{2} + Y_{0} \\ = (P_{2})^{2} + Y_{1} + Y_{0} \\ = (P_{m})^{2} + Y_{m - 1} + . . . + Y_{0} \end{aligned}

Y_{m}

則是 y + b

y =
$c_{m}$
m =
$d_{m}$

if (x >= b) {
    x -= b;
    y += m;
}

if (x >= b) 代表目前剩餘的值還大於該回合的

Y

，並且可以藉由這個條件得知該位元為一。

Y_{m} = {\begin{cases} c_{m} + d_{m}, & if a_{m} = 2^{m}, \\ 0, & if a_{m} = 0. \end{cases}

(P_{m})^{2}

的值則可以用以下公式得知：

P_{m} = {\begin{cases} P_{m + 1} + 2^{m}, & if P_{m}^{2} \leq N^{2}, \\ P_{m + 1}, & otherwise. \end{cases}

最後每個迴圈用位元運算完成遞迴的迭代：

y >>= 1;
m >>= 2;

延伸問題

擴充為
$⌈ \sqrt{x}) ⌉$ (向上取整數) 實作

我的想法是單純的用得出的答案 ｙ＾２，和 x 比較即可。
因此需要實作只使用 bitwise 乘法，這需要用到 bitwise 加法和 bitwise 絕對值

+   if(multiply(y,y) < x) return y + 1;

bitwise 加法

op1	op2	carry
0	0	0
0	1	0
1	0	0
1	1	1

前三種情況可以透過 XOR 得到一樣的結果，而有 carry 產生則必須使用到 & 判斷及 << 作位移。

int add(int op1, int op2){
    int sum = op1;
    int carry = op2;

    while(carry){
        int temp = op1;
        sum = temp ^ carry;
        carry = (sum & op2) << 1;
    }
    return sum;
}

這段程式碼就是用 XOR 進行每個位元的加法後，並且用 & 判斷每個位元是否有carry` 還有則要進一步做加法直到所有位元都沒有進位了。

bitwise 絕對值

如果是負數，將二補數負數轉為正數（取補數+1）

int abs(int num)
{
  return num < 0 ? add(~num, 1) : num;
}

bitwise 乘法

參考位運算筆記(bitwise operation)

int multiply(int a, int b)
{
  int multiplicand = abs(a), multiplier = abs(b);

  int product = 0;
  while (multiplier)
  {
    product = add(product, multiplicand);
    multiplier = sub(multiplier , 1);
  }

  if ((a ^ b) < 0)
  {
    product = add(~product, 1);
  }

  return product;
}

乘法就是多次的加法，先統一把 multiplicand 和 multiplier 都取絕對值然後就是不斷重複加法。
(a ^ b) < 0 代表兩者的sign bit(Most Significant bit) 不同則將 Product 取負數。

符號位 (MSB) 代表正負號
在 二補數 (Two's Complement) 表示法中：

最高位 (MSB) = 0 → 正數
最高位 (MSB) = 1 → 負數

位元 A	位元 B	A ^ B (XOR)
0	0	0
0	1	1
1	0	1
1	1	0

此外乘法還有另一種使用左移右移實作：

\begin{aligned} 乘 數 \times 被 乘 數 & = 積 \\ (乘 數 \times \frac{1}{2}) \times (被 乘 數 \times 2) & = 積 \end{aligned}

while(multiplier)
{
    if(multiplier & 1)
        add(product, multiplicand);
    multiplicand <<= 1;
    multiplier >>= 1;
}

撰寫不依賴除法指令的 `sqrtf`

待補

比較不同手法的整數開平方根效能

待補

Quiz 2-3

AAAA = map->bits

BBBB = map->bits

CCCC = first->pprev

DDDD = n->pprev

EEEE = n->pprev

延伸題目

程式運作

分為幾個主要物件：

map_t 管理雜湊表的 bucket，bit 用來決定雜湊表範圍
每個 bucket 的 first 指向 hlist_head hlist_head沒有 pprev 可以幫助在 bucket 時很多減輕記憶體負擔
key_t 管理雜湊表中的值，具有 next 指向下一個 key_t， pprev 是指標的指標指向上一個 key_t 的 next。

2025q1 Homework2 (quiz1+2)

開發環境

Quiz 1-1

單向鏈結串列

assert

list_insert_before

延伸題目

程式運作

撰寫合併排序操作

Quiz 1-2

程式運作

延伸題目

補齊獨立測試程式嗎

記憶體配置器

實作設計

Quiz 1-3

延伸題目

程式運作

研讀〈A comparative study of linked list sorting algorithms〉

sediment sort

tree sort

Quiz 2-1

延伸題目

程式運作

改進 random_shuffle_array

將程式碼整合進 lab0 提及的 qtest

Quiz 2-2

Digit-by-digit Method

程式運作

延伸問題

擴充為 ⌈x)⌉ (向上取整數) 實作

bitwise 加法

bitwise 絕對值

bitwise 乘法

撰寫不依賴除法指令的 sqrtf

比較不同手法的整數開平方根效能

Quiz 2-3

延伸題目

程式運作

Read more

2025q1 Homework1 (lab0)

Custom memory allocators 研讀筆記

2025q1 Homework1 (ideas)

將程式碼整合進 lab0 提及的 `qtest`

擴充為
$⌈ \sqrt{x}) ⌉$ (向上取整數) 實作

撰寫不依賴除法指令的 `sqrtf`