2024q1 Homework1 (lab0)

contributed by < fennecJ >

Reviewed by HenryChaing

學到很多之前曾未想過得串列實作方式，其他留言放在內文。

開發環境

# gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

# lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         48 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  12
  On-line CPU(s) list:   0-11
Vendor ID:               AuthenticAMD
  Model name:            AMD Ryzen 5 7600X 6-Core Processor
    CPU family:          25
    Model:               97
    Thread(s) per core:  2
    Core(s) per socket:  6
    Socket(s):           1
    Stepping:            2
    CPU max MHz:         5453.0000
    CPU min MHz:         400.0000
    BogoMIPS:            9381.96

q_insert_head

commit 56af0a

對照 Dictionary.com 對 implement 一詞的解釋:

• to fulfill; perform; carry out:
• to put into effect according to or by means of a definite plan or procedure.
• Computers. to realize or instantiate (an element in a program), often under certain conditions as specified by the software involved.
• to fill out or supplement

「實作」會是符合上述 "implement" 語意的譯詞，取「起」以「創作」的意思，而「製造」本質上是固定輸入並通常產生固定輸出的行為。

$\to$ 資訊科技詞彙翻譯

一開始我的作法如下：

bool q_insert_head(struct list_head *head, char *s)
{
    ...
    list_add(&(ele->list), head);
    return true;
}

不要寫錯重要軟體的名稱。

但這樣在嘗試 commit 的時候會一直被 Cppcheck 擋下來：

error: Memory leak: ele [memleak]

一開始嘗試查閱 Cppcheck manual ，但卻沒能解決我的問題。
花了一些時間後我猜 ele->list 如果沒有初始化的話 list->next, list->prev 不知道會指到哪邊造成潛在的錯誤。因此一開始以 INIT_LIST_HEAD 初始化 ele->list 的方式通過 Cppcheck。 但仔細檢視 list_add 後留意到它會明確將 list->next, list->prev 指到原本的 head->next 和 head ，不符前述假設。
之後做了許多嘗試，最後發現問題出在最後面的 list_add(&(ele->list), head) ，將其改為 list_add(&ele->list, head) （移除 ele->list 前後的括號）後就能通過 Cppcheck 的靜態檢查。

bool q_insert_head(struct list_head *head, char *s)
{
    ...
-   list_add(&(ele->list), head);
+   list_add(&ele->list, head);
    return true;
}

q_remove_head

看到 remove 這個字的時候，一開始直覺認為會需要 free 記憶體空間，直到檢視 queue.h 中的註解：

NOTE: "remove" is different from "delete"
The space used by the list element and the string should not be freed.
The only thing "remove" need to do is unlink it.

才知道只需 unlink 即可。
檢視 List Management Functions ，留意到 list_del 這個 API ，到 list.h 中可看到對應實作僅有將 node 進行 unlink:

static inline void list_del(struct list_head *node)
{
    struct list_head *next = node->next;
    struct list_head *prev = node->prev;

    next->prev = prev;
    prev->next = next;

#ifdef LIST_POISONING
    node->prev = (struct list_head *) (0x00100100);
    node->next = (struct list_head *) (0x00200200);
#endif
}

同時可以留意裡面的 LIST_POISONING 會將 node 的前後指向非法的記憶體位址，用來防止 access via deleted node's next/prev，為何不將 node's next/prev 直接指向 NULL，這是為了能幫助我們更好的 debug ，可參考 What is the role of LIST_POISON1 and LIST_POISON2 的討論，若我們知道 page fault 的 addr 是 LIST_POISON1/2 ，我們能更容易定位到可能出錯的程式碼有哪些。

對照 2024-02-{20,27} 問答簡記

授課老師有建議可以多使用中文專有名詞，如節點。
HenryChaing

q_merge

commit 285041

不斷的將第二個以後的 queue merge 到第一個 queue 中即可。而在 merge 二個已排序的雙向鏈結串列時，為了方便處理迴圈結束的判斷條件，會將二個鏈結串列都改為 singular list

...
entry->q->prev->next = NULL;
...

最後透過一個 helper function rebuild_list_link
將全部合併完的 list 回復為雙向鏈結串列。
值得一提的是在合併比較時用了一個 bitwise 的小技巧：

node = ((strcmp(ele1->value, ele2->value) < 0) ^ descend) ? &l1 : &l2;

直接用 xor descend 來判斷接下來的 node 應該是接 l1 的 node 或是 l2 的 node ，但會導致 sort unstable 的問題。

可以了解互斥或操作，但想請教您為何結果會 unstable
HenryChaing

您好，stable sort 的定義為若存在元素 A, B 滿足兩者鍵值相等，則 sort 後 A, B相對位置不變。現在我們檢視上述透過互斥或的操作，假設 ele1->value 和 ele2->value 相等且 ele1 在 ele2 前面，若要滿足 stability ， ele1 在排序後也需要在 ele2 前面。若此時 descend = ture ，則 (strcmp(…) < 0 ) ^ descend 會等於 (0) ^ 1 = 1 。導致 ele2 先於 ele1 被放進 sorting 後的佇列中， ele1, ele2 兩者的前後關係發生改變。造成結果 unstable 。 在這裡用 ^ descend 的問題為，在 ele1, ele2 兩者相等時也會達成交換順序的條件。
fennecJ

q_delete_mid

commit e51e73

改進你的漢語表達。

我的作法是用兩個指標 forward, backward 以對向、相同移動速度來存取節點。由於這裡處理的是雙向鏈結串列，因此當兩個指標以相反等速的方向移動時，他們最終會相遇，下圖是一個簡單的示意：

為了說明為何他們相遇在中間點，現在我們將他們的起點切開，把圓攤平：

此時我們假設 Backward 和 Forward 相遇時， Backward 移動了 K 個距離。由於 Forward 以相同的速度移動，因此 Forward 的移動距離亦為 K 。我們可以得到

$$\begin{gathered} 2K=L \\ K={\displaystyle \frac{L}{2}} \end{gathered}$$

因此他們相遇的地方就在中間點。取出中間點後把它刪除即可。

...
struct list_head *forward, *backward;
forward = head->next;
backward = head->prev;
while(forward != backward && forward->next != backward){
    forward = forward->next;
    backward = backward->prev;
}
// backward will be the target we want to delete

q_reverse

commit b7150e

將每個 node 的 prev 和 next 對調即可。

list_for_each_safe (n, sf, head) {
    tmp = n->next;
    n->next = n->prev;
    n->prev = tmp;
}

不過要注意 list_for_each 系列的 MACRO 都是從 head->next 開始 traverse ，所以要記得另外更新 head 的 prev 和 next

tmp = head->next;
head->next = head->prev;
head->prev = tmp;

q_reverseK

commit 1e64e3e

q_reverseK 的處理步驟如下：

• 將 list 以 K 個 node 為一組切成數組 sublists
• 找到每個 sublists 的 start 和 tail nodes，若找不到 tail (i.e. 剩餘 nodes 不足 K 個 ) 則直接 return
• 除了 start 和 tail node 之外，sublist 中其餘 node 的處理方式都和 q_reverse 相同：將 node 的 prev 和 next 對調。
• 最後單獨處理 start 和 tail ：
  • start->next 指向原本的 tail->next
  • start->prev 指向原本的 start->next
  • tail->next 指向原本的 tail->prev
  • tail->prev 指向原本的 start->prev

q_descend, q_ascend

commit 1e64e3e

由於處理 q_descend 和 q_ascend 的主要邏輯相同，因此這裡只介紹 q_decend 的作法：
從最後一個 node head->prev 開始往前面的 node 看，並紀錄目前看過得最大 string max_str 。若往前看時該 node 的值小於 max_str ，則移除該 node。

---

網頁伺服器

研讀 整合網頁伺服器 時，學到了一個系統呼叫 select() 。
目前的理解如下：
使用者可將多個 file descriptor 傳入同一個集合 set 中，而 select 會同時 monitor 這些 file descriptor ，並透過 return value 告知使用者本次讀到的 file descriptor 是哪一個 file descriptor。

用數位邏輯裡頭的 MUX 解釋。

Mux （多工器）在數位邏輯中指的是可根據 sel 訊號從多個 input 中選擇一個訊號傳送到 output 的硬體，一個常見的 2-to-1 mux 構造如下：

以硬體描述語言 (HDL) 展現其行為：

module Mux(
    input i0,
    input i1,
    input sel,
    output out
)
assign out = (sel == 0) ? i0 : i1;
endmodule;

而 select() 系統呼叫可被視為：

• 可同時接收多個 I/O 輸入訊號。
• 根據不同的 I/O event 選擇對應的訊號輸出。

• 我們可以透過 FD_ISSET() 得知 select 訊號 S0 為何

Demux （解多工器） 在數位邏輯中指的是可根據 sel 訊號將一個訊號傳送到指定的接收端的硬體，一個常見的 1-to-2 demux 構造如下：

我們透過 FD_ISSET() 得知 select 訊號 S0 之後，可以根據 S0 進行後續的處理，就像是 Demux 的行為一樣：

可對照 console.c 中 cmd_select 的實做：

    if (readfds && FD_ISSET(infd, readfds)) {
        // readline from stdin
        ...
    } else if (readfds && FD_ISSET(web_fd, readfds)) {
        // read cmd from web server
        ...
    }

line_edit()

在 linenoise.c 中，主要讀取使用者輸入的 function 是 line_edit() 這個 function ：

...
while (1) {
    signed char c;
    int nread;
    char seq[5];

    nread = read(l.ifd, &c, 1);
...
}

這裡的 l.ifd 會是 stdin 的 fd ，透過 read 從 stdin 讀取一個 char 到 c 在交由後續進行處理。 若要讓 linenoise 也支援透過網頁伺服器接收命令，我們可以用 select() function 做 I/O multiplexing ，並依據收到的輸入是經由網路還是 stdin 做對應的處理。

web command

file 的翻譯是「檔案」，而非「文件」(document)

檢視 console.c ，可以看到 do_web 這個 function ，透過字串查找卻沒有看到有哪個文件 檔案有透過 do_web( 呼叫這個 function 。然而透過 ./qtest 開啟程式後輸入命令 web

# ./qtest
cmd> web
listen on port 9999, fd is 3

對照閱讀你所不知道的 C 語言：前置處理器應用篇

可以看到它會去執行 do_web 函式。仔細檢視和 web 相關的程式碼，發現 console.c 中有使用到一個巨集：

...
ADD_COMMAND(web, "Read commands from builtin web server", "[port]");
...

ADD_COMMAND 巨集展開如下：

#define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param)

可以看到它會藉由 do_##cmd 將 ADD_COMMAND(web,...) 展開為
add_cmd(web, do_web, ...)
當 console 接收到 web 命令時，就會執行對應的 do_web() ，這裡我們簡單檢視其實作（詳見 github ：

改進上方描述

static bool do_web(int argc, char *argv[])
{
    ...
    web_fd = web_open(port);
    if (web_fd > 0) {
        printf("listen on port %d, fd is %d\n", port, web_fd);
        use_linenoise = false;
    } 
    ...
}

可以注意到其中的 use_linenoise = false ，這是因為藉由 curl 透過網頁伺服器傳命令到 console 中必須要傳輸完整的命令，用不上自動補全，所以當啟用 web 命令後會將 use_linenoise 設為 false

檢視 run_console() 可得知 console 處理 input 的流程：

bool run_console(char *infile_name)
{
...
    if (!has_infile) {
        char *cmdline;
        while (use_linenoise && (cmdline = linenoise(prompt))) {
            interpret_cmd(cmdline);
            line_history_add(cmdline);       /* Add to the history. */
            line_history_save(HISTORY_FILE); /* Save the history on disk. */
            line_free(cmdline);
            while (buf_stack && buf_stack->fd != STDIN_FILENO)
                cmd_select(0, NULL, NULL, NULL, NULL);
            has_infile = false;
        }
        if (!use_linenoise) {
            while (!cmd_done())
                cmd_select(0, NULL, NULL, NULL, NULL);
        }
    } else {
        while (!cmd_done())
            cmd_select(0, NULL, NULL, NULL, NULL);
    }
...
}

先判斷是否有指定輸入檔案，若無 (i.e. stdin or via web) 則接著判斷是否能用 use_linenoise ，並透過 cmd_select 處理 input 。
cmd_select 是一個根據不同的 fd (stdin or web_fd) 進行對應處理的 function ，其實作可見 github

上述實作的缺陷

當開啟 web server 後，便再也不能使用 linenoise 的功能。有沒有辦法能同時支援 web server 又支援 linenoise 呢？

我的作法

commit ed8a2ad

由於使用 web 命令後便會把 linenoise 的功能關掉，因此我決定新增一個命令 web_close 讓使用者能在開啟 web server 後把它關起來，而在關掉 web server 的同時會再次將 linenoise 的功能打開。

嘗試改善

millaker's commit

增加 web_close 讓使用者能夠重新開啟 linenoise 的功能，但在 web server 運作時仍會導致 linenoise 失效。可否進一步使 web server 運作的同時 console 中的 linenoise 也能同時運作呢？
強者我朋友 millaker 提出了一個解決思路：
無論何時都 call 到 linenoise 中，在 line_edit 內才分辨目前的 fd 是 stdin 還是 web_fd ，並根據對應的 fd 做後續的處理：
只要是 std_in 就進行 linenoise 的自動補全；只要是 web_fd 就直接處理 web_fd 傳來的命令。

但這樣還是會有一個缺陷，就是當使用者在 console 中使用了自動補全之後，經由 curl 傳到 web server 的命令沒辦法立刻被收到，要等到使用者在 console 中按下 enter 後才會被接收到。和 millaker 討論後，我們發現 linenoise 中的 complete_line() 有一個 while loop ，直到使用者按下 enter 後才會離開這個迴圈，這時程式才有機會注意到 web_fd 中有尚未讀取的 data 的原因導致這個現象。我們可以很直接的修改 complete_line() 中處理的流程來解決 curl 被 linenoise 阻塞住的問題，但這會導致 linenoise 套件的運作邏輯被大幅改動，不利於後續的維護。

查資料的過程中，大致看了 SIGIO/poll/epoll 等等可以用來處理 socket data 的作法，但無論是哪個 function 似乎都不能很好 / 優雅的處理上述的問題。
如果要作到兩邊都能即時有反應，我目前只想到透過 context switch 的方式輪流處理 stdin 和 web_fd ，不知道還有什麼好方法？

對照 https://github.com/sysprog21/lab0-c/pull/162

vax-r 同學也對同時使用網頁伺服器和 linenoise 提出他的 解決方案 ，我十分贊同他 「盡可能對 linenoise 做最小改動」的這個想法，由於 linenoise 是額外整合在作業中的套件，日後若要將其 sync 到 upstream ，較小的改動能讓我們更容易進行更新的維護以及減少 bug 發生的機會。

我嘗試了 vax-r 同學的 repo 但仍會出現前述問題。
為了清楚說明，我將開啟兩個 terminal 並分成兩個名字： term_stdin, term_web
其中 term_stdin 用來透過終端機藉由 linenoise 直接和 qtest 互動
term_web 僅會透過 curl 將命令傳入 qtest 中的網頁伺服器。
依照下列步驟執行可重現我的問題：

• 在 term_stdin 輸入 web 開啟網頁伺服器
• 在 term_stdin 輸入 ne ，其後按下 tab 使其自動補全為 new
• 補全後不要在 term_stdin 中按下任何鍵，直接切換到 term_web (此時 term_std 畫面如下)

cmd> web
listen on port 9999, fd is 3
cmd> new▮

( ▮ 為游標符號 )

• 移動到 term_web 視窗，輸入 curl http://localhost:9999/it/a 並按下 enter ，會發現該命令被 block 住， qtest 不會處理它
• 這時回到 term_stdin 按下 enter 後會發現 it a 命令在 new 之後才被處理，此時term_stdin 畫面如下：

cmd> web
listen on port 9999, fd is 3
cmd> new
l = []
cmd> 
l = [a]
cmd> 

我認為先送出的命令 (it a 先被 enter 送出） 應先被處理較合理，但顯然 output 不符合先送出先處理的原則。（若先處理 it a 預期應可見到 Warning: Calling insert tail on null queue 等訊息）

I-HSIN Cheng
經過測試後，上述問題的發生是由於函式 complete_line 當中的 read 函式呼叫引起的阻塞問題，當我們按下 tab ( line_edit 當中的 main loop 監聽) 進行自動補全後，程式行為實際上是交給 complete_line 來進行自動補全，並在補全後依然停留在 complete_line 當中的 read 函式等待使用者進一步輸入，造成此 ./qtest 這個 process 阻塞在此處。
同時您在 term_web 下達的 curl 命令則被寫入 socket fd 指向的 file 當中等待讀取，直到您在 term_stdin 按下 ENTER 使得 ./qtest 跳出 complete_line 的迴圈並完成對應命令後，才去處理 socket fd 當中的指令。

fennecJ
原來如此，謝謝您耐心解釋程式流程和前述現象發生的原因。

I-HSIN Cheng
此處我認為有兩個解決方法。第一種是同時間處理多個請求的話，利用多執行緒的方法分開處理，畢竟 linenoise 原本的設計就建立在面對單一命令輸入的情形。第二種是同樣利用 web_eventmux 在complete_line 內做監聽，將 term_web 傳送進來的命令暫存，並在 complete_line 回傳時讓 line_edit 有兩個命令必須執行。我認為第一個方法較為恰當，第二個方法會大幅改動到 linenoise 套件預設行為（試想如果同時開啟 n 個 terminal 並對 ./qtest 發送請求，此方法就要暫存 n 條指令）。 此處應請教 Jserv 老師何種變更較為合適。
我認為還有一種較暴力的可能方法是在 web_eventmux 當中若收到網路封包請求就直接執行 interpret_cmd 將該命令直接執行，執行完後回到 linenoise 中的 complete_line 或 line_edit 繼續監聽 standard input 的命令，但此方法同樣涉及大量改動與變更 web 預設行為，我認為能讓功能執行但不適當。

fennecJ
原先我和 millaker 討論的解法也是您提到的第二點 - 在 complete_line 中進行 I/O 的監聽，但正如您提到的，此種方法將大幅改動 linenoise 原先的行為，可能導致後續維護上的困難。

I-HSIN Cheng
我使用一個替代方案，依據我上次提交的 PR ，如果在開啟 web 命令後，在 command-line 寫入任何指令（不按 tab ），並在另一個 terminal 傳入 command ，則程式會將 command buffer 當中的指令替換成 web request 傳送進來的指令，於是原本 command-line 的命令會被丟棄。如果此行為是可接受的，那只要在 complete_line 當中進行以下更動，即可做到相同的行爲。如果此行為是可接受的，我將於近日提交新的 PR 以修復此問題。

                ls->pos = saved.pos;
                ls->buf = saved.buf;
            } else {
                refresh_line(ls);
            }

+        if (eventmux_callback != NULL) {
+            int result = eventmux_callback(ls->buf);
+            if (result != 0) {
+                free_completions(&lc);
+                return ENTER;
+            }
+        }  

當初設計這項作業時，希望引導學員引入 coroutine 來解決問題，例如 Coroutines in C，工程領域本來就常見殊途同歸，很難說一個方法就絕對優於另一者，尚有其他的權衡 (trade-off) 因素，如程式碼的維護成本、持續擴充的考量。

jserv

實作 q_shuffle

commit 7002a4

照著教授提供的 Fisher–Yates shuffle 演算法可很容易的實作出來，比較特別的是和 404allen404 討論時他指出其實不用特別花心思處理要交換的 node->prev, next 等 link 的資料，而是可以直接交換 node 中 element 存的值。我覺得這個想法很好，因此用這個方法進行交換。

研讀論文〈Dude, is my code constant time〉

Misc

• make valgrind trace-17 每次都會過（目前試過 7 次），但 make test trace-17 幾乎都會 failed （ 14 次僅一次 pass）
• q_merge() 改良（改成頭尾兩兩合併）

研讀指定的論文

ttt

將 ttt 引入 lab0-c

為了方便後續的維護，我將 ttt 獨立為一個目錄並整合進 lab0-c 中，詳見 commit 613374

Concurrent programming

我將 ttt 的運作過程分為幾個並行程式：

• listen_keyboard 負責監聽任何按下按鍵的事件
• player_X_move 負責下 X 的 agent, ai 為 negamax
• player_O_move 負責下 O 的 agent, 根據 ttt_mode 的 option
• update_screen 負責顯示時間資訊和重新繪製棋盤等工作
• game_manager 負責判斷是否有人獲勝或是以滿足平手條件

task 的 schedule 則參考 preempt_sched 中的實做，同時在必要的地方直接呼叫 schedule() 將 cpu 使用權交出去增進使用體驗。

要注意的是，由於任一邊（ O 或 X ）下完之後都有可能滿足獲勝或平手的條件，因此實做上需要在 player_X_move/player_O_move 後都呼叫一次 game_manager 。另外也記得要分別呼叫 update_screen ，避免

task_add(listen_keyboard, g_args);
task_add(player_X_move, g_args);
task_add(update_screen, g_args);
task_add(game_manager, g_args);
task_add(player_O_move, g_args);
task_add(update_screen, g_args);
task_add(game_manager, g_args);

此外，為了方便不同並行程式間的溝通，我定義了一個結構 game_arg ：

typedef int(game_agent_t)(char *table, char mark);
typedef struct {
    char turn;
    char table[N_GRIDS];
    bool game_play;
    game_agent_t *agentX;
    game_agent_t *agentO;
    int pX_score;
    int pO_score;
    int draw;
    char *pX_name;
    char *pO_name;
    bool echo;
} game_arg;

而 player_X_move 和 player_O_move 運作上會分別呼叫 agentX 和 agentO 來決定要下在哪裡，如此只要替換掉 更改 agentX 和 agentO 指向的 function 便能很簡單的替換不同的 ai 邏輯。

ai vs ai

commit 2628ae

listen_keyboard

commit 4a2111

我留意到大部分同學在進行 ai vs human 的作業時無法同時顯示出當前的時間（精確到秒），而想要達到這樣的效果需要解決一個問題，就是若直接透過 read() 去捕捉使用者的輸入，則因為 nonblocking read 以及處理 IO 時會關閉 preemption 的關係，若使用者完全沒有在進盤上進行任何輸入，則畫面會直接卡在那邊無法透過 scheduler 跳到別的 coroutine 執行。
這裡我嘗試透過 poll() 系統呼叫，當 poll 偵測到 stdin 有新的 input ，則會直接由 read 讀取一個字元並寫入 input buffer ，直到偵測到使用者按下 enter 後才根據 input buffer 內容執行對應操作。若 poll 尚未偵測到 stdin 有新的 input ，則會直接呼叫 scheduler 進行排程讓畫面時間能夠刷新。而由於只有在明確知道有字元需要讀取時才會呼叫 read() ，此時由於 STDIN 有尚未讀取的字元存在所以立刻會處理完往後執行，而不會卡在那邊等新的輸入，如此便能造成即時反應的效果達到顯示出當前的時間（精確到秒）的功能。

nfds_t nfds = 1;

while (run_ttt) {
    poll(&pfd, nfds, 0);
    if (!(pfd.revents & POLLIN))
        schedule();

    // read part
    preempt_disable();
    (void) !read(STDIN_FILENO, &c, 1);
    ...

ai vs human

commit 76d90c

為了讓 ai vs human 也能順利顯示出當前的時間（精確到秒），我們仍需要 scheduler 的介入適時切換到印出時間資訊的 task 。

我在 listen_keyboard 中額外處理了 ENTER 和 BACKSPACE 事件，讓使用者能藉由 listen_keyboard 輸入座標並顯示在終端機上，同時透過 shceduler 來呼叫 update_screen 使時間能順利更新。

以下為 demo 影片：

定點數運算

log

實做主要參考 Clay S. Turner 提出的 A Fast Binary Logarithm Algorithm 以及對應的實現 程式碼

sqrt

使用牛頓法進行開根號運算：
假設我們要以牛頓法求 val 之根：
令方程式

$$f(x)=x^2-val$$
我們要求的根 a 滿足

$$f(a)=0$$
用牛頓法進行迭代，假設 a 初始值為

$a_0$ ， 可得

$$e_0=f(a_0)=a_0^2-val$$

已知

$$f^{\prime }(x)=2x$$
則我們可以得出過點 (

$a_0,e_0$) 之切線方程 L1 為

$$L1(x)=2a_0\ast x+e_0-2a_0^2$$
令

$a_1$ 為

$L1(x)=0$ 的根，則可求出

$$a_1={\displaystyle \frac{2a_0^2-e_0}{2a_0}}$$

$$=a_0-{\displaystyle \frac{e_0}{2a_0}}$$

$$=a_0-{\displaystyle \frac{a_0^2-val}{2a_0}}$$

$$=a_0-{\displaystyle \frac{a_0}{2}}+{\displaystyle \frac{val}{2a_0}}$$

$$={\displaystyle \frac{1}{2}}(a_0+{\displaystyle \frac{val}{a_0}})$$
之後我們便能再用 a_1 進行後續的迭代。

加速牛頓法的迭代
若初始值足夠靠近目標點則可以用更少的迭代次數取得足夠的精度。
已知

$val=2^{MSB}+...$ ，則我們可以知道

$\sqrt{val}$ 必定滿足

$\sqrt{val}>=2^{\lfloor \frac{MSB}{2}\rfloor }$
因此我們可將初始值設為

int x = 1 << (MSB >> 1);

而 MSB 的計算可由

MSB = 32 - __builtin_clz(val); 

得出。
然而這種估計方式只對整數域有效，假設傳入的定點數小數域共有 PRECISION 個 bits ，則

int x = 1 << (MSB >> 1);

會變成

int x = (1 << PRECISION) << (MSB >> 1);
// to express 1 in fixed point, we need to left shift PRECISION bits

且在計算 MSB 時，也要把 PRECISION 佔的 bit 數剪掉：

MSB = 32 - PRECISION - __builtin_clz(val); 

最後將其整理為初始值的計算公式：

$$(1<<PRECISION)<<(MSB>>1)$$

$$=1<<(PRECISION+(MSB>>1)$$

$$=1<<(PRECISION+(32-PRECISION-CLZ)>>1)$$

$$=1<<((PRECISION>>1)+16-(CLZ>>1))$$

uint32_t clz_res = __builtin_clz(val);
uint64_t x = 1 << ((precision >> 1) + 16 - (clz_res >> 1));

目前取 PRECISION 為 20 bits ，經過實驗，只要進行四次牛頓法就能收斂到可接受的誤差範圍。
之所以取 20 的原因是因為 mcts 演算法中的 ITERATION 次數為

${10}^6\approx 2^{20}$ 而計算 ust 的公式為

$${\displaystyle \frac{wins}{ITERATION}}+\sqrt{{\displaystyle \frac{2\ast log(parent\mathrm{\_}try)}{ITERATION}}}$$
因此小數部份需要能有

${10}^{-6}\approx 2^{-20}$ 的精度，因此取 20 bits 。
最後我們可以實做出對應的開根號運算：

uint32_t sqrtFix(uint32_t val){
clz_res =(uint32_t) __builtin_clz(val | 1);
    uint64_t x = 1 << ((PRECISION >> 1) + 16 - (clz_res >> 1));
    x = (x + fixDiv(val, x, PRECISION)) >> 1;
    x = (x + fixDiv(val, x, PRECISION)) >> 1;
    x = (x + fixDiv(val, x, PRECISION)) >> 1;
    x = (x + fixDiv(val, x, PRECISION)) >> 1;
    return x;
}

div/mult

直接進行乘除運算後記得 div 要左移; mult 要右移 PRECISION 位即可。

uint32_t fixMult(uint32_t a, uint32_t b, int precision){
    uint64_t res = a * b;
    return (uint32_t)(res >> precision);
}

uint32_t fixDiv(uint32_t a, uint32_t b, int precision){
    uint64_t t_a = (uint64_t)a << precision;
    // or 1 to prevent div by zero
    uint32_t res = t_a / (b | 1);
    return res;
}