# 2025q1 Homework4 (quiz3+4)
**Contributed by <`JimmyChongz`>**

## Quiz 3
### 測驗一
##### Accuracy VS Precision
> 參考 [精度和精度 (Accuracy and Precision)
](https://tw.voicetube.com/videos/26583)
- Accuracy 準確度
- 測量出的數據有多接近正確的數值
- Precision 精密度
- 多次測量結果的一致性
#### 填空
- AAAA：實現不使用浮點數運算的 **ceiling division**
- 在整數除法中，`n / d` 會向下取整數。例如 `10 / 3 = 3`
- BBBB：定義 `INTMAX`
- 有號整數的最大值在 64 位元的機器上為 2^64-1^ - 1 即 7FFFFFFF~16~
- CCCC
- DDDD
- EEEE

**延伸問題**
#### 1. 解釋程式碼運作原理
:::spoiler 定義 `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）
:::spoiler 記憶體管理相關的操作

// 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`），報錯記憶體不足並終止程式。

:::spoiler 準備基本操作

/* 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
### 測驗一
### 測驗二
### 測驗三