如何實現巨大數字的長分區（bignums）

我正在嘗試爲長號實現長分區。不幸的是，由於嵌入式編程的侷限性，我不能使用像GMP這樣的庫。此外，我想要學習如何實施它的智力活動。到目前爲止，我已經使用任意長度的字節數組完成了加法和乘法運算（因此每個字節都像是一個256位的基數）。如何實現巨大數字的長分區（bignums）

我只是試圖開始實施師/模數，我想知道從哪裏開始？我在網上發現了很多高度優化的（也就是不可讀的）代碼，這對我沒有幫助，而且我發現了很多高技術數學白皮書，我無法彌合理論和實施之間的差距。

如果有人可以推薦一種流行的算法，並指向我一個簡單易懂的解釋，它傾向於implmenentation，那太棒了。

-edit：我需要的算法，它工作時的股息〜4000比特，並且除數〜2000bits

-edit：請問與基地-256算法的工作？ http://courses.cs.vt.edu/~cs1104/BuildingBlocks/divide.030.html

-edit：這是我真的應該使用的算法（牛頓師）嗎？ http://en.wikipedia.org/wiki/Division_(digital)#Newton.E2.80.93Raphson_division

來源

2010-07-07 Chris

我發現這個，但我不確定它會是一個很好的算法，數字> 2048位？ http://stackoverflow.com/questions/2525172/custom-very-long-int-division-issue – Chris 2010-07-07 23:53:31

我也發現這篇論文，對我來說這是一個很好的算法嗎？ http://www.brinch-hansen.net/papers/1994b.pdf – Chris 2010-07-07 23:57:17

如果你想學習，那麼從你在小學時使用的鉛筆和紙的方法開始。相信與否，這與O（n^2）算法基本相同，該算法在大多數bignum庫中用於處於所需範圍內的數字。棘手的第一步被稱爲「商估計」，這可能是最難理解的。一旦你明白了，其餘的應該變得容易。

一個很好的參考是Knuth的「算法算法」。他有很多討論關於在文本和練習中做商數估計的不同方法。這本書有專門討論bignum實現的章節。

來源

2010-07-08 00:06:53

+1爲Knuth參考。 – 2010-07-08 00:09:23

鉛筆和紙的方法似乎只工作，如果除數是一個或兩個數字長，從我可以在網上找到 – Chris 2010-07-08 00:24:54

掛起，這是相同的移位/減法在這裏？ http://courses.cs.vt.edu/~cs1104/BuildingBlocks/divide.030.html – Chris 2010-07-08 00:32:36

這個問題已經超過2年了，但對於這個大小的數字，你可以看看OpenSSL的源代碼。它使用這個大小的數字進行RSA處理，所以有很多數學例程優化了1000到4000位數字。

來源

2012-12-18 03:15:21

你是否在你的代碼中使用了void four1（long double []，int，int），然後進行了卷積然後做了一個逆變換以及我有乘法運行，但是當我嘗試以相同方式進行分割時出一個結果然後退出，所以我不禁要，如果你有一個名爲「C++中的數字食譜」的圖書館去接近尾聲，你會發現你正在尋找什麼，實際上它開始頁916至926.

來源

2014-12-02 19:32:11 user80998

如何實現巨大數字的長分區（bignums）

回答

相關問題