# 2025q1 Homework4 (quiz3+4)
contributed by <`leowu0411`>

## 第 3 週測驗題

### q1 precision integer caculation

/* mpi: Multi-Precision Integers */
typedef struct {
    uint32_t *data;                           
    size_t capacity;
} mpi_t[1];

* `mpi[1]` 使此 struct 宣告當被引用時能夠因 c 語言陣列的特性隱式的轉換為指標，節首使用 address of 運算子 `&`
* `capacity` 表有幾個 limb 為 `data` 的長度。

for (size_t i = rop->capacity - 1; i != (size_t) -1; --i) {
        if (rop->data[i])
            break;
        capacity--;
    }

* C 語言中，有號數與無號數的運算，有號會被提升至無號數，故當迴圈終止條件設為 `i >= 0` 時，永遠成立；`i` 會強制使 `-1` 轉型為無號，即 `0xffffffff`，而 MSB 此時為正權重
* 故正確迴圈條件應如上，當 `i == UINTMAX == (size_t)-1`

#### AAAA

static size_t ceil_div(size_t n, size_t d)
{
    return (n + (d - 1)) / d;
}

對整數除法取上高斯，較好理解的方式為
* 假使 n 為 d 的公倍數，「n 距離使商多 1 恰好差 d」則加上 d - 1 也無法使原分母多出一份 d
* 相反，如 n 無法被 d 整除，「n 距離使商多 1 差一正整數 z， 且 z 必然 `<= (d - 1)`」，故加上 d - 1 必定使商加一，即上高斯。

#### BBBB

#define INTMAX 0x7fffffff

#### CCCC

for (size_t n = 0; n < op1->capacity; ++n) { 
        for (size_t m = 0; m < op2->capacity; ++m) {
            uint64_t r = (uint64_t) op1->data[n] * op2->data[m];
            uint64_t c = 0;
            for (size_t k = CCCC; c || r; ++k) {
                if (k >= tmp->capacity)
                    mpi_enlarge(tmp, tmp->capacity + 1);
                tmp->data[k] += (r & INTMAX) + c;
                r >>= 31;
                c = tmp->data[k] >> 31;
                tmp->data[k] &= INTMAX;
            }
        }                                     
    }

* 此 mpi 乘法相對直覺，迭代兩個 `op` 的 limb，首先將 limb 的值相乘的結果存於 `r`
* 接著將 r 差分為 limb 存入 tmp，故 CCCC 應為 `n + m`，定位從哪開始放置此次結果的 limb 位置
* 而 `c` 表示 carry 處理進位，內層迴圈需迭代至 carry 為 0 或者 r 已經被拆分完了
(`1 <=limb(r) <= 3`)