我需要一种算法来对大数执行算术运算（远高于浮点数、双整数或任何其他数据类型的范围）。我需要用 C 编写代码。我试着在这里查找：Knuth, Donald, The Art of Computer Programming, ISBN 0-201-89684-2, Volume 2: Seminumerical Algorithms, Section 4.3.1: The Classical Algorithms但是受不了了。我只需要算法而不是代码。
问问题
3304 次
5 回答
3
此外，据我所知，您不会比简单的线性 O(n) 算法更好，即，只需逐位添加。无论如何，您可能都必须阅读整个输入，因此它至少是线性的。您也许可以采取各种技巧来降低常数。
由于基本长乘法算法的二次性质，您的主要问题将是乘法。您可能需要考虑这里给出的几种更快的方法之一。Karatsuba 方法很难很好地实现，但可能是最简单的非平凡算法，它会给你带来好处。否则，您将不得不更多地研究快速傅里叶变换方法，例如Schönhage-Strassen 算法或Fürer 算法。
另请参见大 O 表示法。
于 2011-08-05T07:12:02.803 回答
3
我认为 Karatsuba 算法最适合对大数执行算术运算。对于足够大的 n，另一种概括，Schönhage-Strassen 算法甚至更快。您可以在Karatsuba 或 Karatsuba_Multiplication中查找算法
于 2012-03-13T10:18:26.213 回答
2
没有算法可以对非常大的数字执行算术运算。算术运算保持不变。你需要的是像http://www.codeproject.com/KB/cs/BigInt.aspx这样的课堂
于 2011-08-05T12:13:54.167 回答
1
Riesel 的质数和因式分解的计算机方法一书有一个附录，其中包含易于阅读的多精度算术代码。
于 2011-08-05T12:05:09.957 回答
0
对于算法，请阅读 Knuth vol 2 或 Crandall 和 Pomerance。对于编码，我建议先让显而易见的算法工作，然后再进行 Karatsuba 或傅立叶变换。
于 2011-08-05T10:53:27.137 回答