2024q1 Homework4 (quiz3+4)

contributed by < ranvd >

第三周測驗 1

根據 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\to 0$ 的迭代過程中判斷

$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{array}{ll}{c}_m+d_m& \text{if }{a}_m=2^m\\ 0& \text{if }{a}_m=0\end{array}$$ 其中

$c_m=P_{m+1}{2}^{m+1};d_m=(2^m{)}^2$，從這裡可以得知，當

$m=-1$ 時，

$c_{-1}=P_0{2}^0=P_0$，因此

$c_{-1}$ 為

$\lfloor \sqrt{z}\rfloor$，接著可以推導出

$c_m$ 與

$d_m$ 的遞迴關係式。

$$c_m=\{\begin{array}{ll}\frac{c_{m+1}}{2}+d_m& \text{if }{a}_{m+1}=2^{m+1}\\ \frac{c_{m+1}}{2}& \text{if }{a}_{m+1}=0\end{array}$$

$$d_m=\frac{d_{m+1}}{4}$$

因此從上面可以看到

$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\ge 0$ 因此可以透過判斷

$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 中有 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 可以得知當 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 應用案例

代補