contributed by <`eleanorLYJ`>

## [第 3 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz3)
### 測驗 1 平方根

除了測驗題上的敘述，也閱讀[Digit-by-digit calculation: Binary numeral system (base 2)](https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Binary_numeral_system_(base_2))

> 本筆記的變數的下標與作業說明順序相反

把 N 看為 某 bit pattern 的平方, 其中 $a_i$ 可能是 $a^i$ 或 0。我將 $2_i$ 想成 2 的冪的係數

$$N^2 = (a_0+a_1+a_2+...+a_n)^2$$

$$
N =\left[\begin{matrix}
a_0a_0 & a_0a_1 & a_0a_2 &... & a_0a_{n}\\
a_{1}a_{0} & a_{1}a_{1} & a_{1}a_{2}&... & a_{1}a_{n}\\
a_{2}a_{0} & a_{2}a_{1} & a_{2}a_{2}&... & a_{2}a_{n}\\
⋮ & ⋮ & ⋮ & ⋮ & ⋮\\
a_{n}a_{0} & a_{n}a_{1} & a_{n}a_{2} &... &a_{n}a_{n} \\
\end{matrix}\right]
$$
$$
N^2 = a_0a_0 + ( a_0a_1+a_1a_0+ a_1a_1) +(a_0a_2 +a_{1}a_{2} +a_{2}a_{2}+a_{2}a_{1}+a_{2}a_{0}) +...+ \sum_{i=0}^{n-1} \sum_{j = n-1}^{0} a_ia_j
={a_0}^2+ (a_{1}*(a_0+a_1+a_0)) + (a_{2}*(a_0+a_1+a_2+a_1+a_0)) +...
={a_0}^2+ (a_{1}*(2a_0+a_1)) + (a_{2}*(2a_0+2a_1+a_2)) + ...+ a_n*[2 \sum_{i=0}^{n-1}a_i+a_n]
$$

設$P_k = a_0+ a_1 +a_2+..+a_k = \sum_{i=0}^{k}a_i$

故
$N^2 = a_0 + (a_1*(2P_1+a_1))+ (a_2*(2P_2+a_2)) +...+ (a_n*(P_{n-1}+a_n))$ 。

$P_m$ 會有兩種情況

$$
\begin{aligned}
P_m &= \begin{cases}
P_{m-1} +2^m \text{, if } {P_m}^2 \leq N^2 \\
P_m, \text{ otherwise}
\end{cases}
\end{aligned}
$$

這算 n~0 逐一算 $N^2 - {P_m}^2$,得知 m 等於多少時，使 $P_m$ 值最接近 $\sqrt{N}$

為了避免不要不斷的去算出${P_m} ^2$，所以改成僅存每一輪的差異， $X_{m} = N^2 - {P_m}^2$。

$X_m$ 的更新為: $X_m= X_{m-1}-Y_{m}$
而 Y 的定義為上一輪的 P 與此輪的 P 的差異:
$$Y_m = {P_m}^2 - {P_{m-1}}^2 = 2a_m{P_{m-1}} + a_m^2$$

這裡的推導

$$
\begin{aligned}
{P_m}^2 &= {a_0} ^2 + {a_1}^2 + ... {a_{m-1}}^2+ {a_m}^2 + 2a_0a_1 + ...+2a_0a_{m-1}+2a_{0}a_{m}+2a_1a_{m-1}+2a_1a_{m} \\
{P_{m-1}}^2 &= {a_0}^2 + {a_1}^2 + ... {a_{m-1}}^2 + 2a_0a_1 + ...+2a_0a_{m-1}+2a_1a_{m-1} \\
{P_m}^2 - {P_{m-1}}^2 &= {a_m}^2 +2a_m(a_0+...+a_{m-1})\\
Y_m &= 2a_m{P_{m-1}} + {a_m}^2 \\
\end{aligned}
$$
接著在維基百科中說: 將 $Y_m$ 看成兩部分 $c_m$ 與 $d_m$

$$
\begin{aligned}
c_m &= 2a_m{P_{m-1}} \\
d_m &= {a_m}^2 = (2^m)^2 = 2^{2m}\\
Y_m &= \begin{cases}
c_m+d_m, & \text{if } a_m=2^m \\
0, & \text{if } a_m=0 \\
\end{cases}\\
\end{aligned}
$$

接著看如何迭代
<!-- $Y_{m_1}$有相同嗎??Y_{m-1} &= 2 a_{m-1} P_{m-2} + {a_{m-1}}^2 \\ -->
$$
\begin{aligned}
P_m &= P_{m-1}+a_m\\
c_{m-1} &= 2a_{m-1} P_{m-2}= \frac{c_m}{2} +d_m \\
d_{m-1} &= {a_{m-1}}^2 = 2^{2(m-1)} = \frac{d_m}{4}\\
Y_{m-1} &= \begin{cases}
c_m/2+d_m, & \text{if }a_m=2^m \\
c_m/2, & \text{if } a_m=0 \\
\end{cases}\\ \\
\end{aligned}
$$

以下程式的變數意義:
:::info
b = $y_m$ = $P_m$ - $P_{m-1}$
z = $c_m$
m = $d_m$
x = $X_m = N^2 - {P_m}^2$
:::

int i_sqrt(int x)
{
    if (x <= 1) /* Assume x is always positive */
        return x;

    int z = 0;
    for (int m = 1UL << ((31 - __builtin_clz(x)) & ~1UL); m; m >>= 2) {
        int b = z + m;
        z >>= 1;
        if (x >= b) 
            x -= b, z += m;               
    }
    return z;
}

### 測驗 3 ilog2()
用二分搜尋法尋找 Most Significant Bit (MSB)

static size_t ilog2(size_t i)
{
    size_t result = 0;
    while (i >= AAAA) {
        result += 16;
        i >>= 16;
    }
    while (i >= BBBB) {
        result += 8;
        i >>= 8;
    }
    while (i >= CCCC) {
        result += 4;
        i >>= 4;
    }
    while (i >= 2) {
        result += 1;
        i >>= 1;
    }
    return result;
}

### 測驗 5 ceil_log2
一開始的 `x` 減1 是為了確保結果向上進位到下一個整數。而 `r` 用於累加位移位元數。

該程式碼會迭代`x`多次，檢查特定的位元模式。它使用移位操作從中刪除已檢查的位元`x`。首先檢查最高位元 (MSB > 16)，接著每次檢查的位元都除以2。 最終有考量最後 x 等於 2 或 3 的情況會進位，而最終 x 等於 1 時不會進位

int ceil_ilog2(uint32_t x)
{
    uint32_t r, shift;
    x--;
    r = (x > 0xFFFF) << 4;                               
    x >>= r;
    shift = (x > 0xFF) << 3;
    x >>= shift;
    r |= shift;
    shift = (x > 0xF) << 2;
    x >>= shift;
    r |= shift;
    shift = (x > 0x3) << 1;
    x >>= shift;
    return (r | shift | x > 1) + 1;       
}