147*_*7pm 3 lisp loops tail-recursion racket
如果我在Racket中尝试这个:
(expt 2 1000)
我得到的数字比宇宙中所有原子大许多倍:
10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
我甚至可以(expt 2 10000)在我的T450笔记本电脑上使用仍然只需要一秒钟.据我了解,这只能因为尾递归而成为可能.它是否正确？如果是这样,Racket的尾递归是纯函数式编程,还是幕后隐藏的副作用？另外,当我看到Common Lisp时loop,它是否基于引擎盖下的尾递归？一般来说,我想我想知道这些递归/循环的功能是如何实现的.
Racket使用C库来实现大整数(bignums).该库名为GMP:
https://gmplib.org/manual/Integer-Exponentiation.html
现在2 ^ n的情况很容易在二进制表示中实现.你只需要一个1后跟n个零.也就是说,GMP可以非常快速地计算数量.