c++ - 为什么在 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 有 bignums并在必要时尝试使用它们(除非另有说明)，以便结果在数学上对大多数用户有用:非计算人员通常不期望模算术超过 2 的幂。

您可以查看 bignums 是如何实现的(例如 sbcl )，以更好地了解它们的工作原理、内存分配方式以及它们为何如此之快。 bignums 背后有很多工作要让它们在实践中快速运行(我遇到的唯一问题是使用 bignums 来打印它们(尤其是在 Emacs 中))。

long long unsigned 类型应至少为 64 位宽(在 C++ 中，宽度始终是 2 的幂，但我不确定标准是否需要)，并且无符号整数被定义为有一个环绕语义。你得到 0 因为阶乘是 2⁶⁴

的倍数

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

事实上，Legendre's formula可用于确定最高指数 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