<p>你可以利用“分而治之”的策略,既可以提高速度,也可以在不破坏堆栈的情况下计算非常大的功率。下面的关系和实现都假定幂参数为非负整数值。你知道吗</p>
<p>你已经注意到了<code>a**b == a * a**(b-1)</code>。然而,当<code>b</code>是偶数时<code>a**b == (a*a)**(b/2)</code>也是正确的,这将问题大小减少一半而不是减少1。与递归一样,还需要基本情况<code>a**0 == 1</code>。综合起来,我们得到:</p>
<pre><code>def power(a, b):
if b == 0:
return 1
result = power(a * a, b // 2) # calculate the halved problem
return a * result if b & 1 else result # and multiply by a if b is odd
</code></pre>
<p>它允许我们计算<code>power(2, 2000)</code>:</p>
<p>你知道吗114813069527425452423283320117768198402231770208869520047764273682576626139237031385665948631650626991844596463898746277344711896086305533142593135616665318539129989145312280000688779148240044871428926990063486244781615463646388363947317026040466353970904996558162398808944629605623311649536164221970332681344168908984458505602379484807914058900934776500429002716706625830522008132236281291761267883317206598995396418127021779858404042159853183251540889433902091920554957783589672039160081957216630582755380425583726015528348786419432054508915275783882625175435528800822842770817965453762184851149029376. 你知道吗</p>
<p>对于<code>b == 2000</code>,该算法的递归堆栈增长为O(logb),与11成正比。你知道吗</p>