Зарядный переполнение после умножения

Question

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

(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-conepts.html. Максимальный размер для Bignum (2 ^ 2097088 - 1), а ваш 2 ^ 7830457 намного больше, чем это.

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

Answer 2

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

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

Answer 3

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

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

Answer 4

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

Компьютеры имеют конечную память. Программы в некоторых операционных системах могут иметь ограничения по размеру памяти. Различные общие реализации LISP используют разные числовые библиотеки.

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

Answer 5

CLISP предоставил функцию «Mod-Expt» (или Ext: Mod-Expt)

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

53

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