演算法作業好朋友 - BigInteger

日常 .NET 程式開發，若要處理超大數字，ulong 可到 18,446,744,073,709,551,615 (64位元)，若還不夠，decimal 支援範圍從 ±1.0 x 10²⁸ to ±7.9228 x 10²⁸，精確度為 28-29 位，對一般應用已如天文數字，足以應付各式需求。

但切換到數學領域，則是完全不同的局面。尤其是密碼學，在 ECC 橢圓曲線密碼學掘起前，過去常要靠超大數字的計算難題構建防止破解的高牆，以當今仍是資安主力擔當的 RSA 非對稱金鑰加密為例，其原理便是兩個超大質數乘積的因數分解難題。 RSA-2048 挑戰(成功破解可得獎金 USD 20 萬)便高達 617 位十進位數字；而 SSL(TLS)/SSH/IPSec 會用到的迪菲-赫爾曼密鑰交換(Diffie–Hellman Key Exchange)演算法，公式 g^a mod p 中的 p 也是個特大質數，一般也建議要 2048 位元，寫成十進位，數字超過 600 位。

實務上這類超大數字運算通常在底層程式庫或晶片裡做掉，輪不到我們操煩，唯一的例外是學習演算法時可能需要實際寫程式驗證，故練習或作業裡可能出現數百位整數的加減乘除兼取餘數運算需求，此時該怎麼辦？自己宣告一個 byte[] 寫邏輯實現長整數的四則運算？(題外話：小時候參加程式設計比賽，好像有一題就是自己寫除法)

最近發現，現代高階程式語言幾乎都有內建超長整數型別，如 .NET、Java 都有 BigInteger 型別，Python 更是阿莎力，整數原本就沒位數上限，永不溢位。BigInteger 的最大特色是沒有位數上限(所以不會有 BigInteger.MaxValue 這種東西)，只要記憶體放得下，再大的數字都讓你玩。

這篇來簡單介紹 .NET BigInteger 怎麼用。

如何建立 BigIntger？

方法很多，用 new 傳數值建構、明確或隱含轉型、Parse 字串。

// 使用 new 並指定數值，浮點數的話小數部分無條件捨去
var bi1 = new BigInteger(123456);
var bi2 = new BigInteger(1234.567);
// 成百上千位元時，可從 byte[] 建立
// 註：可用 $"{bi3:x}" 顯示為 16 進位，下例為 0x04030201 (高位元在前)
var bi3 = new BigInteger(new byte[] { 1, 2, 3, 4 });
// 明確轉型再等於或用等於隱含轉型都成
var bi4 = (BigInteger)123456789;
BigInteger bi5 = 1234;
// 由字串 Parse
var bi6 = BigInteger.Parse("123456");
// 16 進位數字
var bi7 = BigInteger.Parse("1a2b3c4d", System.Globalization.NumberStyles.HexNumber);

16 進位數字轉換時有個小眉角，若第一個數字大於 7 會被解析為負數，解法是在最前面加一個 "0"：

BigInteger 如何加減乘除？

BigInteger 有實作各種常用運算子，故計算時用一般整數的寫法就可以了。另外，因 Math.Abs() 等方法不支援 BigIneger，BigInteger 有實作專屬版本，例如：BigInteger.Abs()、BigInteger.Pow() (次方)、BigInteger.Max()... 等。使用上蠻直覺的，有 C# 經驗的話可直接上手，有疑問再去翻文件就好。

BigInteger 的效能如何？

未測先猜：很差。

畢竟它是為計算超長整數的特殊目的設計，勢必要取捨，效能肯定不是強項；而 BigInteger 像字串一樣是不可變的，每次計算後要產生一個新結構儲存結果，扯上記憶體配置、資料搬移，想快也快不起來。

官方文件有個經典案例，如果你要做 BigInteger 遞增迴圈，用 int 算完再加到 BigInteger 上，絕對比直接用 BigInteger 計算快 N 倍。

用 LinqPad 7 小測一下：840.78 vs 8.93，差了 94 倍，得證。

小結

這篇文章介紹了 .NET 處理超大數字的利器 - BigInteger 型別，位數無上限(只要記憶體裝得下)，使用上跟 int, long 差不多方便，直接加減乘除即可，但其計算效能較差，但可以滿足密碼學常見的超大數值計算需求，是寫演算法作業的好朋友。

Introduction to .NET BigInteger strcut.