> While this isn’t recursive, there’s still an n−1 unnecessary matrix multiplications. These are expensive time-wise and it seems like there should be a simple

> While this isn’t recursive, there’s still an n−1 unnecessary matrix multiplications. These are expensive time-wise and it seems like there should be a simple formula involving n. Computing the nth power of the matrix takes only log n iterations [1]. So the overhead will be much less than n-1. [1] http://en.wikipedia.org/wiki/Exponentiation_by_squaring http://en.wikipedia.org/wiki/Exponentiation_by_squaring