If the power is zero, we will return the identity matrix.
If the power is even (2N), we can recursively compute M^N, and then return the square of the obtained matrix.
If the power is odd (2N+1), itβs enough to recursively compute M^2N value, and return the obtained matrix, that has been multiplied by M."
Tidbit: that likely is the best approach in practice, but perhaps surprisingly, it is not optimal in the number of matrix multiplications. See http://en.m.wikipedia.org/wiki/Addition-chain_exponentiation and https://oeis.org/A003313. Wikipedia has a link mentioning addition-subtraction chains, so it may even be beneficial to compute the inverse of the matrix in some cases (M^1023 likely is such a case, if inverting M isn't too hard)
Well -- the thing about using addition chains is, which addition chain do you use? If we're talking about a general algorithm for any n, rather than for a specific n, then we need to algorithmically generate our addition chain. So going with the shortest addition chain is a bad idea, because it will take you too long to find it. Any method of finding short addition chains based on factoring is similarly a bad idea.
(It's worth noting that while finding short addition chains isn't known to be NP-complete, a slight variant of the problem is.)
I think there are methods of finding short addition chains that reliably do better than the binary method, though; in TAOCP volume 2, "Evaluation of powers" section (which is a very good reference on addition chains in general!), Knuth talks about the power tree method, which from a brief skim seems like it might be better even when you include the time to find the chain. I think there might also be better methods based on continued fractions, going from memory.
I'm not certain I understand what's being asked. I'm going to assume you mean, "Could an optimizing compiler for a language with a built-in exponentiation operator use short addition chains to speed up exponentiation at runtime?" In which case, again, the answer depends on whether the exponent is fixed or is allowed to vary.
For a fixed exponent, certainly; you could just spend additional time in the compiler finding short addition chains for all the exponents that are used. When exponents are allowed to vary, then we're in the case I described in my post above -- maybe using the power-tree method, or certain other methods, would improve on the binary method; but finding the shortest addition chain at runtime would not. (By which I mean, not with existing methods, and it seems unlikely that there's any fast way.)
If the power is zero, we will return the identity matrix. If the power is even (2N), we can recursively compute M^N, and then return the square of the obtained matrix. If the power is odd (2N+1), itβs enough to recursively compute M^2N value, and return the obtained matrix, that has been multiplied by M."
Tidbit: that likely is the best approach in practice, but perhaps surprisingly, it is not optimal in the number of matrix multiplications. See http://en.m.wikipedia.org/wiki/Addition-chain_exponentiation and https://oeis.org/A003313. Wikipedia has a link mentioning addition-subtraction chains, so it may even be beneficial to compute the inverse of the matrix in some cases (M^1023 likely is such a case, if inverting M isn't too hard)