# linux2025-homework4 (quiz3+4)
contributed by < [fcu-D0812998](https://github.com/fcu-D0812998) >
## [第三週測驗題](https://hackmd.io/@sysprog/linux2025-quiz3#%E6%B8%AC%E9%A9%97-1)

### 測驗一

/* ceiling division without needing floating-point operations. */
static size_t ceil_div(size_t n, size_t d)
{
    return (n+d-1)/d;
}
#define INTMAX 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 = n+m; 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;
        }
    }                                     
}

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

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);                                     

    mpi_clear(q);
    mpi_clear(r);
}