我能够使用比内公式（即封闭解公式计算斐波那契数）在恒定时间内计算任何通常可计算的斐波那契数（除非结果变得很大）。这是我的代码：
对于斐波那契的非递归实现：
gr = (1 + 5**0.5) / 2
def gfib(n):
return int(((gr**n - (1-gr)**n) / 5**0.5))
我知道 a^n 表示指数运行时间复杂度，但是当代码在 python 中运行时情况并非如此，因为这会立即计算第 n 个斐波那契数。我已经对如何在 python 中实现指数进行了一些研究（可能是通过平方求幂？）以给出我得到的恒定时间解决方案，但还没有找到明确的答案。有任何想法吗？
float.__pow__()方法使用 C 的libm ，它充分利用了对二进制浮点运算的硬件支持。后者使用对数表示数字。对数表示可以实现一次乘法运算。
执行摘要：浮点指数是在硬件中实现的，由于对数的魔力，它以几乎恒定的速度运行。
整数指数的计算效率比您想象的要高得多。以下是Wikipedia 对此的评价：
计算 bⁿ 的最简单方法需要 n-1 次乘法运算，但它的计算效率比这更高，如下面的示例所示。要计算 2¹⁰⁰，请注意 100 = 64 + 32 + 4。按顺序计算以下内容：
2² = 4
(2²)² = 2⁴ = 16
(2⁴)² = 2⁸ = 256
(2⁸)² = 2¹⁶ = 65,536
(2¹⁶)² = 2³² = 4,294,967,296
(2³²)² = 2⁶⁴ = 18,446,744,073,709,551,616
2⁶⁴ × 2³² × 2⁴ = 2¹⁰⁰ = 1,267,650,600,228,229,401,496,703,205,376
这一系列步骤只需要 8 次乘法运算，而不是 99 次（因为上面的最后一个乘积需要 2 次乘法）。
一般来说，计算 bⁿ 所需的乘法运算次数可以通过使用平方取幂或（更一般地）加法链取幂减少到 Θ(log n) 。找到 bⁿ 的最小乘法序列（指数的最小长度加法链）是一个困难的问题，目前还没有已知有效的算法（参见子集和问题），但有许多相当有效的启发式算法可用。 [29]
平方指数的页面很难总结，但它基本上是 2⁸ == (2⁴)² == (2²)²)² 的想法，所以2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 = 256你可以计算而不是计算2 × 2 = 4; 4 × 4 = 16; 16 × 16 = 256。
您可以在 CPython 的源代码中找到 log_pow 函数的实现。