大數運算的函式庫—BigNumber.h

發表於 分類於 文章字數： 1k

因為在許多online judge的題目中，大數運算是很常見的題型之一， 所以就寫了一個可以簡單進行大數運算的函式庫。

BigNumber 內容

  • 目前只支援整數
  • 四則運算(除法只算到整數)
  • 可直接比較，賦值
  • 從各種type轉換成BigNumber物件，如int, long, string...
  • 以string形式輸出

Github Repo連結

用NaN表示例外

  • Not A Number
    • Example: 0/0, log(-1)
    • NaN == NaN is false
    • 可用 isnan() 檢查
1
2
double list = 0.0 / 0.0;
printf("%lf\n", list); // will print -nan

實作方法

儲存方式

  • 用陣列存「每一格是一個大進位」，而不是一格存一位十進位數字
    • 一格存 $10^9$ 剛好塞得進 uint32_t，而且兩格相乘不會溢出 uint64_t
    • 比一格一位數快約 9 倍，而且輸出時直接 printf("%09u") 補零就好
  • 低位存在陣列前端(little-endian)
    • 加法、乘法都是從低位往高位進位，順著索引走比較自然
    • 進位造成長度變長時，直接 push_back 即可，不用整個搬移
  • 符號另外用一個 bool/int 存，絕對值和符號分開處理
    • 0 只能有一種表示法(不能有 -0)，否則比較和相等判斷會出錯

四則運算

  • 加法：逐格相加，carry = sum / BASE, digit = sum % BASE
  • 減法：確保被減數絕對值較大(否則交換並翻轉符號)，借位同理
    • 結尾要去掉前導的 0 格，不然長度會虛胖，影響後續比較
  • 乘法：依長度分三段選演算法
    演算法 複雜度 適用長度
    長乘法(schoolbook) $O(n^2)$ 幾百位以內
    Karatsuba $O(n^{1.585})$ 上千位起才划算
    FFT / NTT $O(n \log n)$ 上萬位以上
    • online judge 的大數題幾乎都是長乘法就夠，遞迴的常數項反而讓 Karatsuba 在短輸入更慢
  • 除法：長除法，每一位用二分搜尋試商
    • 每次二分約 $\log(\text{BASE})$ 次「乘一位數 + 比較」，所以整體是 $O(n^2 \log B)$
    • 這是四則運算中最容易寫錯的部份，尤其是餘數的符號(C++ 的 % 對負數是往零截斷)

比較

  • 先比符號 → 再比長度 → 最後才從高位往低位逐格比
    • 前兩步就能短路掉絕大多數情況，不用真的走完整個陣列

邊界條件

  • 0 的表示法要唯一
  • 除以 0 → 這也是本文用 NaN 的理由
  • 前導零：無論哪個運算，結束前都要 normalize(去掉高位的 0 格)
  • 字串轉入時要接受 +/- 開頭與前導空白，並且拒絕非數字字元