2025q1 Homework4 (quiz3+4)

contributed by <kk908676>

第 3 週測驗題

測驗 一 :

參考答案

• AAAA = (n+d-1)/d
• BBBB = 0x7fffffff
• CCCC = n+m
• DDDD = 1
• EEEE = mpi_gcd(rop,op2,r)

程式碼運作原理

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

這是經典的「整數實現的向上除法」，避免使用浮點數：

• 若 n 可被 d 整除則剛好，否則就進一格
• 應用在需要知道至少要幾格能裝下 n 單位，每格能裝 d 單位的場景

#define INTMAX 0x7FFFFFFF  // ← BBBB，31 bits all 1s

由於這個 MPI 實作是以 31-bit 為單位儲存每一段數字（因為乘法可能會進位到第 32 位），所以這個掩碼用來確保每段最大為 2^31 - 1。

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) {  // ← CCCC = n + m
            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 個數

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

每輪都要把 r 乘以 2，並把 n 的第 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);  // ← EEEE

    mpi_clear(q);
    mpi_clear(r);
}

這是經典的輾轉相除法（Euclidean Algorithm）：

gcd(a, b) = gcd(b, a % b)

程式中：

• op1 % op2 → 餘數儲存在 r
• 然後用 op2, r 作為下一輪輸入

測驗 二 :