loops - Racket expt 是否使用尾递归？

Question

如果我在 Racket 中尝试这个:

(expt 2 1000)

我得到一个比宇宙中所有原子大很多倍的数字:

10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

我什至可以使用 (expt 2 10000) 变得更加疯狂，这在我的 T450 笔记本电脑上仍然只需要一秒钟。据我了解，这只有在尾递归的情况下才有可能。它是否正确？如果是这样，Racket 的尾递归是纯粹的函数式编程，还是在幕后发生了隐藏的副作用？另外，当我看到 Common Lisp 的 loop 时，它是否基于引擎盖下的尾递归？总的来说，我想我想知道这些递归/循环的壮举是如何实现的。

Answer 1

Racket 使用 C 库来实现大整数 (bignums)。该库称为 GMP:

https://gmplib.org/manual/Integer-Exponentiation.html

现在 2^n 的情况很容易在二进制表示中实现。您只需要一个 1 后跟 n 个零。也就是说，GMP 可以非常快速地计算出这个数字。