python - 求幂是如何在 Python 中实现的？

Question

我能够使用 Binet 的公式(即封闭解公式)计算斐波那契数，在恒定时间内计算任何通常可计算的斐波那契数(除非结果变得很大)。这是我的代码:

对于斐波那契的非递归实现:

gr = (1 + 5**0.5) / 2
def gfib(n):
    return int(((gr**n - (1-gr)**n) / 5**0.5))

我知道 a^n 表示指数运行时间复杂度，但是当代码在 python 中运行时情况并非如此，因为它会立即计算第 n 个斐波那契数。我已经对如何在 python 中实现指数(可能是通过平方取幂？)进行了一些研究，以给出我得到的常数时间解决方案，但还没有找到明确的答案。有什么想法吗？

Answer 1

float.__pow__()方法使用 C 的 libm它充分利用了对二进制浮点运算的硬件支持。后者使用对数表示数字。对数表示使得只需要一次乘法就可以实现求幂。

执行摘要:浮点指数是在硬件中实现的，并且由于对数的魔力而以几乎恒定的速度运行。