Addition-chain exponentiation

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.

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 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)

On the other hand, the addition-chain method is much more complicated, since the determination of a shortest addition chain seems quite difficult: 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.

Table demonstrating how to do *Exponentiation* using *Addition Chains*
Number of Multiplications	Actual Exponentiation	Specific implementation of Addition Chains to do Exponentiation
0	a¹	a
1	a²	a × a
2	a³	a × a × a
2	a⁴	(a × a→b) × b
3	a⁵	(a × a→b) × b × a
3	a⁶	(a × a→b) × b × b
4	a⁷	(a × a→b) × b × b × a
3	a⁸	((a × a→b) × b→d) × d
4	a⁹	(a × a × a→c) × c × c
4	a¹⁰	((a × a→b) × b→d) × d × b
5	a¹¹	((a × a→b) × b→d) × d × b × a
4	a¹²	((a × a→b) × b→d) × d × d
5	a¹³	((a × a→b) × b→d) × d × d × a
5	a¹⁴	((a × a→b) × b→d) × d × d × b
5	a¹⁵	((a × a→b) × b × a→e) × e × e
4	a¹⁶	(((a × a→b) × b→d) × d→h) × 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}{\sqrt {\frac {1}{2}}}&0&{\sqrt {\frac {1}{2}}}&0&0&0&\\0&{\sqrt {\frac {1}{2}}}&0&{\sqrt {\frac {1}{2}}}&0&0&\\0&{\sqrt {\frac {1}{2}}}&0&-{\sqrt {\frac {1}{2}}}&0&0&\\-{\sqrt {\frac {1}{2}}}&0&{\sqrt {\frac {1}{2}}}&0&0&0&\\0&0&0&0&0&1&\\0&0&0&0&1&0&\\\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}

.

As an easier alternative to doing the matrix manipulation above, generate the addition-chains for 31415 and 27182 and use addition-chain exponentiation to calculate these two equations:

1.00002206445416³¹⁴¹⁵
1.00002550055251²⁷¹⁸²

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.

C

Using complex instead of matrix. Requires Achain.c. It takes a long while to compute the shortest addition chains, such that if you don't have the chain lengths precomputed and stored somewhere, you are probably better off with a binary chain (normally not shortest but very simple to calculate) whatever you intend to use the chains for. <lang c>#include <stdio.h>

include "achain.c" /* not common practice */

/* don't have a C99 compiler atm */ typedef struct {double u, v;} cplx;

inline cplx c_mul(cplx a, cplx b) { cplx c; c.u = a.u * b.u - a.v * b.v; c.v = a.u * b.v + a.v * b.u; return c; }

cplx chain_expo(cplx x, int n) { int i, j, k, l, e[32]; cplx v[32];

l = seq(n, 0, e);

puts("Exponents:"); for (i = 0; i <= l; i++) printf("%d%c", e[i], i == l ? '\n' : ' ');

v[0] = x; v[1] = c_mul(x, x); for (i = 2; i <= l; i++) { for (j = i - 1; j; j--) { for (k = j; k >= 0; k--) { if (e[k] + e[j] < e[i]) break; if (e[k] + e[j] > e[i]) continue; v[i] = c_mul(v[j], v[k]); j = 1; break; } } } printf("(%f + i%f)^%d = %f + i%f\n", x.u, x.v, n, v[l].u, v[l].v);

return x; }

int main() { cplx r1 = {1.0000254989, 0.0000577896}, r2 = {1.0000220632, 0.0000500026};

init(); puts("Precompute chain lengths"); seq_len(31415);

chain_expo(r1, 27182); chain_expo(r2, 31415); return 0; }</lang>output<lang>Exponents: 1 2 4 8 10 18 28 46 92 184 212 424 848 1696 3392 6784 13568 27136 27182 (1.000025 + i0.000058)^27182 = -0.000001 + i2.000001 Exponents: 1 2 4 8 16 17 33 49 98 196 392 784 1568 3136 6272 6289 12561 25122 31411 31415 (1.000022 + i0.000050)^31415 = -0.000001 + i2.000000</lang>

J

<lang j>vars=: 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz' mul=: '+/ .*' eq=: '=:' b2e=:3 :0 NB. express binary chain as equation

 (|.x{.~##:y) b2e y

 b=. }.#: y 
 v=. (-#b) {. x
 ({.x),eq,(,(mul,~])"0 |.b#v), ([,eq,])/(],mul,])"0 v

)

addch=:3 :0

 p=. q: y
 N=: +/n=. #@#:"0 p
 assert N <: 1+#vars NB. enough variables?
 v=. (|.N{.vars) <@(' ',])/.~ (+/\n) I. 1+i.N
 3}.;v b2e&.> p

)</lang>

This implementation finds an expression which calculates the given exponent. b2e finds the binary chain expression for that exponent. addch finds the addition chain expression.

This implementation of addch uses binary chain for each prime factor of the exponent and combines them.

Example use:

<lang j> mul=: '*'

  addch 15

C*C*C =:A*B*B=:A*A

  addch 31415

L*M*M=:L*L =:G*I*J*K*K*K=:J*J=:I*I=:H*H=:G*G =:A*B*C*F*F*F=:E*E=:D*D=:C*C=:B*B=:A*A

  addch 27182

N*N =:A*B*C*E*I*K*M*M*M=:L*L=:K*K=:J*J=:I*I=:H*H=:G*G=:F*F=:E*E=:D*D=:C*C=:B*B=:A*A

  addch 27182*31415

a*a =:Y*Z*Z=:Y*Y =:T*V*W*X*X*X=:W*W=:V*V=:U*U=:T*T =:N*O*P*S*S*S=:R*R=:Q*Q=:P*P=:O*O=:N*N =:A*B*C*E*I*K*M*M*M=:L*L=:K*K=:J*J=:I*I=:H*H=:G*G=:F*F=:E*E=:D*D=:C*C=:B*B=:A*A</lang>

I tried to compute the expression given by addch 31415 using matrix multiplication as my multiplier, and using

<lang j>A=: ".;._2]0 :0

 4   _3    4r3  _1r4

_13r3 19r4 _7r3 11r24

 3r2 _2    7r6  _1r4
_1r6  1r4 _1r6   1r24

)</lang>

However, I ran out of memory needed to represent the arbitrary precision intermediate results.

When I use floating point values instead of arbitrary precision, the result I got was:

<lang j> mul=: +/ .*

  do addch 31415
_ __  _ __

__ _ __ _

_ __  _ __

__ _ __ _</lang>

Here a single underline represents floating point infinity and a double underline represents negative floating point infinity.

So I have elected to not try to compute the other requested results.

That said, note that this approach exceeds the values given in the A003313 by 1 in 22 cases, when considering the first 100 values in the sequence.