6

有什么方法可以合理地对非常大的整数(数百万或数十亿位)进行操作?我需要做的操作是简单的+、-、*,也许还有/。

我正在寻找的是在合理的时间内完成上述操作的算法(在现代 PC 上最多 1 小时)。我不介意对数字使用任何类型的表示,但如果我需要为每个操作使用不同的表示,那么不同表示之间的转换也应该在合理的时间内完成。

当用于这个大小的数字时,我看过的所有大数字库都完全崩溃了。这是否表明不存在此类算法,或者只是这些库表示/实现未针对此类大小进行优化?

编辑1 小时的限制可能是不可能的。我给出了这个数字,因为超过十亿次迭代的简单循环应该花费更少的时间,我希望有一个算法可以使用 O(n) 时间。24小时的限制似乎更合理吗?

4

1 回答 1

2

您可能希望查看DecInt Python 类

这针对非常长的十进制整数进行了优化。(这些数字存储在一种表示形式中,可以在 O(n) 时间内轻松转换为十进制数字)。

它可以执行您希望的操作,包括:

  1. O(n ln(n)) 中的乘法
  2. O(n ln(n)^2) 中的除法
于 2013-10-28T13:16:27.007 回答