在Python中如何实现指数化？

Question

我可以用Binet公式，即闭解公式，在一个固定的时间内，计算任何通常可计算的fibonnaci数（除非结果变得很大）。这是我的代码：

对于fibonnaci的非递归实现：

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

我知道a^n表示指数级的运行时复杂性，但是当代码在python中运行时，情况并非如此，因为这会立即计算第n个fibonnaci数。我做了一些关于指数在python中如何实现的研究（可能是通过平方来求幂？）给出常数时间解，但还没有找到一个明确的答案。有什么想法吗？在

Answer 1

float.__pow__()方法使用C的libm，它充分利用了硬件对二进制浮点运算的支持。后者用对数表示数字。对数表示使实现指数化仅仅是一次乘法成为可能。在

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

Answer 2

您可以在CPython的source code for the log_pow function找到实现。在

Answer 3

整数的指数可以比你想象的更有效地计算。以下是Wikipedia has to say about it：

The simplest method of computing bⁿ requires n−1 multiplication operations, but it can be computed more efficiently than that, as illustrated by the following example. To compute 2¹⁰⁰, note that 100 = 64 + 32 + 4. Compute the following in order:

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

This series of steps only requires 8 multiplication operations instead of 99 (since the last product above takes 2 multiplications).

In general, the number of multiplication operations required to compute bⁿ can be reduced to Θ(log n) by using exponentiation by squaring or (more generally) addition-chain exponentiation. Finding the minimal sequence of multiplications (the minimal-length addition chain for the exponent) for bⁿ is a difficult problem for which no efficient algorithms are currently known (see Subset sum problem), but many reasonably efficient heuristic algorithms are available.[29]

平方求幂这一页很难总结，但它基本上是2⁸==（2⁴）²==（2²）²，所以不需要计算2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 = 256，而是可以计算2 × 2 = 4; 4 × 4 = 16; 16 × 16 = 256。在