在處理大數字在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

回答