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

## 2025q1 第 3 週測驗題

### Q1

觀察以下 code 及敘述:

/* ceiling division without needing floating-point operations. */
static size_t ceil_div(size_t n, size_t d)
{
    return AAAA;
}

並根據 function call :

void mpi_set_u64(mpi_t rop, uint64_t op)
{
    size_t capacity = ceil_div(64, 31);
    //...

可得 n > d，n 應為被除數，讓計算直接得 ceiling ，可得`AAAA= (n+d-1)/d`

#define INTMAX BBBB

`BBBB = int最大值 = 2^31-1 = 2147483647 = 0x7fffffff`

// ...
    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;
            }
        }                                     
    }

k為積在 op1 第n位與 op2 第m位相乘的 bit 位 : `CCCC = k = n + m`

// ...
    for (size_t i = start; i != (size_t) -1; --i) {
        mpi_mul_2exp(r, r, 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);
        }
    }

根據function名稱判斷，應是用做r = r * 2^DDDD，因為除法做位移後相減，所以使DDDD=1來完成每回合一位的位移。

根據GCD的輾轉相除以及code判斷:

void mpi_gcd(rop, op1, op2)
{
// To make sure op2 is not zero
// div then get q, r
// Ans : recursion -> mpi_gcd(rop, op2, r)
// ...
}

### Q2

## 2025q1 第 4 週測驗題

## Reference
- [2025q1 第 3 週測驗題](https://hackmd.io/@sysprog/linux2025-quiz3)
- [2025q1 第 4 週測驗題](https://hackmd.io/@sysprog/linux2025-quiz4)