c - 如何编写处理大数字的解决方案？

Question

关闭。这个问题是 opinion-based 。目前不接受答案。

---

想要改进这个问题吗？更新问题，以便 editing this post 可以用事实和引文来回答它。 .

已关闭 3 年前。

Improve this question

我正在做一些欧拉项目问题，大多数时候，计算涉及除 int、float、double 等之外的大量数字。

首先，我知道我应该寻找更有效的计算方法以避免大数问题。 我听说过 Bignum 库。

但是，出于学术兴趣，我想知道如何编写自己的解决方案来解决这个问题。

有高手可以帮帮我吗？ (我的语言是C)

Answer 1

您需要将大数字存储在计算机可以使用其 native 类型轻松处理的基数中，然后将数字存储在可变长度数组中。为了简单起见，我建议您首先以 10 为基数存储数字，以便掌握如何执行此操作的窍门。这将使调试变得更加容易。

一旦您拥有一个可以以这种形式存储数字的类，只需在该类上实现加、减、乘等操作即可。每个操作都必须迭代其操作数的数字并将它们组合起来，小心地正确进位，以便您的数字永远不会大于基数。加法和减法很简单。乘法需要更多的工作，因为朴素算法需要嵌套循环。然后，一旦您完成了该工作，您就可以尝试以有效的方式实现求幂(例如重复平方)。

如果您计划编写一个认真的bignum实现，基数10不会削减它。浪费内存而且速度会很慢。您应该选择适合计算机的基数，例如 256 或字长 (2**32)。然而，这将使简单的操作变得更加困难，因为如果你天真地添加两位数字，你就会溢出，所以你需要非常小心地处理它。