2024q1 Homework4 (quiz3+4)

Quiz 3

測驗一

延伸問題：

1. 解釋上述程式碼運作原理並重新整理數學式 (原題目故意略去某些細節)，並嘗試用第 2 週測驗題提到的 ffs / fls 取代 __builtin_clz，使程式不依賴 GNU extension，且提供分支和無分支 (branchless) 的實作。
2. 在 Linux 核心原始程式碼找出對整數進行平方根運算的程式碼，並解說其應用案例，至少該包含 block 目錄的程式碼。
3. 閱讀〈Analysis of the lookup table size for square-rooting〉和〈Timing Square Root〉，嘗試撰寫更快的整數開平分根運算程式。

測驗二

延伸問題：

1. 參照《Hacker's Delight》和 CS:APP 第二章，解釋上述程式碼運作原理，並對照 Instruction tables，以分析最初具備除法操作的程式碼和最終完全不依賴除法和乘法的實作程式碼裡頭，指令序列佔用的 CPU 週期數量。
2. 練習撰寫不依賴任何除法指令的 % 9 (modulo 9) 和 % 5 (modulo 5) 程式碼，並證明在 uint32_t 的有效範圍可達到等效。
3. 實作不同於《Hacker's Delight》的程式碼

測驗三

延伸問題:

1. 解釋上述程式碼運作原理
2. 在 Linux 核心原始程式碼找出 log2 的相關程式碼 (或類似的形式)，並解說應用案例

測驗四

延伸問題:

1. 解釋上述程式碼運作原理
2. 在 Linux 核心原始程式碼找出 EWMA 的相關程式碼 (或類似的形式)，並解說應用案例，至少該涵蓋無線網路裝置驅動程式。
3. 可對照〈圖解傅立葉分析〉

測驗五

延伸問題:

1. 解釋上述程式碼運作原理
2. 改進程式碼，使其得以處理 x = 0 的狀況，並仍是 branchless
3. 在 Linux 核心原始程式碼找出 ceil 和 log2 的組合 (類似的形式)，並解說應用案例 (提示: 在 Linux 核心排程器就有)

Quiz 4

測驗一

延伸問題：

1. 參照《Hacker's Delight》和 CS:APP 第二章，解釋上述程式碼運作原理。
2. 不依賴 popcount，嘗試以上述歸納的規則，針對 LeetCode 477. Total Hamming Distance 撰寫出更高效的程式碼。

測驗二

延伸問題：

1. 參照《Hacker's Delight》和 CS:APP 第二章，解釋上述程式碼運作原理。
2. 將上述手法應用於第三次作業中，追求更有效的賽局判定機制。

測驗三

延伸問題:

1. 解釋上述程式碼運作原理
2. 指出上述程式碼可改進之處，特別跟 AVL tree 和 red-black tree 相比，並予以實作

   考慮到循序輸入和亂序輸入的狀況

3. 設計效能評比程式，探討上述程式碼和 Linux 核心 red-black tree 效能落差