contributed by <eleanorLYJ>

第 3 週測驗題

測驗 1 平方根

除了測驗題上的敘述，也閱讀Digit-by-digit calculation: 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{array}{ccccc}{a}_0{a}_0& a_0{a}_1& a_0{a}_2& ...& a_0{a}_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{array}\right]$$

$$N^2=a_0{a}_0+(a_0{a}_1+a_1{a}_0+a_1{a}_1)+(a_0{a}_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}_i{a}_j={a_0}^2+(a_1\ast (a_0+a_1+a_0))+(a_2\ast (a_0+a_1+a_2+a_1+a_0))+...={a_0}^2+(a_1\ast (2a_0+a_1))+(a_2\ast (2a_0+2a_1+a_2))+...+a_n\ast [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\ast (2P_1+a_1))+(a_2\ast (2P_2+a_2))+...+(a_n\ast (P_{n-1}+a_n))$ 。

$P_m$ 會有兩種情況

$$\begin{array}{rl}{P}_m& =\{\begin{array}{l}{P}_{m-1}+2^m\text{, if }{P_m}^2\le N^2\\ P_m,\text{ otherwise}\end{array}\end{array}$$

這算 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{array}{rl}{P_m}^2& ={a_0}^2+{a_1}^2+...{a_{m-1}}^2+{a_m}^2+2a_0{a}_1+...+2a_0{a}_{m-1}+2a_0{a}_m+2a_1{a}_{m-1}+2a_1{a}_m\\ {P_{m-1}}^2& ={a_0}^2+{a_1}^2+...{a_{m-1}}^2+2a_0{a}_1+...+2a_0{a}_{m-1}+2a_1{a}_{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{array}$$
接著在維基百科中說: 將

$Y_m$ 看成兩部分

$c_m$ 與

$d_m$

$$\begin{array}{rl}{c}_m& =2a_m{P}_{m-1}\\ d_m& ={a_m}^2=(2^m{)}^2=2^{2m}\\ Y_m& =\{\begin{array}{ll}{c}_m+d_m,& \text{if }{a}_m=2^m\\ 0,& \text{if }{a}_m=0\end{array}\end{array}$$

接著看如何迭代

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

以下程式的變數意義:

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;       
}