# 2024q1 Homework4 (quiz3+4) contributed by < `yan112388` > ## 2024q3 第 3 週測驗題 ### 測驗一 [連結](https://hackmd.io/@sysprog/linux2024-quiz3) **程式碼解釋** 計算非負整數 `N` 的平方根 1. **版本一**： 使用 `log2(N)` 含式來計算 `N` 的以 2 為底的對數，並將結果轉換為整數，儲存在 `msb` 中，藉此得到 `N` 的最高非零位的位置 **版本二**： 使用　`while`　迴圈，將數字 `N`　右移（相當於將數字除以 2），直到剩下最高的非零位元，得到該位置 3. 計算 `a = 1 << msb`，這等同於設置 `a` 為 2 的 `msb` 次方，此值將作為初始步長 4. `result` 被初始化為 0，將用來儲存最終的平方根 5. 使用`while` 迴圈，只要 `a` 不為 0，迴圈就會繼續。在每次的迭代中： a. 它檢查 `(result + a) * (result + a)` 是否小於或等於 `N`，相當於檢查 `(result + a)` 的平方是否小於或等於 `N` b. 如果上述條件成立，那麼 `a` 被加到 `result` 上，因為 `(result + a)` 仍然是 `N` 的平方根的下界 c. 無論上述條件是否成立，`a` 都會被右移一位，相當於將 `a` 除以 2，藉此將搜尋的步長做調整 5. 當 `a` 變為 0 時，迴圈結束，此時 `result` 包含了 `N` 的平方根的整數部分 6. 回傳 `result` **版本三**： 以　Digit-by-digit calculation　方式，數學式的原理與細節尚未搞懂，待釐清。 ### 測驗二 目的：計算 `in` 除以 10 的商和餘數，並將結果儲存在 `div` 和 `mod` 中 程式碼如下： ```c uint32_t x = (in | 1) - (in >> 2); /* div = in/10 ==> div = 0.75*in/8 */ ``` ``` (in | 1) - (in >> 2) = in + 1 - (in >> 2) = in + 1 - (in / 4) = 0.75 * in + 1 ``` * 欲計算 `in` 除以 10，10 可以表達為 `1.25 * 8`，所以我們可以先計算` 0.75 * in`，接著除以 8，就可以得到`in` 除以 10 的近似值 * `(in | 1)` 亦即 `in + 1`，作用為將 `in` 的最低位元設為 1。 * 如果 in 是奇數， 則 `(in | 1) = in` * 如果 in 是偶數，則 `(in | 1) = in + 1` 可以將此操作看成是一種數值的修正，計算` 0.75 * in` 時，實際上是在計算 `3 * in / 4`。當 `in` 是奇數時，此算數為精確的。但是當 `in` 是偶數時，由於我們進行了除法並向下取整數，結果會比實際的 `0.75 * in` 略小，加 1 可以補償這個誤差。 ```ｃ uint32_t q = (x >> 4) + x; x = q; q = (q >> 8) + x; q = (q >> 8) + x; q = (q >> 8) + x; q = (q >> 8) + x; ``` * 每一行 `q = (q >> 8) + x` 都相當於將 `q` 除以 256，256 可以表達為 2 的 8 次方。在此有 4 行，表示將 x 除以 2 的 32 次方。 ```c *div = (q >> 3); *mod = in - ((q & ~0x7) + (*div << 1)); ``` * 為了得到商數，將 `q` 右移 3 個位元，即提取 q 的高位元作為商。 ``` (*div << DDDD) ≈ in / 10 * 2 = 0.2 * in+ ``` * 計算餘數部分，希望計算 in 除以 10 的餘數，於是我們需要從 in 中減去 *div * 10`((q & ~0x7) + (*div << 1))` 亦同於 `div * 8 + *div * 2` ### 測驗三 計算以 2 為底的對數 **版本二**： ``` c static size_t ilog2(size_t i) { size_t result = 0; while (i >= 65536) { result += 16; i >>= 16; } while (i >= 256) { result += 8; i >>= 8; } while (i >= 16) { result += 4; i >>= 4; } while (i >= 2) { result += 1; i >>= 1; } return result; } ``` 使用了二分搜法的想法 * 檢查輸入是否大於等於 65536（$2^{16}$） * 如果是，將結果加上 16，並將　`i`　右移 16 位，代表著將其範圍縮小到原來的 1/65536 重複此過程，檢查輸入是否大於等於 256（$2^8$）、16 ($2^4$) 及 $2$。每次檢查成功，就將結果加上相應的值（$8、4、1$），並將　`i`　右移相應的位數。 **版本三** ```　ｃ int ilog32(uint32_t v) { return (31 - __builtin_clz(v | 1)); } ``` * 利用了 GCC 的內建函數 `__builtin_clz`，其功能為找到 x 最高位數前面有幾個 0 ， x 為 0 時，未定義。 * 對於一個 32 位的數字 v，`31 - __builtin_clz(v)` 就等於 v 的最高非零位的位置，也就是 `floor(log2(v))`。 * 為了處理　`__builtin_clz(0)` 是未定義的這種問題，使用了 `v | 1` 而非 `v`。　`v | 1` 的作用是將 `v` 的最低位設為 1，確保了進入 __builtin_clz is never的輸入永遠非０。 ### 測驗四 EWMA 數學式展開如下： \begin{aligned} S_t &= \alpha Y_t + (1 - \alpha) \cdot S_{t-1} \\ &= \alpha Y_t + (1 - \alpha)(\alpha Y_{t-1} + (1 - \alpha) \cdot S_{t-2}) \\ &= \alpha Y_t + (1 - \alpha)(\alpha Y_{t-1} + (1 - \alpha)(\alpha Y_{t-2} + (1 - \alpha) \cdot S_{t-3})) \\ &= \alpha (Y_t + (1 - \alpha) Y_{t-1} + (1 - \alpha)^2 Y_{t-2} + \ldots + (1 - \alpha)^k Y_{t-k} + \ldots + Y_0) \end{aligned} ```c struct ewma *ewma_add(struct ewma *avg, unsigned long val) { avg->internal = avg->internal ? (((avg->internal << avg->weight) - avg->internal) + (val << avg->factor)) >> avg->weight : (val << avg->factor); return avg; } ``` * $S_t$　表示時間 $t$ 時的EWMA值，對應程式碼中的 `avg->internal`　 * $Y_t$　表示時間 $t$ 時的資料點，對應程式碼中的 `val`　 * $\alpha$　為一係數，用來控制新樣本值的權重，即 $(1 - 2^{-weight})$， 流程： * 先判斷 internal 是否為零 * 若為零則表示這是第一個資料點，將 `val` 值乘以 $2^{factor}$，作為初始的 EWMA 值 `(val << avg->factor)` * 非零則代表已經有資料點被加入到 EWMA 公式中 * 將 `internal` 值乘以 $2^{weight}$ 再減去 `internal` ，得到$(2^{weight} - 1) \cdot S_{t-1}$ ，對應於公式中的$(1 - \alpha) \cdot S_{t-1}$ * `val << avg.factor` 將新的樣本值 `val` 左移 `avg->factor` 位，相當於將其乘以 $2^{factor}$ 進行縮放，對應於公式中的 $\alpha Y_t$ * 將前述兩項相加，得到 $(2^{weight} - 1) \cdot S_{t-1} + 2^{factor} \cdot Y_t$，最後將結果右移 `avg->weight` 位，相當於除以 $2^{weight}$ **Q：為甚麼 $(2^{weight} - 1) \cdot S_{t-1}$ 會對應於公式中的 $(1 - \alpha) \cdot S_{t-1}$ ?** 欲求 $(1 - \alpha) \cdot S_{t-1}$，將之展開，得到： \begin{aligned} (1 - \alpha) \cdot S_{t-1} &= (1 - (1 - 2^{-weight})) \cdot S_{t-1} \\ &= 2^{-weight} \cdot S_{t-1} \end{aligned} 程式碼中： \begin{aligned} (2^{weight} - 1) \cdot S_{t-1} &= (2^{weight} - 2^0) \cdot S_{t-1} \\ &= (2^{weight} - 2^{weight} \cdot 2^{-weight}) \cdot S_{t-1} \\ &= 2^{weight} \cdot (1 - 2^{-weight}) \cdot S_{t-1} \\ &= 2^{weight} \cdot \alpha \cdot S_{t-1} \\ \end{aligned} 最後，將 $(2^{weight} \cdot \alpha \cdot S_{t-1})$ 除以 $2^{weight}$： \begin{aligned} \frac{2^{weight} \cdot \alpha \cdot S_{t-1}}{2^{weight}} &= \alpha \cdot S_{t-1} \\ &= (1 - 2^{-weight}) \cdot S_{t-1} \end{aligned} ## 2024q3 第 4 週測驗題