# 2024q1 Homework4 (quiz3+4)
**contributed by < `RRbell1027` >**
## 第 3 週測驗題
### 測驗一
### 測驗二
* 目標：對有限範圍(1-19)內的被除數的除法(10)和取餘優化。
* 首先，取餘可以被表示成：

int r, a, b

- r = a % b
+ r = a - b * [a / b]

* 除法當中，當被除數為 2 的冪時，可以被「右移」代替為：

int q, a, b

- q = a / b
+ q = a >> log2(b)

* 任何乘法皆可用「左移」、「右移」和「加法」替換，舉例來說：
$$
\begin{gather*}
n \times 13 \\
13_{10} = 1101_{2}\\
n \times 13 = (n \ \verb|<<| \ 3) + (n \ \verb|<<| \ 2) + n \\
\end{gather*}
$$

* 為了避免 overflow ，將右式除 8 加總後在乘 8 回去。(先除後乘會損失部份位元，要加回去。)

$$
\begin{gather*}
d_0 = n \ \verb|&| \ 0b1 \\
d_1 = n \ \verb|&| \ 0b11 \\
d_2 = n \ \verb|&| \ 0b111 \\
n \times 13 = (n + (n \ \verb|>>| \ 1) + (n \ \verb|>>| \ 3)) \ \verb|<<| \ 3 + d_0 + d_1 + d_2
\end{gather*}
$$
> [time=Tue, Apr 2, 2024 12:30 PM]照我的理解這裡do, d1, d2 應該是從 n 得來的，但是第三周測驗題的公式卻是從 q 得出 d0, d1, d2 。這裡寫上我認為版本。

* 結合這兩項，我們可以將除法 10 當成乘以分子為 1 的分數 $\frac{1}{10}$，找出 2 的冪的分母 128，以及能讓結果接近的分子 13。
$$
\frac{1}{10} \approx \frac{13}{128}
$$

* 如此就能優化掉除法了。

#include <stdint.h>
#include <stdio.h>
/* Find the quotient and remainder when dividing by 0 to 19 */
int main()
{
    for (int n = 0; n <= 19; n++) {
        unsigned q, r;
        d0 = n & 0b1; /* quiz3: d0 = q & 0b1; */
        d1 = n & 0b11;
        d2 = n & 0b111;
        /* q = n * 13 / 128 */
        q = ((((n >> 3) + (n >> 1) + n) << 3) + d0 + d1 + d2) >> 7;
        /* r = n - q * 10 */
        r = n - (((q << 2) + q) << 1);
        printf("q: %d r: %d\n",  q, r);
    }
    
    return 0;
}

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

## 第 4 週測驗題
### 測驗一
### 測驗二
### 測驗三