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?