Editing Addition-chain exponentiation (section)

{{Short description|Method of exponentiation using a minimal number of multiplications}}
In [[mathematics]] and [[computer science]], optimal '''addition-chain exponentiation''' is a method of [[exponentiation]] by a positive [[integer]] power that requires a minimal number of multiplications. Using ''the form of'' the shortest [[addition chain]], with multiplication instead of addition, computes the desired exponent (instead of multiple) of the [[base (exponentiation)|base]]. (This corresponds to {{OEIS el |A003313 |Length of shortest addition chain for n}}.) Each exponentiation in the chain can be evaluated by multiplying two of the earlier exponentiation results. More generally, ''addition-chain exponentiation'' may also refer to exponentiation by non-minimal addition chains constructed by a variety of algorithms (since a shortest addition chain is very difficult to find).

The shortest addition-chain [[algorithm]] requires no more multiplications than [[binary exponentiation]] and usually less. The first example of where it does better is for ''a''<sup>15</sup>, where the binary method needs six multiplications but the shortest addition chain requires only five:

:<math>a^{15} = a \times (a \times [a \times a^2]^2)^2 \!</math> (binary, 6 multiplications)
:<math>a^{15} = ([a^2]^2 \times a)^3 \!</math> (addition chain, 5 multiplications).
:<math>a^{15} = a^3 \times ([a^3]^2)^2 \!</math> (addition chain, 5 multiplications).
:<math>a^{15} = (a^3 \times a^4) \times ([a^4]^2) \!</math> (shortest addition chain, 4 multiplications).
{|class=wikitable
|+Table demonstrating how to do ''exponentiation'' using ''addition chains''
|-
!Number of<br>multiplications || Actual<br>exponentiation || Specific implementation of<br>''addition chains'' to do exponentiation
|-
|0|| a<sup>1</sup> || a
|-
|1|| a<sup>2</sup> || a × a
|-
|2|| a<sup>3</sup> || a × a × a
|-
|2|| a<sup>4</sup> || (a × a→b) × b
|-
|3|| a<sup>5</sup> || (a × a→b) × b × a
|-
|3|| a<sup>6</sup> || (a × a→b) × b × b
|-
|4|| a<sup>7</sup> || (a × a→b) × b × b × a
|-
|3|| a<sup>8</sup> || ((a × a→b) × b→d) × d
|-
|4|| a<sup>9</sup> || (a × a × a→c) × c × c
|-
|4|| a<sup>10</sup> || ((a × a→b) × b→d) × d × b
|-
|5|| a<sup>11</sup> || ((a × a→b) × b→d) × d × b × a
|-
|4|| a<sup>12</sup> || ((a × a→b) × b→d) × d × d
|-
|5|| a<sup>13</sup> || ((a × a→b) × b→d) × d × d × a
|-
|5|| a<sup>14</sup> || ((a × a→b) × b→d) × d × d × b
|-
|5|| a<sup>15</sup> || ((a × a→b) × b × a→e) × e × e
|-
|4|| a<sup>16</sup> || (((a × a→b) × b→d) × d→h) × h
|}
On the other hand, the determination of a shortest addition chain is hard: no efficient optimal methods are currently known for arbitrary exponents, and the related problem of finding a shortest addition chain for a given set of exponents has been proven [[NP-complete]].<ref>{{cite journal |first1=Peter |last1=Downey |first2=Benton |last2=Leong |first3=Ravi |last3=Sethi |title=Computing sequences with addition chains |journal=SIAM Journal on Computing |volume=10 |issue=3 |year=1981 |pages=638–646 |doi=10.1137/0210047}}</ref> Even given a shortest chain, addition-chain exponentiation requires more memory than the binary method, because it must potentially store many previous exponents from the chain.  So in practice, shortest addition-chain exponentiation is primarily used for small fixed exponents for which a shortest chain can be pre-computed and is not too large.

There are also several methods to ''approximate'' a shortest addition chain, and which often require fewer multiplications than binary exponentiation; binary exponentiation itself is a suboptimal addition-chain algorithm. The optimal algorithm choice depends on the context (such as the relative cost of the multiplication and the number of times a given exponent is re-used).<ref>{{cite journal |last1=Gordon |first1=Daniel M. |year=1998 |title=A survey of fast exponentiation methods |journal=J. Algorithms |volume=27 |pages=129–146 |citeseerx=10.1.1.17.7076 |doi=10.1006/jagm.1997.0913 |url=https://www.dmgordon.org/papers/jalg.pdf}}</ref>

The problem of finding the shortest addition chain cannot be solved by [[dynamic programming]], because it does not satisfy the assumption of [[optimal substructure]].  That is, it is not sufficient to decompose the power into smaller powers, each of which is computed minimally, since the addition chains for the smaller powers may be related (to share computations).  For example, in the shortest addition chain for ''a''<sup>15</sup> above, the subproblem for ''a''<sup>6</sup> must be computed as (''a''<sup>3</sup>)<sup>2</sup> since ''a''<sup>3</sup> is re-used (as opposed to, say, ''a''<sup>6</sup>&nbsp;=&nbsp;''a''<sup>2</sup>(''a''<sup>2</sup>)<sup>2</sup>, which also requires three multiplies).