# 2024q1 Homework4 (quiz3+4)
contributed by < [ranvd](https://github.com/ranvd) >

## 第三周測驗 1
根據 [Digit-by-digit calculation](https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Digit-by-digit_calculation) 的方法，一個數字 $Z$ 可以表示為 $(x+y)^2$，假設以 10 為底的話 $Z=(a_n+\cdots+a_0)^2$ 其中 $a_m=10^m$ 或 $0$，同樣的方式可以推廣至以 2 為底。如果將整個公式展開的可以表示成下面公式 $$Z=a_0^2+[2a_0+a_1]a_1+[2(a_0+a_1)+a_2]a_2+\cdots+[2(\sum_{i=0}^{n-1}a_i)+a_n]a_n$$

接著假設 $P_m=(a_n+\cdots+a_m);\;Z=P_0^2$，其中 $a_i$ 代表 $2^i$ 或 $0$，因此可以列出遞迴關係式 $P_m=P_{m+1}+a_m$。在 $m$ 從 $n\to0$ 的迭代過程中判斷 $P_m^2$ 是否大於 $Z$ 即可判斷 $a_m$ 是 0 或 $2^m$。但為了不要每次都重新做平方運算，因此定義 $X_m=Z-P_m^2$，並列出遞迴關係式 $$X_m=X_{m+1}-Y_m$$，其中 $Y_m=P_m^2-P_{m+1}^2=2P_{m+1}a_m+a_m^2$。

又可以將 $Y_m$ 拆解成 $$Y_m=\begin{cases}c_m + d_m & \text{if }a_m=2^m\\ 0&\text{if }a_m=0\end{cases}$$ 其中 $c_m=P_{m+1}2^{m+1};d_m=(2^m)^2$，從這裡可以得知，當 $m=-1$ 時，$c_{-1}=P_02^0=P_0$，因此 $c_{-1}$ 為 $\lfloor\sqrt{z}\rfloor$，接著可以推導出 $c_m$ 與 $d_m$ 的遞迴關係式。 $$c_m=\begin{cases}{c_{m+1}\over 2}+d_m&\text{if }a_{m+1}=2^{m+1}\\{c_{m+1}\over 2}&\text{if } a_{m+1}=0\end{cases}$$ $$d_m={d_{m+1}\over4}$$

因此從上面可以看到 $X_{n}=X_{n+1}-Y_{n+1}=X_n-c_{n+1}+d_{n+1}$，其中 $d_{n+1}=4^{n+1}$ 因此在初始化時須將其設為不超過 x 且為 4 的冪的數值。因此才會使用 `int d = 1UL << ((31 - __builtin_clz(x)) & ~1UL)` 做初始化。由於 $X_{m}\ge0$ 因此可以透過判斷 $X_{m+1}-Y_m$ 來判斷 $a_{m+1}=2^{m+1}\text{ or } 0$，並根據上述的公式來更新數值。

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

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

### 使用 fls 取代 `__builtin_clz`
依據上述題到的內容，`int d = 1UL << ((31 - __builtin_clz(x)) & ~1UL)` 是要找出不大於 x 的最大 4 的冪。因此透過 fls 就可以正確的找出正確的數值，如下更動。

+    int d = 1UL << (fls(x)-1 & ~1UL)
-    int d = 1UL << ((31 - __builtin_clz(x)) & ~1UL)

## 第三周測驗 2

## 第三周測驗 3
透過判斷 `i` 是否大於 $2^{n}$ 來減少運算的次數，之所以 $n$ 使用 16, 8 ,4, 1 的方式是使用了二分搜尋的概念，減少需判斷的次數。

### Linux 應用案例
在 [include/linux/log2.h](https://github.com/torvalds/linux/blob/master/include/linux/log2.h) 中有 log2 相關的實做。使用 `fls` 函式實做。

## 第三周測驗 4

## 第三周測驗 5
`ceil_ilog2` 與 `ilog2` 的不同在於，`ceil_ilog2` 是 $\lceil\log_2(x)\rceil$ 而 `ilog` 是 $\lfloor\log_2(x)\rfloor$。這導致 ceil_ilog2 不能直接使用 fls 找出最高為 1 的 bit。例如 `ceil_ilog2(0b1000)=3` 而 `ceil_ilog2(0b1001)=4`。

因此可以在取 log 之前先將數值減 1，這可以讓數值剛好是 $2^n$ 的資料取 log 後比原本還要小 1，但對於數值不等於 $2^n$ 的資料則不會有影響。因此在取完 log 後再無條件加 1 就可以得到 $\lceil\log_2(x)\rceil$。

### 改進程式碼
參考 [include/linux/log2.h](https://elixir.bootlin.com/linux/latest/source/include/linux/log2.h#L21) 可以得知當 `n == 0` 時，ilog2 回傳的數值為 -1。因此以下改進也會遵循此規則。

static __always_inline __attribute__((const))
int __ilog2_u32(u32 n)
{
	return fls(n) - 1;
}

目前的實作有兩個缺陷，第一個是 `n==0` 時，函式的回傳值為 32，應該要為 -1；第二個是 `n==1` 時，函式的回傳值為 1，應該為 0。

根據上述的規則套用到現在的程式碼上，可以理解為當 `n==1` 時，最後回傳時不需要加 1；同時，因為 `n==0` 時必須回傳 -1，因此可以考慮讓 `n==0` 時的運算結果等於 1，接著再做二補數，也就是讓 0 直接取 log 後在加上 1，最後再進行反轉，即可得到 -1。

int ceil_ilog2(uint32_t x)
{
    uint32_t r, shift;
+    uint32_t t = x;
-    x--;
+    x -= !!t;
    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;  
+    return (((r | shift | x > 1) + !!(t-1)) ^ -!t) + !t ;
}

### Linux 應用案例
> 代補