CLISP溢出乘法

Question

我試圖讓第一LISP程序使用CLISP實現，通過在REPL鍵入

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

工作。

但它給我*** - overflow during multiplication of large numbers。我認爲lisp具有任意大小/精度。那麼怎麼會發生呢？

Answer 1

根據http://clisp.cons.org/impnotes/num-concepts.html，一個bignum的最大尺寸是（2^2097088 - 1），而你的2^7830457比這個大得多。

或許你可以看一下打破這個數字 - 也許分離出許多較小的2^X因素...

Answer 2

Lisp是一個擁有數十種方言和數百種不同實現的語言家族。

計算機具有有限的內存。某些操作系統下的程序可能對內存大小有限制。不同的Common Lisp實現使用不同的數字庫。

您可能想查閱您的CLISP手冊，瞭解其各種數據類型的侷限性。

Answer 3

有機會有更好的方法來解決問題。我沒有在PE上做過這麼多，但我知道我迄今爲止所做的少數人傾向於「唉！」看似出於計算機程序範圍的問題的解決方案。

這一個特別 - 2^7830457是一個巨大的號碼 - 嘗試(format t "~r" (expt 2 160))。你可以嘗試用新的眼光來看待問題，看看有沒有辦法看到它，你沒有想到。

Answer 4

Lisp的大數可容納真正的大數字，但他們也有自己的極限。

就你而言，你可以將指數和模數組合成一個單獨的程序，例如，如在http://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method中那樣。

Answer 5

CLISP提供的功能 「MOD-EXPT」（或EXT：MOD-實驗）

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

53 

這是相當快的。併爲你的目的，工程。