如何在Python中实现取幂？

Question

我能够使用Binet的公式计算任何正常可计算的fibonnaci数(除非结果变得很大),使用Binet公式即闭合解公式来计算fibonnaci数.这是我的代码:

对于fibonnaci的非递归实现:

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

我理解^ ^ n表示指数运行时复杂度,但是当代码在python中运行时不是这种情况,因为这会立即计算第n个fibonnaci数.我已经做了一些关于如何在python中实现指数的研究(可能是通过平方取幂？)来给出我得到的恒定时间解,但是还没有找到明确的答案.有任何想法吗？

Answer 1

所述浮子.__ POW __()方法采用C的的libm其中充分利用了硬件支持二进制浮点算术.后者使用对数表示数字.对数表示使得实现指数只能进行单次乘法成为可能.

执行摘要: Float指数在硬件中实现,并且由于对数的魔力而以几乎恒定的速度运行.

Answer 2

整数的指数可以比你想象的更有效地计算.以下是维基百科对此所说的话:

计算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.

Answer 3

您可以在CPython的log_pow函数源代码中找到实现.