<p>整数的指数可以比你想象的更有效地计算。以下是<a href="https://en.wikipedia.org/wiki/Exponentiation#Efficient_computation_of_integer_powers" rel="noreferrer">Wikipedia has to say about it</a>:</p>
<blockquote>
<p>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:</p>
</blockquote>
<pre><code>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
</code></pre>
<blockquote>
<p>This series of steps only requires 8 multiplication operations instead of 99 (since the last product above takes 2 multiplications).</p>
<p><strong>In general, the number of multiplication operations required to compute bⁿ can be reduced to Θ(log n) by using <a href="https://en.wikipedia.org/wiki/Exponentiation_by_squaring" rel="noreferrer">exponentiation by squaring</a></strong> or (more generally) <a href="https://en.wikipedia.org/wiki/Addition-chain_exponentiation" rel="noreferrer">addition-chain exponentiation</a>. 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]</p>
</blockquote>
<p>平方求幂这一页很难总结,但它基本上是2⁸==(2⁴)²==(2²)²,所以不需要计算<code>2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 = 256</code>,而是可以计算<code>2 × 2 = 4; 4 × 4 = 16; 16 × 16 = 256</code>。在</p>