在很大的數字上進行算術運算的算法

我需要一個算法來對大數字進行算術運算（比float，double int或任何其他數據類型的範圍要高）。我需要用C編寫代碼。我試着在這裏查找：Knuth，Donald，計算機編程藝術，ISBN 0-201-89684-2，第2卷：研討會算法，第4.3.1節：古典算法但無法忍受它。我只需要算法而不是代碼。在很大的數字上進行算術運算的算法

來源

2011-08-05 Tom Helinski

功課，你可以使用鏈表一大批。列表中的單個節點將保存號碼的單個數字。 –

您可以對GMP（http://gmplib.org/）或Java的BigInteger類等現有庫進行逆向工程。源代碼位於http://www.java2s.com/Open-Source/Java-Document/6.0-JDK-Core/math/java/math/BigInteger.java.htm。 –

你會如何對非常大的數字進行算術運算？有你的算法，至少有一個起點... –

另外，據我所知，你不會比簡單的線性O（n）算法好得多，也就是說，只需要逐位添加數字。你可能必須讀完整個輸入，所以它至少是線性的。你也許可以做各種各樣的技巧來保持不變。

由於基本長乘法算法的二次性，您的主要問題是乘法。您可能需要考慮here提供的幾種更快的方法之一。 Karatsuba方法實現起來有點棘手，但它可能是最簡單的非平凡算法，它會給你帶來好處。否則，您將不得不更多地瞭解快速傅立葉變換方法，例如Schönhage-Strassen's algorithm或Fürer's algorithm。請參閱Big O notation。

來源

2011-08-05 07:12:02 MGwynne

我在C中實現了一個簡單的基於FFT的乘法（〜Fürer方法），作爲一年級大學生，用於一個學校項目。數字食譜中有一些有趣的材料，並不是很難。 –