为什么在 Lisp 中计算 1000 阶乘如此之快（并显示正确的结果）？

Question

我尝试在 Lisp 中实现阶乘的简单计算。

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

正如人们所期望的那样，该代码适用于较小的数字 (< 10)。然而，令我感到非常惊讶的是它也适用于更高的数字（例如 1000），而且几乎是立即计算出结果。

另一方面，在 C++ 中，以下代码为 factorial(1000).

检索 0

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

为什么Lisp中的计算速度这么快，数字是如何存储在内存中的？

Answer 1

Common Lisp（理论上）对整数没有限制（例如 Python）。整数的存储是根据需要自动分配的，以表示大整数。另一方面，C++ 原生整数（例如 int 类型）存储在固定大小的内存中。在当今大多数平台上，大小通常在 1 到 8 个字节之间。

C++ 方法的好处是整数计算可以非常快，因为它们可以直接编译为非常快的处理器指令（与 Common Lisp 不同）。但是，缺点是当计算值太大而无法放入 C++ 本机整数类型变量时，就会发生溢出。结果值在数学上不再正确。

由于 factorial(1000) 是一个非常大的数字，它通常不适合本机整数。溢出是得到 0 的原因。您可以使用（非标准）高级可变大小 C++ 整数类型（例如 Boost multi-precision library 中提出的那种）获得数学上正确的结果。使用它，factorial(1000) 的计算也可以在 C++ 中非常快速地完成（并且在数学上仍然是正确的）。

Answer 2

Common Lisp 有 bignums 并在必要时尝试使用它们（除非另有说明）以便结果在数学上对大多数用户有用：非计算人员通常不希望对 2 的幂进行模运算.

您可以查看 bignums 的实现方式（例如 sbcl），以更好地理解它们的工作原理、内存分配方式以及它们速度的原因。 bignums 背后有很多工作可以使它们在实践中更快（我遇到的唯一问题是打印它们（尤其是在 Emacs 中））。

long long unsigned 类型应该至少有 64 位宽（在 C++ 中，宽度总是 2 的幂，但我不确定标准是否要求它），并且无符号整数被定义为有一个换行符-around 语义。您获得 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

为什么在 Lisp 中计算 1000 阶乘如此之快（并显示正确的结果）？

Why is the calculation of 1000 factorial so fast in Lisp (and shows correct result)?

c++

lisp

performance

common-lisp

factorial