lisp - 乗算後の CLISP オーバーフロー

Question

次のように入力して、CLISP 実装を使用して最初の Lisp プログラムを動作させようとしています。

(print (mod (+ (* 28433 (expt 2 7830457) 1)) (expt 10 10))))

REPLで。

しかし、それは私に与えます*** - overflow during multiplication of large numbers。Lisp は任意のサイズ/精度を備えていると思いました。どうしてそれが起こり得るのですか？

score 3 · Accepted Answer

Lisp の bignum は非常に大きな数を保持できますが、それらにも限界があります。

あなたの場合、たとえばhttp://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_methodのように、累乗とモジュラスを単一の手順に組み合わせることができます。

score 2 · Accepted Answer

問題を解決するためのより良い方法がある可能性があります。私は体育でそこまでできていませんが、これまでにやったいくつかのことは「あはは！」になる傾向があることを知っています。コンピュータプログラムの範囲外と思われる問題の解決策。

これは特に - 2^7830457 は膨大な数です - 試してみてください(format t "~r" (expt 2 160))。問題を新しい観点から見て、考えもしなかった方法があるかどうかを確認してみてください。

score 2 · Accepted Answer

http://clisp.cons.org/impnotes/num-concepts.htmlによると、bignum の最大サイズは (2^2097088 - 1) であり、2^7830457 はそれよりもはるかに大きくなります。

おそらく、その数を分解して見ることができます-おそらく、いくつかの小さな2 ^ X要因を分離します...

score 1 · Accepted Answer

Lisp は、数十の方言と数百の異なる実装を持つ言語ファミリーです。

コンピュータのメモリは有限です。一部のオペレーティングシステムのプログラムでは、メモリサイズに制限がある場合があります。Common Lisp の実装が異なれば、使用する数値ライブラリも異なります。

CLISP のさまざまなデータ型の制限については、CLISP のマニュアルを参照してください。

score 0 · Accepted Answer

CLisp は関数 "mod-expt" (または EXT:mod-expt) を提供しました

[1]> (mod-expt 2 1000000 59)

53

これはかなり高速です。そして、あなたの目的のためにそれは機能します。

5 に答える 5