contributed by <bevmmf
>
補完程式碼
AAAA
:(n + d - 1) / d
BBBB
:0x7fffffff
CCCC
:n + m
DDDD
:1
EEEE
:mpi_gcd(rop, op2, r)
解釋上述程式碼運作原理
size_t
: 一個專為表示「大小」或「數量」設計的unsignd int類型
此為宣告本題MPI的結構,由 capacity
段 uint32_t 類型 data
組合成多精度的整數進而能描述規模大的int
mpi_t[1]
表示單元素array,目的是傳遞pointermpi_init
: 初始化一mpi_t使capacity為0,data指向NULL
mpi_clear
: free 釋放一mpi_t之data
mpi_enlarge
: 擴充一mpi_t的data段數,若傳參capacity > 該mpi之capacity才運作。運作時由realloc重新分配(傳參capacity*4)bytes,然後將新擴充的段數data都設為0。若分配失敗則輸出錯誤資訊然後abort。
mpi_compact
: 壓縮一mpit的記憶體使用,去除末尾的零元素,調整capacity。從data array末尾倒序檢查是否為0,為0則使capcity-1,直到不為0退出。此時退出後之capacity即為皆非0值之data段數。最後利用realloc分配該capacity段數4 bytes的空間。分配失敗則終止。
(size_t) -1
?
%zu
專為用來輸出 size_t 的值
ceil_div
: 取天花板數(向上取整)
mpi_set_u64
: 將 uint64_t 轉成 mpi_t
為啥用 31 bit 作為一段長度?
因為若用 32 bit 加法或乘法進位(carry)處理會變複雜
mpi_mul_naive
: mpi乘法
是否需要以下部分?
1.
不需要 => n段*m段不會大於n+m段
2.
不需要 => 因data大小即為INTMAX
使用二進制長除法
start = mpi_sizeinbase(n0, 2)
- 1 = 4 - 1 = 3(最高位索引)從最高位(i = 3)到最低位(i = 0)逐一處理被除數的每一位。
驗證結果:
13 = 3 × 4 + 1
使用輾轉相除法
當發生整除時(下一次r=0,guard clause發生return),將輸出rop設為當時被除數op1
這項實作依賴遞迴呼叫,請避免使用並降低記憶體開銷
我將原來遞迴修改成以迭代實作
改進最大公因數的運算效率
AAAA
:(x) ^ (mask)
BBBB
:mask << i
CCCC
:*asrc
AAAA
:ENV_RUNNABLE
BBBB
:attempts + 1
CCCC
:coro_shedule
DDDD
:yield
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