在处理大数字在Haskell

我试图在Haskell（不是米勒拉宾）实施米勒测试。我正在处理大数字，特别是我需要指数大数字，并采取一个模数大量的mod又是一大堆。在处理大数字在Haskell

有没有这样做的标准功能？正常的expt函数^告诉我在计算结果之前内存不足。例如，我想要做的：

（MOD（8888^38071670985）9746347772161）

我可以实现我自己的算法，但它会是不错的，如果这些已经存在。

http://stackoverflow.com/questions/1184296/why-can-haskell-handle-very-large-numbers-easily ...，你的指数非常大......但是...... – 2012-03-25 21:01:57

NVM关于实施我自己的。我查看了这些算法的Haskell实现。他们正是我将如何实施他们。 – 2012-03-25 21:02:44

正如我所说......你的指数是......，非常大...... – 2012-03-25 21:04:52

arithmoi包中有模幂运算（以及更多）。

因为我写了它，我很想听听你是否觉得它有用，什么可以改进。

如果你试图计算

(mod (8888^38071670985) 9746347772161)

的样子，中间结果8888^38071670985会占用大约5 * 10 位，约为60GB。即使你拥有如此多的RAM，接近GMP的限制（可能略高于GMP的限制）（GMP整数中的大小字段为四个字节）。

因此，您还必须在计算过程中减少中间结果。这不仅可以让计算在没有问题的情况下进入内存，而且由于涉及的数量还相当小，因此速度也更快。

2012-03-25 21:05:54

这工作出色。我应该从一开始就这样做。我不知道我为什么没有。无论如何，我一直在盯着算法一段时间。无论出于何种原因，我一直试图分别执行expt和mod，并没有把它们放在一起使用同余特性来减少问题。 – 2012-03-25 21:45:40

的近似计算采取模之前，你的号码是

10^log(8888^38071670985) 
= 10^(38071670985 * log(8888)) 
= 10^(1.5 * 10^11)

换句话说，它有大约1.5 * 10^11位。它需要大约

1.5 * 10^11/log(2)/8/(2^30) = 58GB

的内存只是为了表示。

所以从这开始可能不是最好的主意。图书馆是否有支持用这么大的数字计算？

2012-03-25 21:26:17 Irfy

模数求幂不需要保存“模数取模前的数字” – user102008 2012-03-26 02:45:57

好的算术把戏。 – Trismegistos 2012-03-26 19:16:15

回答