# Algorithm for calculating $A^n$ with as few multiplications as possible

Is there an algorithm for working out the best way (i.e. fewest multiplications) of calculating $A^n$ in a structure where multiplication is associative?

For example, suppose $A$ is a square matrix. Matrix multiplication is associative, and I can compute $A^9$ with $4$ multiplications:

$$A^2 = A \cdot A$$

$$A^3 = A^2 \cdot A$$

$$A^6 = A^3 \cdot A^3$$ $$A^9 = A^6 \cdot A^3$$

One method which works is to compute $A^{2^i}$ and use the binary representation of $n$, but this is not always optimal, e.g. with $n=23$, we can do it in $6$ multiplications:

$$A^2 = A \cdot A$$

$$A^3 = A^2 \cdot A$$

$$A^5 = A^3 \cdot A^2$$

$$A^{10} = A^5 \cdot A^5$$

$$A^{20} = A^{10} \cdot A^{10}$$

$$A^{23} = A^{20} \cdot A^3$$

rather than $7$:

$$A^2 = A\cdot A$$ $$A^4 = A^2 \cdot A^2$$ $$A^8 = A^4 \cdot A^4$$ $$A^{16} = A^8 \cdot A^8$$ $$A^{20} = A^{16} \cdot A^4$$ $$A^{22} = A^{20} \cdot A^2$$ $$A^{23} = A^{22} \cdot A$$

Is there an algorithm which gives the quickest way?

-
Isn't this a Project Euler problem? –  John Gietzen Jul 26 '10 at 17:34
@John: Yes, finding the number of multiplications for n=1:200 is problem 122. –  Larry Wang Jul 26 '10 at 18:13

There seems to be no efficient algorithm for this. Quoting Wikipedia on Addition-chain exponentiation:

… 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. 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 simultaneously. In practice, therefore, shortest addition-chain exponentiation is primarily used for small fixed exponents for which a shortest chain can be precomputed and is not too large.

On the same page, however, it does link to a reference* of some methods better than binary exponentiation.

One simple example is to use base-N number instead of base-2. e.g. for A510,

with binary:   2 = 1 + 1
3 = 2 + 1
6 = 3 + 3
7 = 6 + 1
14 = 7 + 7
15 = 14 + 1
30 = 15 + 15
31 = 30 + 1
62 = 31 + 31
63 = 62 + 1
126 = 63 + 63
127 = 126 + 1
254 = 127 + 127
255 = 254 + 1
510 = 255 + 255   (15 multiplications)

with base-8:   2 = 1 + 1
3 = 2 + 1
4 = 3 + 1
5 = 4 + 1
6 = 5 + 1
7 = 6 + 1
14 = 7 + 7
28 = 14 + 14
56 = 28 + 28
63 = 56 + 7
126 = 63 + 63
252 = 126 + 126
504 = 252 + 252
510 = 504 + 6      (14 multiplications)

with base-4:   2 = 1 + 1
3 = 2 + 1
4 = 2 + 2
7 = 4 + 3
14 = 7 + 7
28 = 14 + 14
31 = 28 + 3
62 = 31 + 31
124 = 62 + 62
127 = 124 + 3
254 = 127 + 127
508 = 254 + 254
510 = 508 + 2      (13 multiplications)


(I don't know how to choose the optimal N.)

*: Daniel M. Gordon, A survey of fast exponentiation methods, Journal of Algorithms 27 (1998), pp 129–146

-
I'm doing something wrong checking the calculation myself, but David Speyer told me once told me that to find the best b you want to minimize some function whose real minimum occurs at e, and so the best base is either 2 or 3. He asked whether you could find a more clever algorithm which improves the run-time to the one you would get if you used "base e" even though that doesn't make sense. –  Noah Snyder Jul 26 '10 at 15:23
I think Noah is right. Also, I can do your example in 12: 1+1=2; +1=3; +3=6; +6=12; +12=24; +24=48; +48=96; +96=192; +192=384; +96=480; +24=504; +6=510; –  Larry Wang Jul 26 '10 at 17:55
@Kaestur: This shows that algorithm is not optimal. –  kennytm Jul 26 '10 at 18:02

Another option would be to use eigendecomposition . It allows you to raise the eigenvalues in the diagonal of the decomposition A = VDV^-1 to a power. It changes the problem from matrix multiplication to the multiplication of the eigenvalues.

Once in eigendecomposition form you could perform the same addition-chain exponentiation technique but it would be with scalars, not matrices. Much more efficient, because each matrix multiplication has n^3 multiplies, but with ed you would only have n.

More is explained here:

http://en.wikipedia.org/wiki/Matrix_decomposition#Eigendecomposition

-
My intuition tells my that this decomposition is not always useful, can someone who knows more chime in on that? –  Jonathan Fischoff Jul 26 '10 at 21:38
Yes, eigendecomposition is not always useful, most especially if your matrix is "defective" (does not have a complete set of eigenvectors/similar to a "Jordan block" or a matrix with a Jordan block on the diagonal). The Schur decomposition (a similarity transformation of your original matrix to a (quasi)triangular matrix) is what is usually used numerically when evaluating a function of a matrix. On the other hand, for integer exponentiation, I would suppose the research on evaluating matrix polynomials might apply here as well. You might want to look at the Patterson-Stockmayer paper. –  Guess who it is. Aug 6 '10 at 13:15
Thanks for J. for clearing that up for me. –  Jonathan Fischoff Aug 6 '10 at 18:36

I admit, I'm here doing research on that Project Euler problem. So far, all I can come up with are minimum and maximum values and I'm stuck doing it by eye.

I can verify the 510 example can be done in 11 multiplications.

1. x*x=x^2
2. x^2*x=x^3
3. x^3*x^3=x^6
4. x^6*x^6=x^12
5. x^12*x^3=x^15
6. x^15*x^15=x^30
7. x^30*x^30=x^60
8. x^60*x^60=x^120
9. x^120*x^120=x^240
10. x^240*x^15=x^255
11. x^255*x^255=x^510

I can guarantee that's the minimum. Unfortunately, this was an easy example and I'm not sure how to generalize it into a program. At this rate, I may be doing half of the problem by hand...

I'm not sure how much I want to add due to it being a Project Euler problem, but if you express those exponents in binary, I think you may see my strategy, why I thought 510 was an easy example, and why I was so sure it couldn't be reduced to fewer multiplications. And maybe be able to determine some cases where you can't do better than the binary method.

-

There is a good discussion of this problem, though no final solution, in Volume 2 of Knuth's The Art of Computer Programming.

-

This problem looks much like that of finding a ruler of optimal composition of the competing properties to have minimal length and to need only least number of marks. This is then known as the Golomb-ruler -problem. It is not solved but if I recall right there is the method of B. Wichmann, whose solution is always near the optimal. In a german newsgroup we had a discussinon of this and Peter Luschny has set up a page collecting and furtherly developing the discussion and partial solutions ("perfect rulers"). Maybe he has also links to the source-articles of the Wichmann-solution.

Just to show my own fiddling I think there is a good start for developing a strategy. I made a small table of compositions. Though no decisive algorithm pops up it gives at least an impression for a general direction how to construct one. Perhaps helpful....

-

[Edited:This is about solving the Project Euler problem, and not directly about your question. ] Admittedly, I'm quite late but remember having worked out this problem myself. The quickest cut to the solution is to use this OEIS page .

Add up the right hand entries for the first 200 rows, and you're done.As a general hint to Project Euler problems, when all this much theory is required, avoid writing your own programs and look it up somewhere.

-
Can you explain the downvotes? –  Ganesh Oct 21 '11 at 20:55