title: How to explain this algorithm for calculating the power of a number?
body: <p>I am currently reading Skiena's "The Algorithm Design Manual".</p>
  
  <p>He describes an algorithm for calculating the power of a number i.e. calculate <code>a^n</code>.</p>
  
  <p>He begins by saying that the simplest algorithm is simply <code>a*a*a ... *a</code>, so we have a total of <code>n-1</code> calculations. </p>
  
  <p>He then goes on to say that there is an optimisation for that, and asks us to recognise that:</p>
  
  <pre><code>n = n/2 + n/2
  </code></pre>
  
  <p>and we can also say that </p>
  
  <pre><code>a^n = ((a^n/2)^2)  (a to the n equals a to the n over 2, squared)
  </code></pre>
  
  <p>Which I understand so far. From these equations, he deduces an algorithm which performs only <code>O(lg n)</code> multiplications.</p>
  
  <pre><code>function power(a, n)
    if (n = 0) 
      return(1)
  
    x = power(a,n/2)
  
    if (n is even)       
      return(x^2)
    else             
      return(a*x^2)
  </code></pre>
  
  <p>It appears that <code>x</code> must be the current value computed so far. But still after reading this several times, I don't understand how from those equations he designed this algorithm, or even how it works. Can anyone explain?</p>