Почему вычисление 1000 факториала в Лиспе происходит так быстро (и показывает правильный результат)?

Я попытался реализовать наивный расчет факториала в Лиспе.

(defun factorial (n)
  (if (equal n 1)
    1
    (* n (factorial (- n 1)))))

Код работает для небольших чисел (‹ 10), как и следовало ожидать. Однако я был очень удивлен, что он работает и для гораздо больших чисел (например, 1000), и результат вычисляется почти мгновенно.

С другой стороны, в C++ следующий код извлекает 0 для factorial(1000).

long long unsigned factorial(int n)
{
    if(n == 1) return 1;
    return n * factorial(n-1);
}

Почему вычисление в Лиспе происходит так быстро и как число хранится в памяти?


c++ performance lisp factorial common-lisp
person Hawklike    schedule 27.05.2020    source источник
comment
Какой Лисп используете? Некоторые не компилируют все по умолчанию; это может быть немного быстрее, если вы скомпилируете эту отдельную функцию с (compile 'factorial).   -  person Kaz    schedule 28.05.2020
comment
Забавный факт: Bignum впервые появился в одном из предков Common Lisp в 1973 году.   -  person Kaz    schedule 28.05.2020
comment
@Kaz Я использую Клисп 2.49.   -  person Hawklike    schedule 28.05.2020

Ответы (2)


arrow_upward
6
arrow_downward

Common Lisp имеет bignums и пытается использовать их при необходимости (и если не указано иное), поэтому что результаты математически полезны для большинства пользователей: некомпьютерные люди обычно не ожидают арифметики по модулю над степенями двойки.

Вы можете посмотреть, как реализованы bignums (например, sbcl), чтобы лучше понять, как они работают, как распределяется память и почему они быстрые. За бигнумами стоит большая работа, чтобы сделать их быстрыми на практике (единственная проблема, с которой я когда-либо сталкивался, это их печать (особенно в Emacs)).

Тип long long unsigned должен иметь ширину не менее 64 бит (в C++ ширина всегда равна степени 2, но я не уверен, что стандарт требует этого), а целые числа без знака определены с семантикой переноса. Вы получаете 0, потому что факториал кратен 264

(mod (factorial 1000) (expt 2 64))
0

Фактически, формула Лежандра может быть использована для определения наивысшего показателя степени v, такого что 2< sup>v делит 1000!:

CL-USER> (loop
            with p = 2
            with n = 1000
            for i from 1
            for v = (floor n (expt p i))
            while (plusp v)
              sum v)
994

Мы можем подтвердить, что (expt 2 994) действительно делит это большое число:

CL-USER> (mod (factorial 1000) (expt 2 994))
0

Но (expt 2 995) нет:

CL-USER> (mod (factorial 1000) (expt 2 995))
167423219872854268898191413915625282900219501828989626163085998182867351738271269139562246689952477832436667643367679191435491450889424069312259024604665231311477621481628609147204290704099549091843034096141351171618467832303105743111961624157454108040174944963852221369694216119572256044331338563584
person coredump    schedule 27.05.2020

arrow_upward
1
arrow_downward

Common Lisp не накладывает (теоретически) никаких ограничений на целые числа (например, Python). Память целого числа автоматически распределяется по мере необходимости для представления больших целых чисел. С другой стороны, собственные целые числа С++ (например, типы int) хранятся в памяти фиксированного размера. Размер обычно составляет от 1 до 8 байт на большинстве современных платформ.

Преимущество подхода C++ заключается в том, что целочисленные вычисления могут выполняться очень быстро, поскольку их можно напрямую скомпилировать в очень быстрые инструкции процессора (в отличие от Common Lisp). Однако недостатком является то, что когда вычисляемое значение слишком велико, чтобы поместиться в собственную переменную целочисленного типа C++, возникает переполнение. Полученное значение больше не является математически правильным.

Поскольку factorial(1000) — очень большое число, обычно оно не помещается в исходное целое число. Переполнение является причиной получения 0. Вы можете получить математически правильные результаты, используя (нестандартный) целочисленный тип C++ высокого уровня с переменным размером, такой как предложенный в Увеличить библиотеку мультиточности. Используя это, вычисление factorial(1000) также может быть выполнено очень быстро в C++ (и при этом быть математически правильным).

person Jérôme Richard    schedule 27.05.2020
comment
вам нужно будет указать компилятору Common Lisp через объявления использовать непроверенные и переполненные целые числа. - person Rainer Joswig; 28.05.2020