# 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` 中

程式碼如下：

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 次方。

*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 為底的對數
**版本二**：

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}

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 週測驗題