# 2025q1 Homework4

contributed by < [BennyWang1007](https://github.com/BennyWang1007) >

{%hackmd NrmQUGbRQWemgwPfhzXj6g %}

## 開發環境

$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0

$ lscpu
架構：                    x86_64
  CPU 作業模式：          32-bit, 64-bit
  Address sizes:          39 bits physical, 48 bits virtual
  Byte Order:             Little Endian
CPU(s):                   20
  On-line CPU(s) list:    0-19
供應商識別號：            GenuineIntel
  Model name:             12th Gen Intel(R) Core(TM) i7-12700H
    CPU 家族：            6
    型號：                154
    每核心執行緒數：      2
    每通訊端核心數：      14
    Socket(s):            1
    製程：                3
    CPU(s) scaling MHz:   23%
    CPU max MHz:          4700.0000
    CPU min MHz:          400.0000
    BogoMIPS:             5376.00
Virtualization features:  
  虛擬：                  VT-x
Caches (sum of all):      
  L1d:                    544 KiB (14 instances)
  L1i:                    704 KiB (14 instances)
  L2:                     11.5 MiB (8 instances)
  L3:                     24 MiB (1 instance)
NUMA:                     
  NUMA 節點：             1
  NUMA node0 CPU(s)：     0-19

### Quiz03-1
#### 參考答案
AAAA = (n+d-1)/d
BBBB = 0x7fffffff
CCCC = n+m
DDDD = 1
EEEE = mpi_gcd(rop,op2,r)

#### 延伸1: 解釋上述程式碼運作原理

static size_t ceil_div(size_t n, size_t d)
{
    // return AAAA;
    return (n+d-1)/d;
}

除法取上高斯等同於加上(除數-1)然後相除取下高斯：
$\lceil \frac{n}{d} \rceil = \lfloor \frac{n + (d-1)}{d} \rfloor$

// #define INTMAX BBBB
#define INTMAX 0x7fffffff

有號整數的最大值為 `0x7fffffff`

在 `mpi_mul_naive` 中，首先對每一對 31-bit 的 limb 相乘，會產生一個最大 62-bit 的中間結果，接下來進行加總與進位處理(res[n+m] += a[n] * b[m]):

// for (size_t k = CCCC; c || r; ++k)
for (size_t k = n+m; c || r; ++k)

最後用位元運算操作加法以及進位。

用 mpi_testbit() 檢查 n 的每一位，把 `r` 左移一位，加上該位。
若 r ≥ d，則減去 `d`，並把 `q` 的那一位設為 1。


`mpi_gcd` 等價於輾轉相除法：

if (op2 == 0)
return op1;
else
gcd(op2, op1 % op2)

因此 EEEE = `mpi_gcd(rop, op2, r)`;

#### 延伸二: 這項實作依賴遞迴呼叫，請避免使用並降低記憶體開銷
將程式碼改成避免遞迴

void mpi_gcd(mpi_t rop, const mpi_t op1, const mpi_t op2)
{
...

while (mpi_cmp_u32(b, 0) != 0) {
mpi_fdiv_qr(NULL, t, a, b); // t = a % b, don't care the quotient
mpi_set(a, b); // a = b
mpi_set(b, t); // b = t
}
...

#### 延伸三: 改進最大公因數的運算效率
可以使用「Stein's GCD（Binary GCD）」：
1. 若兩數都是偶數，gcd(a,b) = 2 * gcd(a/2, b/2)
2. 若一偶一奇，則 gcd(a,b) = gcd(a/2, b) or gcd(a, b/2)
3. 若兩數皆為奇數，則 gcd(a,b) = gcd(|a-b|, min(a,b))

以下為最終程式碼

int mpi_even(const mpi_t op)
{
return (op->capacity == 0) || ((op->data[0] & 1) == 0);
}

void mpi_rshift1(mpi_t rop)
{
uint32_t carry = 0;
for (size_t i = rop->capacity; i-- > 0;) {
uint32_t new_carry = rop->data[i] & 1;
rop->data[i] = (rop->data[i] >> 1) | (carry << 30);
carry = new_carry;
}
mpi_compact(rop);
}

void mpi_lshift(mpi_t rop, const mpi_t op, size_t k)
{
mpi_set(rop, op);
while (k--)
mpi_lshift1(rop);
}

void mpi_swap(mpi_t a, mpi_t b)
{
mpi_t tmp;
mpi_init(tmp);

mpi_set(tmp, a);
mpi_set(a, b);
mpi_set(b, tmp);

mpi_clear(tmp);
}

void mpi_gcd(mpi_t rop, const mpi_t op1, const mpi_t op2)
{
mpi_t a, b;
mpi_init(a);
mpi_init(b);

mpi_set(a, op1);
mpi_set(b, op2);

if (mpi_cmp_u32(a, 0) == 0) {
mpi_set(rop, b);
mpi_clear(a);
mpi_clear(b);
return;
}

if (mpi_cmp_u32(b, 0) == 0) {
mpi_set(rop, a);
mpi_clear(a);
mpi_clear(b);
return;
}

// Find common power of 2 (d)
size_t d = 0;
while (mpi_even(a) && mpi_even(b)) {
mpi_rshift1(a);
mpi_rshift1(b);
++d;
}

// Divide a by 2 until it becomes odd
while (mpi_even(a))
mpi_rshift1(a);

do {
while (mpi_even(b))
mpi_rshift1(b);

if (mpi_cmp(a, b) > 0)
mpi_swap(a, b); // Ensure a <= b

mpi_sub(b, b, a); // b = b - a

} while (mpi_cmp_u32(b, 0) != 0);

// Restore common factors of 2
if (d > 0)
mpi_lshift(a, a, d);

mpi_set(rop, a);

mpi_clear(a);
mpi_clear(b);
}

### Quiz03-2
#### 參考答案
測驗二：
\

### Quiz03-3
#### 參考答案
AAAA = ENV_RUNNABLE
BBBB = attempts+1
CCCC = coro_schedule
DDDD = coro_yield