# 2025q1 Homewor4
contributed by < ibat10clw >

{%hackmd NrmQUGbRQWemgwPfhzXj6g %}

## [2025q1](https://hackmd.io/@sysprog/linux2025-quiz3) 第 3 週測驗題
### 測驗 1
題目實作的是一個儲存 bit 數可隨需求增長的計算系統。

第一個函式 `ceil_div`，要求不使用浮點數達成向上取整的效果

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

觀察 `(n + d) / d` 和 `n / d` 兩者的結果相差為 1，但考慮 `n % d == 0` 的狀況，不需要將結果向上調整，因此使用 `(d - 1)` 來調整 n 的值，可以使 `n % d == 0` 時候不會進位到下一個區間。

接著是 `INTMAX` 的巨集，可以觀察到在下面的程式中有使用到此巨集

void mpi_set_u32(mpi_t rop, uint32_t op)
{
    size_t capacity = ceil_div(32, 31);

    mpi_enlarge(rop, capacity);

    for (size_t n = 0; n < capacity; ++n) {
        rop->data[n] = op & INTMAX;
        op >>= 31;
    }

    for (size_t n = capacity; n < rop->capacity; ++n)
        rop->data[n] = 0;
}

從 `capacity` 的計算可以得知，此處永遠會是 2，代表 `mpi` 結構體中的 `uint32_t *data;` 很可能無法存滿 32 bits 的資料
且結合 `op >>= 31` 的操作，可以發現 `rop->data[n]` 每次都寫入 31 個 bits，因此得出此處的 `INTMAX` 應該為取出 lower 31 bits 的巨集。
`#define INTMAX 0x7fffffff/*BBBB*/`

`CCCC` 的填空出現在 `mpi_mul_naive` 函式中，其內部有個三層的 `for` 迴圈

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` 中的每一筆紀錄，嘗試做長乘法運算

          123
x         456
-------------
          738
         6150
        49200

可以觀察上方的直式，每輪計算時須計算出乘積，之後與先前的結果相加，考慮最大的情況若是 `999 * 999` 這種組合，最終的位數會需要兩者的長度相加，因此 `CCCC` 為 `n + m`

接下來觀察除法實作，此處使用長除法的方式，計算 `mpi` 中的每一個位元

/* Computes the quotient (q) and remainder (r) of n / d. */
void mpi_fdiv_qr(mpi_t q, mpi_t r, const mpi_t n, const mpi_t d)
{
    mpi_t n0, d0;
    mpi_init(n0);
    mpi_init(d0);
    mpi_set(n0, n);
    mpi_set(d0, d);

    if (mpi_cmp_u32(d0, 0) == 0) {
        fprintf(stderr, "Division by zero\n");
        abort();
    }

    mpi_set_u32(q, 0);
    mpi_set_u32(r, 0);

    size_t start = mpi_sizeinbase(n0, 2) - 1;
    
    for (size_t i = start; i != (size_t) -1; --i) {
        mpi_mul_2exp(r, r, 1/*DDDD*/);
        if (mpi_testbit(n0, i) != 0)
            mpi_setbit(r, 0);
        if (mpi_cmp(r, d0) >= 0) {
            mpi_sub(r, r, d0);
            mpi_setbit(q, i);
        }
    }

    mpi_clear(n0);
    mpi_clear(d0);
}

`DDDD` 處理的是餘數的部份，考慮長除法中的一次計算

    3
  -----------
3|105
 | 9
 -----------
   1

這個餘數 1 會跟被除數的下一位數做組合，所以此處的 1 應該視為 10，接著加入 5，下一輪改為計算 `15 / 3`，這是十進位的一個舉例。

對應至二進位同樣也需要將餘數的權重做調整，對應該乘上的數值為 2，所以使用 `mpi_mul_2exp`，將 `mpi` 左移 1 個位元，作為乘 2 的等價操作。

最後的函式為最大公因數的計算，以遞迴處理

void mpi_gcd(mpi_t rop, const mpi_t op1, const mpi_t op2)
{
    if (mpi_cmp_u32(op2, 0) == 0) {
        mpi_set(rop, op1);
        return;
    }

    mpi_t q, r;
    mpi_init(q);
    mpi_init(r);

    mpi_fdiv_qr(q, r, op1, op2);

    mpi_gcd(rop, op2, r);/*EEEE*/

    mpi_clear(q);
    mpi_clear(r);
}

`EEEE` 之處做的事情為 `gcd(a, b) = gcd(b, a % b)` 的操作，所以 `rop` 不變而 `op2` 應取代原 `op1` 的位置，`op2` 則由 `a % b` 的餘數取代。
根據 `mpi_fdiv_qr` 的輸出會將商數和餘數分別存在 `q` 和 `r`，輸入的兩個運算元 `op1` 以及 `op2` 不作更動，因此接下來的遞迴呼叫取出 `op2` 以及商數 `r` 為下一輪計算的目標。