Editing Exponentiation (section)

==Efficient computation with integer exponents==
Computing {{math|''b''<sup>''n''</sup>}} using iterated multiplication requires {{math|''n'' − 1}} multiplication operations, but it can be computed more efficiently than that, as illustrated by the following example. To compute {{math|2<sup>100</sup>}}, apply [[Horner's rule]] to the exponent 100 written in binary:
: <math>100 = 2^2 +2^5 + 2^6 = 2^2(1+2^3(1+2))</math>.
Then compute the following terms in order, reading Horner's rule from right to left.
{{Static row numbers}}
{| class="wikitable sortable static-row-numbers" style="text-align:right;"
|-
| 2<sup>2</sup> = 4
|-
| 2 (2<sup>2</sup>) = 2<sup>3</sup> = 8
|-
| (2<sup>3</sup>)<sup>2</sup> = 2<sup>6</sup> = 64
|-
| (2<sup>6</sup>)<sup>2</sup> = 2<sup>12</sup> = {{val|4,096}}
|-
| (2<sup>12</sup>)<sup>2</sup> = 2<sup>24</sup> = {{val|16,777,216}}
|-
| 2 (2<sup>24</sup>) = 2<sup>25</sup> = {{val|33,554,432}}
|-
| (2<sup>25</sup>)<sup>2</sup> = 2<sup>50</sup> = {{val|1,125,899,906,842,624}}
|-
| (2<sup>50</sup>)<sup>2</sup> = 2<sup>100</sup> = {{val|1,267,650,600,228,229,401,496,703,205,376}}
|}
This series of steps only requires 8 multiplications instead of 99.

In general, the number of multiplication operations required to compute {{math|''b''<sup>''n''</sup>}} can be reduced to <math>\sharp n +\lfloor \log_{2} n\rfloor -1,</math> by using [[exponentiation by squaring]], where <math>\sharp n</math> denotes the number of {{math|1}}s in the [[binary representation]] of {{mvar|n}}. For some exponents (100 is not among them), the number of multiplications can be further reduced by computing and using the minimal [[addition-chain exponentiation]]. Finding the ''minimal'' sequence of multiplications (the minimal-length addition chain for the exponent) for {{math|''b''<sup>''n''</sup>}} is a difficult problem, for which no efficient algorithms are currently known (see [[Subset sum problem]]), but many reasonably efficient heuristic algorithms are available.<ref>{{cite journal |last1=Gordon |first1=D. M. |title=A Survey of Fast Exponentiation Methods |journal=Journal of Algorithms |volume=27 |pages=129–146 |date=1998 |citeseerx=10.1.1.17.7076 |doi=10.1006/jagm.1997.0913 |url=http://www.ccrwest.org/gordon/jalg.pdf |access-date=2024-01-11  |archive-date=2018-07-23  |archive-url=https://web.archive.org/web/20180723164121/http://www.ccrwest.org/gordon/jalg.pdf |url-status=dead }}</ref> However, in practical computations, exponentiation by squaring is efficient enough, and much more easy to implement.