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?