2025q1 Homework4 (quiz3+4)

contributed by <bevmmf>

預期目標

檢驗學員對於 bitwise 操作及 rbtree 的熟悉程度
檢驗學員對於 CS:APP 第二章的掌握：別忘了課程指定的教科書
引導學員接觸 Linux 核心原始程式碼及解說應用案例

quiz3

測驗一

補完程式碼

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

解釋上述程式碼運作原理

#include <inttypes.h> //support int32_t, uint64_t 
#include <stdint.h> //support uint32_t, int64_t

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

Essential Knowledge
- size_t : 一個專為表示「大小」或「數量」設計的unsignd int類型
  - 根據系統為 32bits或64bits
  - 必為非負

此為宣告本題MPI的結構，由 capacity 段 uint32_t 類型 data 組合成多精度的整數進而能描述規模大的int

mpi_t[1] 表示單元素array，目的是傳遞pointer

mpi_init : 初始化一mpi_t使capacity為0，data指向NULL
mpi_clear : free 釋放一mpi_t之data

void mpi_enlarge(mpi_t rop, size_t capacity)
{
    if (capacity > rop->capacity) {
        size_t min = rop->capacity;

        rop->capacity = capacity;

        rop->data = realloc(rop->data, capacity * 4);

        if (!rop->data && capacity != 0) {
            fprintf(stderr, "Out of memory (%zu words requested)\n", capacity);
            abort();
        }

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

mpi_enlarge : 擴充一mpi_t的data段數，若傳參capacity > 該mpi之capacity才運作。運作時由realloc重新分配(傳參capacity*4)bytes，然後將新擴充的段數data都設為0。若分配失敗則輸出錯誤資訊然後abort。

void mpi_compact(mpi_t rop)
{
    size_t capacity = rop->capacity;

    if (rop->capacity == 0)
        return;

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

    assert(capacity != (size_t) -1);

    rop->data = realloc(rop->data, capacity * 4);
    rop->capacity = capacity;

    if (!rop->data && capacity != 0) {
        fprintf(stderr, "Out of memory (%zu words requested)\n", capacity);
        abort();
    }
}

mpi_compact : 壓縮一mpit的記憶體使用，去除末尾的零元素，調整capacity。從data array末尾倒序檢查是否為0，為0則使capcity-1，直到不為0退出。此時退出後之capacity即為皆非0值之data段數。最後利用realloc分配該capacity段數4 bytes的空間。分配失敗則終止。

為什麼需要 (size_t) -1？
- 此為將 -1 強制轉型為size_t值(0xFFFFFFFF或0xFFFFFFFFFFFFFFFF)
- 當 i = 0 - -i 時i會變成size_t最大值也就是(size_t)，確保迴圈不會無限執行
%zu 專為用來輸出 size_t 的值
- 為什麼不用 %d 或 %u？
  - %d 用於有符號整數（int），而 size_t 是無符號的，可能導致輸出錯誤（特別是當值很大時）。
  - %u 用於無符號 int，但 size_t 的大小可能與 int 不同（例如在 64 位系統上，size_t 可能是 64 位，而 int 是 32 位）。使用 %u 可能導致截斷或未定義行為。

/* 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

void mpi_set_u64(mpi_t rop, uint64_t op)
{
    size_t capacity = ceil_div(64, 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;
}

ceil_div : 取天花板數(向上取整)
mpi_set_u64 : 將 uint64_t 轉成 mpi_t

操作
- 先用 ceil_div 對 64 與 31 取得分段數 capacity
- 再將傳參mpi擴充到該capacity
- 最後將 uint64_t 的data以31個1(0x7FFFFFFF,
  $2^{31} - 1$ )為一段作mask放進傳參mpi
  - 若傳參mpi capcity過大則將高段數設為0

為啥用 31 bit 作為一段長度?
因為若用 32 bit 加法或乘法進位(carry)處理會變複雜

例如：兩個最大 32 位元數相加：0xFFFFFFFF + 0xFFFFFFFF = 0x1FFFFFFFE（33 位元）
兩個 31 位元數相加的最大結果是 0x7FFFFFFF + 0x7FFFFFFF = 0xFFFFFFFE（32 位元），正好能放入一個 uint32_t 而不溢位

static void mpi_mul_naive(mpi_t rop, const mpi_t op1, const mpi_t op2)
{
    size_t capacity = op1->capacity + op2->capacity;
    
    mpi_t tmp;
    mpi_init(tmp);

    mpi_enlarge(tmp, capacity);
        
    for (size_t n = 0; n < tmp->capacity; ++n)
        tmp->data[n] = 0;

    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;
            }
        }                                     
    }
        
    mpi_set(rop, tmp);
    
    mpi_compact(rop);
    
    mpi_clear(tmp);
}

mpi_mul_naive : mpi乘法

運作
做直式乘法
- 外圈 : op1段數遍歷
- 中圈 : op2段數遍歷
- 內圈 : 處理carry加到data[k+1]

是否需要以下部分?
1.

if (k >= tmp->capacity)
    mpi_enlarge(tmp, tmp->capacity + 1);

不需要 => n段*m段不會大於n+m段
2.

tmp->data[k] &= INTMAX;

不需要 => 因data大小即為INTMAX

//計算多精度整數 n 除以 d 的商 q 和餘數 r (即 n = d * q + r)
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);//copy
    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);
        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);
}

使用二進制長除法

以下為運作流程 :

初始化

被除數：n0 = 1101（十進位 13）
除數：d0 = 11（十進位 3）
商：q = 0
餘數：r = 0
起始索引：start = mpi_sizeinbase(n0, 2) - 1 = 4 - 1 = 3（最高位索引）

逐位處理

從最高位（i = 3）到最低位（i = 0）逐一處理被除數的每一位。

步驟 1：i = 3（最高位，n0[3] = 1）

餘數左移：r = 0 左移 1 位 → r = 0
附加位元：n0[3] = 1，設 r[0] = 1 → r = 1
比較與減法：r = 1 < d0 = 3，不減，設 q[3] = 0
結果：r = 1, q = 0000

步驟 2：i = 2（n0[2] = 1）

餘數左移：r = 1 左移 1 位 → r = 10（十進位 2）
附加位元：n0[2] = 1，設 r[0] = 1 → r = 11（十進位 3）
比較與減法：r = 3 >= d0 = 3，減去 d0：r = 3 - 3 = 0，設 q[2] = 1
結果：r = 0, q = 0100

步驟 3：i = 1（n0[1] = 0）

餘數左移：r = 0 左移 1 位 → r = 0
附加位元：n0[1] = 0，r 不變 → r = 0
比較與減法：r = 0 < d0 = 3，不減，設 q[1] = 0
結果：r = 0, q = 0100

步驟 4：i = 0（最低位，n0[0] = 1）

餘數左移：r = 0 左移 1 位 → r = 0
附加位元：n0[0] = 1，設 r[0] = 1 → r = 1
比較與減法：r = 1 < d0 = 3，不減，設 q[0] = 0
結果：r = 1, q = 0100

最終結果

商：q = 0100（十進位 4）
餘數：r = 1（十進位 1）

驗證

驗證結果：
13 = 3 × 4 + 1

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

使用輾轉相除法
當發生整除時(下一次r=0，guard clause發生return)，將輸出rop設為當時被除數op1

這項實作依賴遞迴呼叫，請避免使用並降低記憶體開銷

我將原來遞迴修改成以迭代實作

void mpi_gcd(mpi_t rop, const mpi_t op1, const mpi_t op2)
{
    if (mpi_cmp_u32(op1, 0) == 0 || mpi_cmp_u32(op2, 0) == 0) {
        fprintf(stderr, "Both operands are zero, GCD undefined\n");
        return;
    }
        
    mpi_t opa, opb, q, r;
    mpi_init(opa); // Dividend
    mpi_init(opb); // Divisor        
    mpi_init(q);
    mpi_init(r);
    mpi_set(opa,op1);
    mpi_set(opb,op2);
    while(mpi_cmp_u32(opb, 0) != 0){
        mpi_fdiv_qr(q, r, opa, opb);   
        mpi_set(opa,opb);
        mpi_set(opb,r);
    }
    mpi_set(rop,opa);

    mpi_clear(q);
    mpi_clear(r);
    mpi_clear(opa);
    mpi_clear(opb);
    
}

改進最大公因數的運算效率

測驗二

AAAA：(x) ^ (mask)
BBBB：mask << i
CCCC：*asrc

測驗三

AAAA：ENV_RUNNABLE
BBBB：attempts + 1
CCCC：coro_shedule
DDDD：yield

quiz4

測驗一

AAAA：0xc38d26c4
BBBB：0xd3d3e1ab
CCCC：0xe330a81a
DDDD：0xf36e6f75

測驗二

AAAA：0x7FFF
BBBB：0x80000000
CCCC：0x7FFFFFFF
DDDD：0x80000000
EEEE：0x7FFFFFFF
FFFF：input & 0xFF
GGGG：Q15_MIN
HHHH：Q15_MAX

測驗三

IIII：max_fd
JJJJ：&rfds

2025q1 Homework4 (quiz3+4)

預期目標

quiz3

測驗一

初始化

逐位處理

步驟 1：i = 3（最高位，n0[3] = 1）

步驟 2：i = 2（n0[2] = 1）

步驟 3：i = 1（n0[1] = 0）

步驟 4：i = 0（最低位，n0[0] = 1）

最終結果

驗證

測驗二

測驗三

quiz4

測驗一

測驗二

測驗三

Reference

Read more

2025/04/23 一對一討論問答簡記

2025q1 Homework3 (kxo)

linux2025-homework1

2025q1 Homework2 (quiz1+2)