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? 
 A: 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
A: 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.


*

*x*x=x^2

*x^2*x=x^3

*x^3*x^3=x^6

*x^6*x^6=x^12

*x^12*x^3=x^15

*x^15*x^15=x^30

*x^30*x^30=x^60

*x^60*x^60=x^120

*x^120*x^120=x^240

*x^240*x^15=x^255

*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.
A: 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.... 
A: There is a good discussion of this problem, though no final solution, in Volume 2 of Knuth's The Art of Computer Programming. 
A: [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.
