переполнения CLISP после умножения

Question

я пытаюсь получить первую LISP программы для работы с помощью реализации CLISP, набрав

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

в REPL.

но это дает мне *** - overflow during multiplication of large numbers. Я думал, что lisp имеет произвольный размер/точность. как это могло случиться тогда?

Answer 1

В соответствии с http://clisp.cons.org/impnotes/num-concepts.html максимальный размер для бигма составляет (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

bignums Лиспа могут занимать очень большое количество, но они тоже имеют свои пределы.

В вашем случае вы можете комбинировать экспоненцию и модуль в единую процедуру, например. как в http://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method.

Answer 5

CLISP при условии, что функция "моды-EXPT" (или EXT: моды-EXPT)

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

53 

который довольно быстро. И для вашей цели, которая работает.