Raising a matrix to a high power quickly

What is an efficient way to compute $A^n$ for a square matrix $A$ and large integer $n$?

Repeated squaring: about $2\log_2 n$ matrix multiplications. Write $n$ in binary, square $A$ repeatedly and multiply into the result whenever the current bit is $1$; each multiply costs $O(d^3)$ for a $d\times d$ matrix. Alternatively, if $A=PDP^{-1}$ is diagonalisable, $A^n=PD^nP^{-1}$ needs only scalar powers.