私はハスケル（Miller-Rabinではない）でミラーテストを実装しようとしています。大きな数字を扱っていますが、特に大きい数字を指数化し、大きな数字は別の大きな数字です。ハスケルで大きな数字を扱う場合
これを行うための標準機能はありますか？通常のexpt関数^は結果を計算する前にメモリが足りなくなったことを知らせます。例えば、私がやりたい：
（MOD（8888^38071670985）9746347772161）
私は自分のアルゴリズムを実装することができますが、これらがすでに存在する場合、それはいいだろう。
arithmoiパッケージには、べき乗剰余があります（さらにはそれ以上）。
私はそれを書いて以来、私はあなたがそれが有用であり、何が改善できるかを知ることに興味があるでしょう。
あなたはそのままで、中間結果8888^38071670985は60ギガバイト程度およそ5×10 ビットを、占有し
(mod (8888^38071670985) 9746347772161)
を計算しよう。 GMPの限界（GMP整数のサイズフィールドは4バイトです）の限界に近い（多分わずかに上の）RAMです。
したがって、計算中に中間結果を減らす必要があります。計算が問題なくメモリに収まるだけでなく、関連する数値もかなり小さいので、高速です。
これはすごくうまくいった。私はこれを最初からやっていたはずです。なぜ私がしなかったのかわかりません。とにかく今はしばらくアルゴリズムを見つめている。何らかの理由で、私はexptとmodを別々にしようと努力しましたが、問題を軽減するため合同の性質を使うためにまとめませんでした。 –
剰余を取る前に、あなたの番号への近似は、約1.5×10^11桁の数字を持っている言い換えれば
10^log(8888^38071670985)
= 10^(38071670985 * log(8888))
= 10^(1.5 * 10^11)
です。それだけで表現するために周りの
1.5 * 10^11/log(2)/8/(2^30) = 58GB
メモリの必要があるだろう。
これで始めるのが最適ではないかもしれません。ライブラリには、この多数の計算をサポートするためにがありますか？
モジュラ累乗では "モジュロを取る前の数"を保つ必要はありません。 – user102008
その良い算術的トリックです。 – Trismegistos
http://stackoverflow.com/questions/1184296/why-can-haskell-handle-very-large-numbers-easily ...あなたの指数は非常に大きいです...しかし、 –
NVMについて自分自身を実装する。私は、これらのアルゴリズムのHaskellの実装を調べました。彼らは私がそれらを実装した方法です。 –
私が言ったように...あなたの指数は...、非常に大きいです... –