# 2024q1 Homework4 (quiz3+4)
contributed by < `yenshipotato` >

## Quiz3
### 測驗一
* 解釋程式碼運作原理
首先，`m` 被初始化為小於或等於 `x` 的最高 4 的冪。這是通過 bitwise 完成的，即 1UL << ((31 - __builtin_clz(x)) & ~1UL)。 `31 - __builtin_clz(x)` 可以得到 `x` 中最高設定位的位置。使用 `& ~1UL` 清除該位置號碼中的最低有效位，以找到一個偶數位置，從而開始於小於或等於 x 的最高的 4 的冪。這樣可以確保程式從檢查最高有效位開始。

函數的主要部分是一個 `for` 迴圈。在迴圈內部，每次迭代將 `m` 向右移 2 個 bit ，相當於除以 4。接著，計算 `b` 為 `z + m` 。

取 `z` 的一半（即 z >>= 1），這代表我們在前一迭代中已確定的 bits 。

之後用 `if` 來檢查 : 如果 `x` 大於或等於 `b` 的情況。這表示當前位應該設置為 1，因為我們可以從 `x` 中減去 `b` 而不會導致結果的平方大於原始的 `x`。

如果條件成立，`x` 減去 `b`，並把當前位添加到 `z` 的結果中。

這個過程會一直重複，直到 `m` 變成 0，此時所有可能設置的位都已經檢查過了。

最終，結束後的 `z` 就是原始數字 `x` 的整數平方根
### 測驗二
* 參照《Hacker's Delight》和 CS:APP 第二章，解釋上述程式碼運作原理
根據前述證明得知，在對於小於 20 的非負整數 $tmp$ 而言，對 10 做 div 的整數結果將近似於 $\frac{13}{128}tmp$ 的結果，又 $13 = 8+4+1$ ，因此 $\frac{13tmp}{8}$ 可以 bitwise operation 表示，即：

`(tmp >> 3) + (tmp >> 1) + tmp)`

然而右移操作會導致位元資料消失，需要設定變數記憶消失的位元。得出 $13tmp$ 的結果後，右移7位便是 $\frac{13}{128}tmp \approx \frac{tmp}{10}$ 也就是除以 10 的商數。

餘數部分，使用 tmp 減去 10 倍商數 (q*4+q)*2 即為結果。

* 對照 Instruction tables，以分析最初具備除法操作的程式碼和最終完全不依賴除法和乘法的實作程式碼裡頭，指令序列佔用的 CPU 週期數量。

* 練習撰寫不依賴任何除法指令的 % 9 (modulo 9) 和 % 5 (modulo 5) 程式碼，並證明在 uint32_t 的有效範圍可達到等效。

問題僅指定 modulo 的部分，因此我不考慮求商數的部分， % 9 的情況
已知 $2^6\equiv 1 \pmod 9$ ， 可得 2 的冪對 9 取餘數為 6 個 1 循環，利用這個特性
可以建立一個 `mask` 為兩個 1 之間有 5 個 0 ，在 uint32_t 裡，這個數是 `0x41041041` ，將輸入的數與 `mask` 做 &(AND) ，結果中 1 的個數乘上對應的餘數為此次的結果，

    uint32_t tmp=0,x;
    
    x=n&MASK; //0x41041041
    for(;x>0;x>>=6)
        tmp+=x&1UL;
    n>>=1;

最後再對 6 個結果求總和， `tmp` 便與 `n` 同餘(在模為 9 的情況下)。

最後，遞迴呼叫此函式，終止條件為輸入 `n` 小於 9 。詳細程式碼在 [Github](https://github.com/yenshipotato/2024q1_HW4/blob/main/mod9.c)

證明：
由於題目的要求明確指出「在 uint32_t 的有效範圍可達到等效」，在證明範圍有限的情況下可以使用 [Proof by exhaustion](https://en.wikipedia.org/wiki/Proof_by_exhaustion) 證明，經測試程式窮舉，

    int main()
    {
        for(uint32_t i=0;i<UINT32_MAX;i++){
            if(mod9(i)!=i%9)
                printf("Error %u %u\n",mod9(i),i%9);
        }
        if(mod9(UINT32_MAX)!=UINT32_MAX%9)
                printf("Error %u %u\n",mod9(UINT32_MAX),UINT32_MAX%9);
        printf("Suc");
        return 0;
    }

沒有錯誤訊息，得證所實作的 `mod9` 「在 uint32_t 的有效範圍可達到等效」。

同理， $2^4\equiv 1 \pmod 5$ ，可得 2 的冪對 5 取餘數為 4 個 1 循環，只要修改上述程式碼即可達到同樣效果。[詳細程式碼](https://github.com/yenshipotato/2024q1_HW4/blob/main/mod5.c)

### 測驗三
### 測驗四
### 測驗五

## Quiz4
### 測驗一
### 測驗二
### 測驗三