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

Question

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

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

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

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

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

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

Answer 1

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

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

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

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

Фактически, формулу Лежандра можно использовать для определения наивысшего показателя v, например что 2 ^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

Answer 2

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

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

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