title: Iterative implementation of pow(x, n)
body: <p>I've found an iterative implementation of pow(x, n) which takes o(log n) time and constant space like below:</p>
  
  <pre><code>double pow(double x, int n) {
      double left = x;
      double right = 1;
  
      if (n&lt;0) return 1/(x*pow(x,-n-1)); // Avoid binary overflow!!!!
  
      if (!n) return 1;
  
      while (n&gt;1)
      {
          if (n%2==1) right *= left;
          left = left * left;
          n = n/2;
      }
  
      return left * right;
  }
  </code></pre>
  
  <p>But I couldn't find any explanation of this algorithm. I understand the recursive solution using divide and conquer technique and I guess this solution uses similar trick. But I don't understand exactly why this works. Can anyone please explain this algorithm to me?
  Thanks!</p>