# 2025-02-25 問答簡記

## 追蹤上週問答
> [2025-02-{18,20} 課堂問答簡記](https://hackmd.io/2jXewm-kQBSDHwWVEZBg2w)
> [2024-02-{20,27} 問答簡記](https://hackmd.io/YCnIwo_0R-GaYjISEZwG1A)

> [出處](https://x.com/Observer_ofyou/status/1893259556488171762)

## 快訊
* [追隨 Apache Iceberg 重量級人物，邁向卓越](https://www.facebook.com/groups/system.software2025/posts/931074139229388/)。最好的個人簡歷，就烙印在大型開放原始碼專案中
* [ThreadX 發布 v6.4.2](https://www.facebook.com/groups/system.software2025/posts/930882719248530/)。ThreadX 是全球唯一符合完整功能安全規範的開放原始碼 RTOS 實作，涵蓋 IEC 61508, IEC 62304, ISO 26262, 和 EN 50128 等規範
* [賭局催生的計算理論突破](https://www.facebook.com/groups/system.software2025/posts/930113009325501/)
* [太空中心校園徵才](https://www.facebook.com/groups/system.software2025/posts/925892259747576/)，國立成功大學場次安排於 3 月 16 日 (週日) 10:00~15:00

## ChinYikMing
> [Facebook 討論區](https://www.facebook.com/groups/system.software2025/posts/928497669487035/)

上學期修習台大[黎士瑋](https://shihweili.com/)老師開的「虛擬機器」課程。剛好那時在投入 [rv32emu](https://github.com/sysprog21/rv32emu) 的系統模擬(system emulation) 開發。課程中學到的東西也持續引導我如何持續改進 rv32emu，比如能不能支援 vhost 加速 virtio 裝置模擬、巢狀虛擬化 (nested virtualization)，等議題。這些議題較爲進階，可持續關注。

以下提供一些正在或需要改善的地方：
1. 使用 block device 掛載 rootfs 加速開機流程 (`rootfs.cpio` 越來越大會導致解壓縮越來越久進而影響開機速度)。
2. virtio block device 目前預設就是讀寫權限，可擴充 CLI parameter 接受使用者給定的權限。
3. virtio block device 無法直接接受 `/dev` 目錄底下 block device。
4. 擴充 virtio block 後端支援多個 virtio block device。
5. 支援 virtio-net 及其他 virtio 裝置。
6. 改進 RVV extension 的實作和測試流程 (導入現有 CI 或撰寫腳本)。
7. 實作 SMP 多核模擬。
8. 實作 TLB。
9. 在網頁執行系統模擬。

[這份期末簡報](https://docs.google.com/presentation/d/1WC4Z5ydXZEjgjcbfnpQ9HczPS4kMULz_Vu8fM7pI4GY/edit)或許對陸續參與開發 [rv32emu](https://github.com/sysprog21/rv32emu) 的人有些幫助 (至少能夠快速掌握關鍵元件)。簡報內還附 WebAssembly 移植的經驗以及 Emscripten 編譯器 CFLAG 的介紹。

2024 年專題: [實作多核 RISC-V 處理器模擬環境並運作 Linux 核心](https://hackmd.io/@sysprog/HyQ9UQ2E0)

## 重視溝通

課程的目的並非在於訓練工程師，而是培養能與工程師有效溝通的人才。因此，我們對各位未來的期望是：
* 掌握新知識，並善於跨領域聯想與應用；
* 面對待解決的問題時，能夠明確釐清需求，具備評估各種解決方案的能力；
* 能自主進行原型設計，初步驗證創新想法；
* 與專業工程師進行精準溝通，攜手打造最佳解決方案。

> 改寫自 [給我的學生](https://hackmd.io/@howkii-studio/for_my_students)

$\to$ [無效的溝通案例](https://www.facebook.com/groups/Taiwan.AI.Group/permalink/1826672180988548/)，有人即便學習多年的理工，但他人很難從言行看得出其專業。

## 檢討第一週測驗題

為何 Linux 和 FreeBSD 一類 POSIX 相容的作業系統，不直接提供記憶體管理的系統呼叫呢？核心只提供 [brk](https://man7.org/linux/man-pages/man2/brk.2.html), [sbrk](https://man7.org/linux/man-pages/man2/sbrk.2.html), [mmap](https://man7.org/linux/man-pages/man2/mmap.2.html) 等系統呼叫。
> 這裡的 brk 不是 Berkshire Hathaway Inc.

探討記憶體配置器的實作，務必理解 [free list](https://en.wikipedia.org/wiki/Free_list) 的寓意。

參見 [CS107, Lecture 24 Explicit Free List Allocator](https://web.stanford.edu/class/archive/cs/cs107/cs107.1246/lectures/24/Lecture24.pdf)

[Memory allocator](https://github.com/mtrebi/memory-allocators)

## 檢討第二週測驗題

使用 Digit-by-digit 方法，單純加減與位移運算來開平方根。先觀察其規律
$$
(a+b)^2 = a^2+(2a+b)b
$$

三元平方和
$\begin{align}
(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 + (2a+b)b + (2(a+b)+c)c
\end{align}$

四元平方和
$\begin{align}
(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 + (2a+b)b + (2(a+b)+c)c + (2(a+b+c)+d)d
\end{align}$

考慮一般化的平方和
$$
N^2 = (a_n+a_{n-1}+\dots+a_{1}+a_0)^2
$$

觀察規律可以發現 $m$ 元平方和可以藉由 $1$ 到 $m-1$ 元平方和總和，同時加上一項
$$
Y_{m}=\left[\left(2\sum^{n}_{i=m+1} a_{i}\right) + a_{m}\right]a_{m} = \left( 2P_{m+1}+ a_{m}\right)a_{m}
$$
其中 $P_{m+1}=a_n+a_{n-1}+\dots+a_{m+2}+a_{m+1}$ 而 $P_0=N$ 且
$$
P_{m} = P_{m+1} + a_{m},\quad \text{for } 1\leq m<n
$$

總結上述兩個觀察的結果：
1. $n$ 元平方和可以藉由 $1$ 到 $n-1$ 元平方和總和，再加一項 $Y_{n}$
2. $Y_{n}=\left( 2P_{n-1}+ a_n\right)a_n$ 其中 $P_{n-1} = P_{n-2} + a_{n-1}$

數值系統在二進位表示下為：
$$
x = (00b_0b_2\dots b_{n-1}b_n)_2^2
$$

$b_0$ 為最高位為 $1$ 之位元，二進位轉十進位如下：
$$
\sum_{i=0}^n b_i\times 2^{n-i}
$$

假設 $N^2$ 可以用二進位系統逼近：
$$
\begin{align}
N^2
&\approx (b_n\times 2^0 + b_{n-1}\times 2^{1}+\dots b_ 1\times2^{n-1} +b_0\times2^n)^2 \\
&= (a_n + a_{n-1} + \dots a_1 + a_0)^2
\end{align}
$$
其中 $b_i\in\lbrace 0,1\rbrace,\text{ for }i=0,1\dots,n$ 且 $P_m=P_{m+1}+a_{m}=P_{m+1}+b_{m}\times 2^{m}$。故逼近過程只要從 $m=n$ 也就是最高位元為 $1$ 開始計算到最低位元 $m=0$，確認 $a_m=2^m$ 或是 $a_m=0$ 對 $0 \leq m < n$ ，藉由上述 $P_m=P_{m+1}+b_{m}\times 2^{m}$ 可以確認有兩種可能：
$$
P_m=
\begin{cases}
P_{m+1}+2^{m}, &\text{if }P_m^2 \leq N^2,\\
P_{m+1}, &\text{otherwise.}
\end{cases}
$$

舉例來說，設 $N^2=10$ 則 $N^2=(10)_{10}=(1010)_2=(b_3\times2^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-Y_m$ 為差值表實際值與逼近值的誤差，其中 $Y_m=\left( 2P_{m+1}+ a_{m}\right)a_{m}$ 運用以下性質可以縮減上述計算過程：
1. $X_m=N^2-P_m^2=X_{m+1}-Y_m$
2. $Y_m=P_m^2-P_{m+1}^2=(2P_{m+1}+a_m)a_m$

由於 $Y_m=2a_mP_{m+1}+a_m^2$ 與 $a_m=2^m$ 則可以將 $Y_m$ 表示為
$$
Y_m = P_{m+1}2^{m+1} + (2^{m})^2
$$

令 $c_m =2a_mP_{m+1}= P_{m+1}2^{m+1}$ 與 $d_m = a_m^2=(2^{m})^2$ 。重新將 $Y_m$ 表示為
$$
Y_m = dddddd
\begin{cases}
c_m+d_m, &\text{ if }a_m =2^m, \\
0, &\text{ if } a_m = 0.
\end{cases}
$$

同時藉由 $P_{m} = P_{m+1}+a_{m}$ 則
$$
\begin{align}
c_m
&= P_{m+1}2^{m+1} \\
&= (P_m-a_m)2^{m}2 \\
&= 2P_m2^{m} - 2a_m2^{m} \\
&= 2c_{m-1} - 2a_m2^m.
\end{align}
$$

如果 $a_m\neq 0$ 則
$$
c_{m-1} = c_m/2 +d_m.
$$

同時
$$
d_m = (2^m)^2 = (2\times2^{m-1})^2 = 4(2^{m-1})^2
$$

則 $d_{m-1} = d_m/4$。

總結迭代關係為
$$
c_{m-1} =
\begin{cases}
c_m/2 +d_m, &\text{ if } a_m\neq 0, \\
c_m/2, &\text{ if } a_m = 0.
\end{cases}
$$
與
$$
d_{m-1} = d_m/4
$$

則可以藉由 $c_{-1}$ 得知平方根為
$$
c_{-1} = P_02^0 = P_0 = N.
$$

Linux 核心中的整數平方根函數實作於 [lib/math/int_sqrt.c](https://github.com/torvalds/linux/blob/master/lib/math/int_sqrt.c) 中，使用 Digit-by-digit calculation 方法來計算開平方根:

/**
 * int_sqrt - computes the integer square root
 * @x: integer of which to calculate the sqrt
 *
 * Computes: floor(sqrt(x))
 */
unsigned long int_sqrt(unsigned long x)
{
    unsigned long b, m, y = 0;

    if (x <= 1)
        return x;

    m = 1UL << (__fls(x) & ~1UL);
    while (m != 0) {
        b = y + m;
        y >>= 1;

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

    return y;
}

`__fls` 用於找到輸入 x 的最高有效位（Most Significant Bit, MSB），並設定變數 m 為 2 的冪值。接著使用 Digit-by-digit calculation 方法迴圈計算開平方根，直到 m 變為 0。

延伸閱讀: [位元操作的應用](https://hackmd.io/@sysprog/HyhMnoRrA)

[Linux 核心原始程式碼的整數除法](https://hackmd.io/@sysprog/linux-intdiv)

考慮以下 C 程式: (檔名 `div3.c`)

int div3(int x) { return x / 3; }

開啟最佳化編譯:

$ gcc -O3 -S div3.c 

可得到 `div3.s` 的輸出，針對 x86-64 處理器架構:

div3:
	movslq	%edi, %rax
	sarl	$31, %edi
	imulq	$1431655766, %rax, %rax
	shrq	$32, %rax
	subl	%edi, %eax
	ret

原本的「除以 3」去哪？這個 `1431655766` 數值是什麼？

在 Arm64 有類似的輸出:

div3:
	mov	w8, #21846
	movk	w8, #21845, lsl #16
	smull	x8, w0, w8
	lsr	x9, x8, #63
	lsr	x8, x8, #32
	add	w0, w8, w9
	ret

> [出處](https://x.com/Observer_ofyou/status/1889639128611926085)

編譯器最佳化的依據是什麼？

> [出處](https://x.com/Observer_ofyou/status/1886703885269508185)

## 檢討第一份作業
來自學員貢獻的程式碼:
* [Add dummy macros for conditionally defined macros](https://github.com/sysprog21/lab0-c/pull/211): 利用 [bit-field 的特性](https://hackmd.io/@sysprog/c-bitfield)，避免原本因缺乏 `typeof` 運算子 (最初是 GNU extension，後來納入 C23 標準) 而無法定義 `list_for_each_entry` 巨集，致使 Cppcheck 靜態分析拋出錯誤。感謝 [lumynou5](https://hackmd.io/@lumynou5/linux2025-homework1)
* [Clear where non-American English appears](https://github.com/sysprog21/lab0-c/pull/209): Git hook 會檢查訊息是否以美式英語書寫 (公開發表在 GitHub，就是為了讓更多人知道你的創作)，但原本無法指出是哪幾行包含不以美式英語書寫，此修正做出改進。感謝 [Dennis40816](https://hackmd.io/@dennis40816/linux2025-homework1)

案例: [Dennis40816](https://hackmd.io/@dennis40816/linux2025-homework1)

## bevmmf

由於先前 commit 未符合[CONTRIBUTING.md](https://github.com/sysprog21/lab0-c/blob/master/CONTRIBUTING.md) 的規範與七條原則，我針對相對應 commit 進行 `git rabase -i` 加以修正。
首先，針對原先第一條 commit，我應當將 `q_new`, `q_free` 與 `q_insert_head`, `q_insert_tail` 分別置於兩則不同 commit，以達到[CONTRIBUTING.md](https://github.com/sysprog21/lab0-c/blob/master/CONTRIBUTING.md) 中 Git commit style 所要求之
> Each commit should encapsulate a single, coherent change.

以下是更正過後的 commit:
> commit [8e86f02](https://github.com/sysprog21/lab0-c/commit/8e86f021a23810731da423cfa2be18a9e7893c18)
> commit [101ef36](https://github.com/sysprog21/lab0-c/commit/101ef36c3fc5d4de40a2034604526212db79288a)

第二則 commit 應當說明實作手法，例如讓 `q_insert_head` 和 `q_insert_tail` 共用程式碼片段。注意 [CONTRIBUTING.md](https://github.com/sysprog21/lab0-c/blob/master/CONTRIBUTING.md) 的規範:
> Use the body to explain what and why, not how.

再者，對於本來的第二條 commit，我應避免濫用 finish 一詞:
> to complete something or come to the end of an activity:

`q_remove_head` 和 `q_remove_tail` 仍有改進空間。在工程領域，不要輕易說 "finish"。
以下是更正後的 commit :
> commit [91aca2d](https://github.com/sysprog21/lab0-c/commit/91aca2d8c0fac900b52fcc311d58e80a109250ff)

最後，對於原來的第三則 commit，我改進英語書寫。並遵循 [CONTRIBUTING.md](https://github.com/sysprog21/lab0-c/blob/master/CONTRIBUTING.md) 的規範，針對 "what" 與 "how" 進行著重探討。
以下是更正後的 commit :
> commit [3769f55](https://github.com/bevmmf/lab0-c/commit/8e86f02)

如何寫出正確的 git commit message ?

TODO: 改進後，使用 `git rebase -i` 和 `git push --force` 發布於 GitHub，並檢討項目下方列出對應的 commit 超連結

檢討:

From 2eb50d2b59d204dfdfce1418928d1832b3825554 Mon Sep 17 00:00:00 2001
From: bevmmf <[e-mail]>
Date: Mon, 24 Feb 2025 11:09:41 +0800
Subject: [PATCH 1/3] Finish 4 functions :
 q_new,q_free,q_insert_head,q_insert_tail

Through the work on that 4 functions,i get familiar with the doubly
linked list in linux as well as API about list.h.
There is one problem i meet about not initialize the tool pointer like trav on static analysis.
It was solved by initialing.

commit message 的主題 (subject) 列出 4 個函式，沒必要置入於同一 commit，注意 [CONTRIBUTING.md](https://github.com/sysprog21/lab0-c/blob/master/CONTRIBUTING.md) 的規範:
> Group Related Changes Together Each commit should encapsulate a single, coherent change. e.g., if you are addressing two separate bugs, create two distinct commits. This approach produces focused, small commits that simplify understanding, enable quick rollbacks, and foster efficient peer reviews. By taking advantage of Git’s staging area and selective file staging, you can craft granular commits that make collaboration smoother and more transparent.

可將 `q_new` 和 `q_free` 置入同一 commit，而 `q_insert_head` 和 `q_insert_tail` 放入另一 commit。

"There is one problem i meet about not initialize the tool pointer like trav on static analysis." 超過一行 72 個字元的限制，務必更新 `lab0-c` 以得到 Git hooks 的檢查修正。

注意 [CONTRIBUTING.md](https://github.com/sysprog21/lab0-c/blob/master/CONTRIBUTING.md) 的規範:
> Use the body to explain what and why, not how.

應當說明實作手法，例如讓 `q_insert_head` 和 `q_insert_tail` 共用程式碼片段。

檢討:

From 1dc27b39ba6230db3cee5ae72e807fa740ef488b Mon Sep 17 00:00:00 2001
From: bevmmf <[e-mail]>
Date: Mon, 24 Feb 2025 11:57:22 +0800
Subject: [PATCH 2/3] Update 2 functions q_remove_head,q_remove_tail

I finsh the 2 functions :
q_remove_head
q_remove_tail

It is verified with executing qtest and experimenting.
Through doing it,i learn the function strncpy in string.h.

避免濫用 [finish](https://dictionary.cambridge.org/dictionary/english/finish) 一詞:
> to complete something or come to the end of an activity:

`q_remove_head` 和 `q_remove_tail` 仍有改進空間。在工程領域，不要輕易說 "finish"。

檢討:

From e546273f2117f84329b7c4ff9a3343dfb4c2be23 Mon Sep 17 00:00:00 2001
From: bevmmf <[e-mail]>
Date: Tue, 25 Feb 2025 10:05:48 +0800
Subject: [PATCH 3/3] Implement q_reverse and q_swap functions

Successfully implemented q_reverse without issues. However, encountered
problems with q_swap. Initially, execution got stuck, so I used gdb to debug
and discovered an infinite loop.

After reviewing the overall program logic and finding no major structural
issues, I suspected a problem with the swap2node function. I conducted a
static test on swap2node and confirmed a logical error. The issue was that
only the target node was handled without considering its neighboring nodes.
After fixing this, the function now works correctly.

改進英語書寫，這是 ChatGPT 一類的工具可直接幫助你的地方。而且，既然你宣稱使用 GDB，應當分析原本的程式為何會出問題 (可列出 stack frame) 並討論後續處置。

## HenryChaing
這次在課堂上被老師問到關於 `q_swap()` 的實作，重新審視自己的程式碼發現雖然可以運作但是程式碼的可讀性太低，因此這次重新實作 `q_swap()` 加入了 Linux 核心風格的鏈結串列 [API](https://github.com/sysprog21/lab0-c/blob/master/list.h) ， 靈感來自 [2 月 25 日測驗](https://hackmd.io/@sysprog/linux2025-quiz2)。

首先要修正的是老師提到的若鏈結串列為空或 singular 的情況下不用作兩兩互換，可以使用 `list_empty()` 以及 `list_singular()` 作處理。再來是節點兩兩互換的部份，我觀察到了一個好用的操作 `list_move()` ，它可以將指定節點從原本的串列移除並插入到指定串列。

至於 if 條件判斷則是要處理鏈結串列節點個數為奇數的情況，這個部份還可以作修正。
> commit [ca748f4](https://github.com/HenryChaing/lab0-c/commit/ca748f44b88693baea50174df27523be87dc6a22)

void q_swap(struct list_head *head)
{
    list_head *node;

    if (list_empty(head) || list_is_singular(head))
        return;

    list_for_each (node, head) {
        if (node->next != head)
            list_move(node->next, node->prev);
    }

}

接著第二個議題是網頁伺服器與命令列輸入共存的實作，在原先 web.c 實作的 `web_eventmux` 函式當中，會有透過 [read](http://man7.org/linux/man-pages/man2/read.2.html) 系統呼叫來讀取 socket 的內容，但是 read 這個系統呼叫預設為 Blocking-I/O ，因此會影響原先命令列輸入讀取鍵盤內容的功能。
> 參考: [檔案系統概念以及實作手法](https://hackmd.io/@sysprog/linux-file-system#IO-%E4%BA%8B%E4%BB%B6%E6%A8%A1%E5%9E%8B)

Blocking-I/O Model 有分成兩個階段，首先是等待 I/O 資料準備就緒，最後是實際將核心空間的資料搬移到使用者空間。以上述問題來說，我們需要同時等待 socket 以及 keyboard 的資料到來，但是原先的 read 只能等待其中一者，因此我們需要另一個系統呼叫 [select](https://man7.org/linux/man-pages/man2/select.2.html) 。

select 可以同時監視多個 file descripter ，直到其中一者的 I/O 資料準備就緒，隨後再使用 read 系統呼叫讀取在核心空間當中的資料。有了 select 的好處是可以在單工程式中監視多個 I/O 事件。

        struct sockaddr_in clientaddr;
        socklen_t clientlen = sizeof(clientaddr);
        int web_connfd =
            accept(server_fd, (struct sockaddr *) &clientaddr, &clientlen);
            
+        fd_set listenset_2;
+        FD_ZERO(&listenset_2);
+        FD_SET(STDIN_FILENO, &listenset_2);
+        FD_SET(web_connfd, &listenset_2);
+        max_fd = STDIN_FILENO > web_connfd ? STDIN_FILENO : web_connfd;
+        int result = select(max_fd + 1, &listenset_2, NULL, NULL, NULL);
+        if (result < 0)
+            return -1;
+        if (FD_ISSET(STDIN_FILENO, &listenset_2)) {
+            FD_CLR(STDIN_FILENO, &listenset_2);
+            return 0;
+        } else {
+            FD_CLR(web_connfd, &listenset_2);
+        }

請問[自我評量](https://docs.google.com/forms/d/e/1FAIpQLSccoOdvKTelvKHFeU5EGrflHgKa1BUxQhgsCm1fI4HlkXl8eA/viewform)沒滿分，是否就拿不到認證碼。
> 你可對表單反覆提交答覆，直到拿到認證碼為止

## Cheng5840
關於 swap 與 reversek 有什麼相似處 ?
swap 是將整條鏈結串列每兩個節點編隊一組做順序交換，若鏈結串列節點數為奇數個，則不更動最後一個節點。
reverseK 是將整條鏈結串列每 K 個一組，組內順序反轉，所以可以把 swap 當作是 reverseK 在 K=2 的特例。

:::warning
TODO: 善用既有的函式，撰寫更精簡的程式碼。
:::

void q_swap(struct list_head *head)
{
    if (list_empty(head) || list_is_singular(head))
        return;

    struct list_head* cur = head->next, *nextpair;

    while (cur!=head && cur->next!=head) {
        nextpair = cur->next->next;
        list_move(cur, cur->next);
        cur = nextpair;
    }
}

void q_reverseK(struct list_head *head, int k)
{
    if (list_empty(head) || list_is_singular(head) || k == 1)
        return;

    struct list_head *prev = head, *cur, *next;
    int count = q_size(head);

    while (count >= k) {
        cur = prev->next;
        next = cur->next;

        /*
         * Reverse k nodes by moving the i-th node
         * to the front of the k-group each round.
         */
        for (int i = 1; i < k; i++) {
            list_move(next, prev);
            next = cur->next;
        }

        prev = cur;
        count -= k;
    }
}

:::warning
使用指定的程式碼縮排格式，詳見: [CONTRIBUTING.md](https://github.com/sysprog21/lab0-c/blob/master/CONTRIBUTING.md)
:::

外層迴圈將鏈結串列分成 k 個一組，內層迴圈則將該組最後一個節點移至最前面，重複 k-1 輪，如此一來便能達到組內 reverese 的效果。

因為swap 是 reverseK 在 K=2 的特例，因此 `q_swap()` 也可以下述方式實作:

void q_swap(struct list_head *head)
{ 
    q_reverseK(head, 2);
}

## I-Ying-Tsai
從泰勒定理可以得知，假設函數 $f$ 為二次可微連續函數，和 $p$ 為 $f(p) = 0$ 的一解，令 $p_0 = p - h$ 為 $p$ 附近之一點，其中 $h$ 為足夠小的正數，則對 $p_0$ 的一階泰勒多項式為：

$$ 0 = f(p) = f(p_0 + h) = f(p_0) + h f'(p_0) + \frac{h^2}{2} f''(\xi). $$

其中，$\xi$ 位於 $p$ 與 $p_0+h$ 之間。

:::warning
怎樣才能得到 $\frac{h^2}{2} f''(\xi) ?$

在 $p$ 點附近的泰勒多項式逼近為：
$$0 = f(p) = f(p_0 + h) = f(p_0) + h f'(p_0) + \frac{h^2}{2} f''(p_0) + \dots +\frac{h^n}{n!} f^n(p_0)+ \dots$$

不難發現，二階導數項開始每個項對整個函數的值影響非常小(因為 $h$ 足夠小)，於是我們可以嘗試用一個項的形式來表示。

#### **柯西均值定理：**
假設F,G兩函式在閉區間[a,b]連續,在開區間(a,b)可微,且對於所有的 $x \in (a,b)$, $G'(x) \neq 0$, 則至少存在一個 $\xi$ 使得 $\frac{F(b) - F(a)}{G(b) - G(a)} = \frac{F'(\xi)}{G'(\xi)}$

### **證明步驟:**

**Step 1 :**

泰勒展開式的餘項 $R_n$ 定義為：

$$
R_n:=f(p) - \sum_{k=0}^n \frac{f^{(k)}(p_0)}{k!} h^k = \sum_{k=n+1}^\infty\frac{f^{(k)}(p_0)}{k!}h^k
$$

其中：
- $\sum_{k=0}^n \frac{f^{(k)}(p_0)}{k!} h^k$ 是以 $p_0$ 為中心的 $n$ 次泰勒多項式。

---

**Step 2:**

#### **考慮輔助函數 :**

$F(x) = \sum_{k=0}^n \frac{f^{(k)}(x)}{k!} (p - x)^k$
$G(x) = (p - x)^{n+1}$

注意到 $F(p) = f(p)$ 以及 $F(p_0) = \sum_{k=0}^n \frac{f^{(k)}(p_0)}{k!} h^k$

---

**Step3:**

#### **使用柯西均值定理(此處略過證明他們都符合使用該定理的條件) :**
$F(p) - F(p_0)= R_n = \frac{F'(\xi)}{G'(\xi)}[G(p) - G(p_0)]$, 對於 $\xi \in (p_0, p)$

$F'(\xi) = \frac{f^{(n+1)}(\xi)(p-\xi)^{n}}{n!}$
$G'(\xi) = -(n+1)(p-\xi)^{n}$
###
### **$R_n = \frac{f^{(n+1)}(\xi)(p-\xi)^{n}h^{n+1}}{n!(n+1)(p-\xi)^{n}} = \frac{f^{(n+1)}(\xi)h^{n+1}}{(n+1)!}$**

---

### *證明完畢*
:::

其中 $\xi$ 為 $p_0$ 和 $p$ 之間的一點，由平均值定理得來。將 $h$ 的一次項移至等號左側則有：

$$-h f'(p_0) = f(p_0) + \frac{h^2}{2} f''(\xi).$$

只要 $f'(p_0) \neq 0$，等式兩側同除以 $-f'(p_0)$ 得：

$$h = -\frac{f(p_0)}{f'(p_0)} - \frac{h^2 f''(\xi)}{2 f'(p_0)}.$$

故 $p_0 + h$ 可以寫為：

$$p = p_0 + h = p_0 - \frac{f(p_0)}{f'(p_0)} - \frac{h^2 f''(\xi)}{2 f'(p_0)} = p_0 - \frac{f(p_0)}{f'(p_0)} + \mathcal{O}(h^2).$$

:::warning
$\mathcal{O}(h^2)$ 表示剩餘項的量級為 $h^{2}$，即當 $h$ 很小時，剩餘項的大小與 $h^{2}$ 成正比。這意味著，當 $h$ 趨近於 $0$ 時，該項對整體的影響變得非常微小。
:::

從上述推導的過程中，得知 $p$ 點可以由附近點 $p_0$ 與該點斜率和函數值逼近：

$$p \approx p_0 - \frac{f(p_0)}{f'(p_0)}.$$