title: quickest way to calculate powers of 2x2 matrix
body: <p>I have a 2x2 matrix <code>M</code> which is in general complex. What is the quickest way to multiply <code>M</code> by itself <code>n</code> times, i.e. M^n? I can think of two ways:</p>
  
  <p>A. diagonalize it and multiply them</p>
  
  <p>B. Break up <code>n</code> into groups. For instance, if <code>n=15</code>, then I can do the following:</p>
  
  <ol>
  <li>A=M*M</li>
  <li>B=A*A=M^4</li>
  <li>C=B*B=A^8</li>
  <li>M<em>A</em>B*C=M^15</li>
  </ol>
  
  <p>So in total I need to do 6 matrix multiplications.</p>
  
  <p>My questions are:</p>
  
  <ol>
  <li><p>Which method is faster?</p></li>
  <li><p>Are there any other methods to accomplish this?</p></li>
  <li><p>For my second method, how to implement the algorithm for any <code>n</code>? It is easy if <code>n</code> is a power of 2, but when it isn't how to break up the multiplication and grouping like in my example given?</p></li>
  </ol>