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

Question

Я пытаюсь заставить первую программу lisp работать с использованием реализации CLISP, набрав

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

в REPL.

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

Answer 1

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

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

Answer 2

Скорее всего, есть лучший способ решить проблему. Я не делал это так далеко на PE, но я знаю, что немногие, которые я сделал до сих пор, как правило, имеют "ага!" решения проблем, которые кажутся выходящими за пределы диапазона компьютерных программ.

Это особенно - 2 ^ 7830457 - это огромное число - попробуйте (format t "~r" (expt 2 160)). Вы можете попытаться взглянуть на проблему в новом свете и посмотреть, есть ли способ взглянуть на нее, о которой вы даже не подумали.

Answer 3

Согласно http://clisp.cons.org/impnotes/num-concepts.html максимальный размер для bignum равен (2 ^ 2097088 - 1), а ваш 2 ^ 7830457 намного больше этого.

Возможно, вы можете посмотреть, как разбить это число - возможно, выделите несколько меньших 2 ^ X факторов ...

Answer 4

Lisp - это семейство языков с десятками диалектов и сотнями различных реализаций.

Компьютеры имеют ограниченную память.Программы под некоторыми операционными системами могут иметь ограничения по объему памяти.Различные реализации Common Lisp используют разные числовые библиотеки.

Возможно, вы захотите обратиться к руководству CLISP, чтобы узнать об ограничениях его различных типов данных.

Answer 5

CLisp предоставил функцию "mod-expt" (или EXT: mod-expt)

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

53

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