演算法作業好朋友 - BigInteger
0 | 2,386 |
日常 .NET 程式開發,若要處理超大數字,ulong 可到 18,446,744,073,709,551,615 (64位元),若還不夠,decimal 支援範圍從 ±1.0 x 1028 to ±7.9228 x 1028,精確度為 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.
Comments
Be the first to post a comment