Addition-chain exponentiation

Incorrect

Note that the table displayed on the task page is incorrect. Currently for the exponent for a ↑ 15 it has: (d←(b←a × a ) × b ) × d × d × a.

But this means b←a↑2 and d←a↑4 and the result calculated is a↑13 --Rdm 15:04, 27 August 2011 (UTC)

Rationale

Addition-chain exponentiation is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

This page uses content from Wikipedia. The original article was at Addition-chain exponentiation. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)

In cases of special objects (such as with matrices) the operation of multiplication can be excessively expensive. In these cases the operation of multiplication should be avoided or reduced to a minimum.

In mathematics and computer science, optimal addition-chain exponentiation is a method of exponentiation by positive integer powers that requires a minimal number of multiplications. It works by creating a shortest addition chain that generates the desired exponent. 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^{15}$, where the binary method needs six multiplies but a shortest addition chain requires only five:

$a^{15}=a\times (a\times [a\times a^{2}]^{2})^{2}\!$ (binary, 6 multiplications)

$a^{15}=a^{3}\times ([a^{3}]^{2})^{2}\!$ (shortest addition chain, 5 multiplications)

Table demonstrating how to do Exponentiation using Addition Chains

#Multiplications	Exponentiation	Specific implementation of Addition Chains to do Exponentiation
0	a ↑ 1	a
1	a ↑ 2	a × a
2	a ↑ 3	a × a × a
2	a ↑ 4	(b←a × a ) × b
3	a ↑ 5	(b←a × a ) × b × a
3	a ↑ 6	(b←a × a ) × b × b
4	a ↑ 7	(b←a × a ) × b × b × a
3	a ↑ 8	(d←(b←a × a ) × b ) × d
4	a ↑ 9	(c←a × a × a ) × c × c
4	a ↑ 10	(d←(b←a × a ) × b ) × d × b
5	a ↑ 11	(d←(b←a × a ) × b ) × d × b × a
4	a ↑ 12	(d←(b←a × a ) × b ) × d × d
5	a ↑ 13	(d←(b←a × a ) × b ) × d × d × a
5	a ↑ 14	(d←(b←a × a ) × b ) × d × d × b
5	a ↑ 15	(d←(b←a × a ) × b ) × d × d × a
4	a ↑ 16	(h←(d←(b←a × a ) × b ) × d ) × h

The number of multiplications required follows this sequence: 0, 1, 2, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 5, 5, 6, 5, 6, 6, 6, 5, 6, 6, 6, 6, 7, 6, 7, 5, 6, 6, 7, 6, 7, 7, 7, 6, 7, 7, 7, 7, 7, 7, 8, 6, 7, 7, 7, 7, 8, 7, 8, 7, 8, 8, 8, 7, 8, 8, 8, 6, 7, 7, 8, 7, 8, 8, 9, 7, 8, 8, 8, 8, 8, 8, 9, 7, 8, 8, 8, 8, 8, 8, 9, 8, 9, 8, 9, 8, 9, 9, 9, 7, 8, 8, 8, 8...

This sequence can be found at: http://oeis.org/A003313

Task requirements: Using the following values:

$A={\begin{bmatrix}4&-3&4/3&-1/4\\-13/3&19/4&-7/3&11/24\\3/2&-2&7/6&-1/4\\-1/6&1/4&-1/6&1/24\\\end{bmatrix}}$ $m=31415$ and $n=27182$

Repeat task Matrix-exponentiation operator, except use addition-chain exponentiation to better calculate:

$A^{m}$, $A^{n}$ and $A^{n\times m}$.

Also: Display a count of how many multiplications were done in each case.

Note: There are two ways to approach this task:

• Brute force - try every permutation possible and pick one with the least number of multiplications. If the brute force is a simpler algorithm, then present it as a subtask under the subtitle "Brute force", eg ===Brute Force===.
• Some clever algorithm - the wikipedia page has some hints, subtitle the code with the name of algorithm.

Note: Binary exponentiation does not usually produce the best solution. Provide only optimal solutions.

Kudos (κῦδος) for providing a routine that generate sequence A003313 in the output.