2025q1 Homework4 (quiz3+4)

Contributed by <JimmyChongz>

Quiz 3

測驗一

Accuracy VS Precision

參考 精度和精度 (Accuracy and Precision)

• Accuracy 準確度
  • 測量出的數據有多接近正確的數值
• Precision 精密度
  • 多次測量結果的一致性

填空

• AAAA：實現不使用浮點數運算的 ceiling division
  • 在整數除法中，n / d 會向下取整數。例如 10 / 3 = 3
• BBBB：定義 INTMAX
  • 有號整數的最大值在 64 位元的機器上為 2^64-1 - 1 即 7FFFFFFF₁₆
• CCCC
• DDDD
• EEEE

延伸問題

1. 解釋程式碼運作原理

定義 mpi

#include <inttypes.h>
#include <stdint.h>

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

• <inttypes.h>：提供固定寬度的整數型別（如 uint32_t）和格式化宏，確保跨平台一致性。
• <stdint.h>：定義標準整數型別（如 uint32_t、size_t），用於精確控制記憶體大小。
• unit32_t *data：無號整數陣列，用於儲存多精度整數的數字。
• size_t capacity：表示 data 陣列的容量，用於追蹤分配的記憶體大小。
• 為什麼 mpi_t 被定義為 mpi_t[1] 而不是 mpi_t 或 *mpi_t ？
  • 這種設計的核心目的是讓 mpi_t 在使用時表現得像一個型別，但保留結構內部動態記憶體管理的靈活性。
    • 宣告 mpi_t x; 時，x 是一個單元素陣列，內含結構實體，無需手動分配結構本身的記憶體。
    • 傳遞 func(x) 時，陣列退化為指向結構的指標，效率高（只傳遞一個指標大小的數據）。
    • 使用者只需要管理 x->data 的動態記憶體，結構本身的生命周期由 C 自動處理（Stack 分配）。
    • 語法簡潔：x->data 直接訪問，無需額外的 & 或 *。
• mp_bitcnt_t：表示多精度整數的位元計數（bit count）

記憶體管理相關的操作

// rop (result of operation)
void mpi_init(mpi_t rop)
{
    rop->capacity = 0;
    rop->data = NULL;
}

void mpi_clear(mpi_t rop)
{
    free(rop->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;
    }
}

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、清除 mpi。
• mpi_enlarge：擴大 rop 的 data 陣列容量到指定的 capacity（如果新容量大於當前容量）。
  • 使用 realloc 重新分配 rop->data 到新空間（capacity * 4，因為每個 uint32_t 佔 4 字節）。
  • 如果分配失敗（rop->data == NULL 且 capacity != 0），報錯記憶體不足並終止程式。
  • 將新分配的 (data) 記憶體區塊自原容量 (min) 到新容量之間的值初始化為 0。
• mpi_compact：去除 rop->data 高位的零元素，壓縮 rop 的 data 陣列容量。
  • 從最高位 (rop->capacity - 1) 開始檢查 rop->data[i]，若 rop->data[i] 為零，則壓縮容量 capacity，直到找到第一個非零元素為止。
  • 使用 realloc 將 rop->data 調整到新容量（capacity * 4）。
  • 更新 rop->capacity 為新容量。
  • 相同地，如果分配失敗（rop->data == NULL 且 capacity != 0），報錯記憶體不足並終止程式。

準備基本操作

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

#define INTMAX BBBB

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

2. 避免使用遞迴呼叫，降低記憶體開銷

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

測驗二

測驗三

Quiz 4

測驗一

測驗二

測驗三