我正在做一些 Project Euler 问题，并且大多数时候，计算涉及超出 int、float、double 等的大量数字。
首先，我知道我应该寻找更有效的计算方法，以避免出现大数问题。我听说过 Bignum 库。
但是，出于学术兴趣，我想知道如何编写自己的解决方案来解决这个问题。
有哪位高手可以帮帮我吗？（我的语言是C）
问问题
17022 次
6 回答
17
您需要将大数字存储在计算机可以使用其本机类型轻松处理的基数中，然后将数字存储在可变长度数组中。我建议为简单起见，首先将数字存储在以 10 为底的数字，以了解如何执行此操作。这将使调试变得容易得多。
一旦你有了一个可以以这种形式存储数字的类，只需在这个类上实现加法、减法、乘法等操作。每个操作都必须迭代其操作数的数字并将它们组合，小心正确携带，以便您的数字永远不会大于基数。加法和减法很简单。乘法需要更多的工作，因为朴素算法需要嵌套循环。然后，一旦你完成了这项工作，你就可以尝试以一种有效的方式实现取幂（例如重复平方）。
如果你打算编写一个严肃的bignum 实现，base 10 不会削减它。这很浪费内存，而且会很慢。您应该选择适合计算机的基数，例如 256 或字长 (2**32)。但是，这将使简单的操作变得更加困难，因为如果您天真地添加两位数字，您将得到溢出，因此您需要非常小心地处理它。
于 2010-01-02T10:38:07.617 回答
12
C 不是 Project Euler 的好选择。C 的好处是原始速度、机器可移植性（在某种程度上，与标准 C）、语言互操作性（如果某种语言与另一种语言进行通信，C 是流行的首选）、紧贴特定库或平台的 API（因为 C是常见的，例如 OS API），以及稳定的语言和标准库。 这些好处都不适用于解决 Project Euler 问题。 甚至没有原始速度，因为大多数问题不是关于原始计算，而是理解所需的算法，您可以整天坐在那里等待提交。
如果您正在尝试 Project Euler 问题来扩展您对 C 的体验，那很好，只要意识到这种体验并不一定适用于您可能从事的长期和现实世界的 C 项目。
对于这种短暂的、一次性的问题，那些通常被称为“脚本语言”的语言将工作得更好、更快（在开发时）和更容易。试试 Python，它在许多方面都接近 C，包括 C API，并且在各种流行的“脚本语言”中，您可能会发现与 C 项目结合使用最多的一种。
这可能会成为一个不受欢迎的答案，但它不是一个咆哮——再加上我真的很喜欢 C 并且经常使用 C/C++——这里有一个明确的答案来解决你的问题：“不要使用 C”，你的最后一个大数字解决方案取决于您选择的替代方案。再次选择 Python，整数没有上限（请注意下面），我使用它来自然地对 Project Euler 问题的答案进行编码，而在其他语言中，我必须使用痛苦的比较替代数字库。
（Python整数： 2.x中有两种整数类型，'int'和'long'（在3.x中已经完全统一）。它们之间的转换实际上是无缝的，'long'允许任意大的值，而不是像 C 的 long 那样只是一个更大的 'int' 类型。）
于 2010-01-02T11:10:04.450 回答
4
一个流行的用于 C/C++ 的 bignum 库是GNU MP Bignum 库。我已经将它用于几个 Project Euler 问题，但事实仍然是 C 不是一种非常适合 Euler 问题的语言。如果性能更重要，C 会提供更多，但现在你最好使用一种内置 bignum 支持的语言，比如 Ruby（还有很多其他语言）。
于 2010-01-02T12:14:12.213 回答
3
一种简单的方法是将数字视为其以 b 为底的字符串表示形式。假设 b=10，可以使用与笔和纸相加时使用的相同方法来完成简单的算术运算，例如对两个这样的字符串进行加法运算。其他简单的操作也是如此。为了获得更好的结果，您可以选择更大的基数。
像这样一个简单的 bignum 实现应该足以解决大多数 Project Euler 问题（可能是所有问题，但我在 Euler 上解决的问题不多，所以不能确定），但是有一些方法可以使用更快的算法进行运算，例如乘法和师/国防部。
尽管我建议您编写自己的 bignum 进行练习，但如果您真的卡住了，您可以从已经实现的 bigint 库的代码中汲取灵感。对于一个严肃的实现，像 gmp 这样的东西是显而易见的选择。但是你也可以在网上解决类似的练习题时找到其他人编码的小的 bigints（例如 Abednego 的bigint.cpp）。
于 2010-01-02T11:04:10.560 回答
1
这是C 语言的一个不错且简单的 bignum 模块。您可以从中学习灵感。C 代码不是最高质量的，但该算法实现得很好并且很常见。
对于更高级的东西，请查阅 GMP。
于 2010-01-02T10:32:23.293 回答
0
如果你想要一个不错的 C++ 版本（我知道，你说的是 C，但这是非常有趣的代码），看看 CGAL 的内部结构：http ://www.cgal.org/
于 2010-01-02T11:04:49.280 回答