如何编写解决方案以处理大量数据？

Question

我正在做一些Project Euler问题,而且大多数时候,计算涉及超出int,float,double等的大量数字.

首先,我知道我应该寻找更有效的计算方法,以避免出现大量问题.我听说过Bignum图书馆.

但是,对于学术界的兴趣,我想知道如何编写我自己的解决方案来解决这个问题.

任何专家都可以帮帮我吗？(我的语言是C)

Answer 1

您需要将大数字存储在计算机可以使用其本机类型轻松处理的基础中,然后将数字存储在可变长度数组中.我建议为简单起见,首先将数字存储在基数10中,以便了解如何执行此操作.它将使调试更容易.

一旦你有一个可以在这个表格中存储数字的类,只需要在这个类上实现加,减,乘等操作.每个操作都必须迭代其操作数的数字并组合它们,小心地正确携带,这样你的数字永远不会大于基数.加法和减法很简单.乘法需要更多的工作,因为朴素算法需要嵌套循环.然后,一旦你有了工作,你可以尝试以有效的方式实现取幂(例如重复平方).

如果你打算写一个严肃的 bignum实现,基数10将不会削减它.它浪费了内存,而且速度很慢.您应该选择一个对计算机来说很自然的基数,例如256或字大小(2**32).但是这会使简单操作变得更加困难,因为如果你天真地添加两位数就会出现溢出,所以你需要非常小心地处理它.

Answer 2

对于Project Euler来说,C不是一个好的选择.C的好处是原始速度,机器可移植性(在某种程度上,使用标准C),语言互操作性(如果某种语言与另一种语言通信,C是一种流行的首选),坚持接近特定的库或平台的API(因为C很常见,例如OS API),以及稳定的语言和stdlib. 这些好处都不适用于解决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的长期那样只是一个更大的'int'类型.)

Answer 3

这是一个很好且简单的 C 语言 bignum 模块。您可以从中学习一些想法。C 代码的质量不是最高的，但算法实现得很好并且很常见。

有关更高级的内容，请查找 GMP。