2024 Homework4 (quiz3+4)

contributed by < williamlin0518 >

第三週測驗題

測驗 1

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 >>= AAAA) {
        int b = z + m;
        z >>= BBBB;
        if (x >= b)
            x -= b, z += m;               
    }
    return z;
}

i_sqrt 為找出平方根的函式，用於計算整數 x 的平方根,假設 x 總是正值。這個函數使用了一種名為"二分搜尋法"的算法來計算平方根。

使用一個 for 迴圈遍歷 31 個位元,從最高有效位元開始。

• 計算 m 的初始值為 1UL << ((31 - __builtin_clz(x)) & ~1UL)。
• __builtin_clz(x) 是 GCC 擴充函數,用於計算 x 的前導零的個數。
• 31 - __builtin_clz(x) 得到 x 的最高有效位元索引。
• (31 - __builtin_clz(x)) & ~1UL 確保最低有效位元為 0,這樣可以確保 m 是偶數。

使用 ffs / fls 取代 __builtin_clz

• k = 32 - fls(x)
• m = 1UL << ((k - 1) & ~1UL)

分支/無分支實作

int i_sqrt(int x) {
    if (x <= 1) return x;
    int z = 0;
    for (int m = 1UL << ((32 - fls(x)) - 1 & ~1UL); m; m >>= 1) {
        int b = z + m;
-       z = (z + (x >= b)) * (x >= b) >> 1;
-       x -= b * (x >= b);
       
+       z >>= 1;
+       if (x >= b)
+            x -= b, z += m;
+   }
    return z;
}

平方根運算的程式碼

測驗 2

Bitwise Operations for Division and Modulo by 10

Goal

1. simulate the division tmp / 10 without using the division or modulo operators.
2. Accurate to the first decimal point

Bitwise Operations

range :0~19 make sure 1.90<19/x<1.99 ( Accurate to the first decimal point )

using N = 7 and 13 ( \(\dfrac{13}{2^7}\) = \(0.1015625\) ) to close 1/10
\(tmp\times \dfrac{13}{2^7}\) = \(tmp\times 13/8 \times 8 \div 128\)

question

題目包裝程式碼:

#include <stdint.h>
void divmod_10(uint32_t in, uint32_t *div, uint32_t *mod)
{
    uint32_t x = (in | 1) - (in >> 2); /* div = in/10 ==> div = 0.75*in/8 */
    uint32_t q = (x >> 4) + x;
    x = q;
    q = (q >> 8) + x;
    q = (q >> 8) + x;
    q = (q >> 8) + x;
    q = (q >> 8) + x;

    *div = (q >> CCCC);
    *mod = in - ((q & ~0x7) + (*div << DDDD));   
}

question 1 : uint32_t x = (in | 1) - (in >> 2);, why in need to be odd number?

uint32_t q = (x >> 4) + x; \(q=\dfrac{3}{4}in\div 16+\dfrac{3}{4}in=\dfrac{51}{64}in=0.796875in\)

\(0.796875\approx\dfrac{8}{10}\) so CCCC is 3

((q & ~0x7) + (*div << DDDD)) should equal 10*div, *div * 8 = (q >> 3) << 8 = q & ~0x7 ; so DDDD is 1

撰寫不依賴任何除法指令的 % 9 (modulo 9) 和 % 5 (modulo 5) 程式碼

Modulus without Division, a tutorial

• efficient algorithms for computing the modulus of a number
• a mod m = ((b mod m)[a/b] + (a mod b)) mod m