title: Calculating powers (e.g. 2^11) quickly
body: <blockquote>
    <p><strong>Possible Duplicate:</strong><br>
    <a href="https://stackoverflow.com/questions/101439/the-most-efficient-way-to-implement-an-integer-based-power-function-powint-int">The most efficient way to implement an integer based power function pow(int, int)</a>  </p>
  </blockquote>
  
  
  
  <p>How can I calculate powers with better runtime?</p>
  
  <p>E.g. 2^13. </p>
  
  <p>I remember seeing somewhere that it has something to do with the following calculation:</p>
  
  <p>2^13 = 2^8 * 2^4 * 2^1   </p>
  
  <p>But I can't see how calculating each component of the right side of the equation and then multiplying them would help me.</p>
  
  <p>Any ideas?</p>
  
  <p>Edit: I did mean with any base. How do the algorithms you've mentioned below, in particular the "Exponentation by squaring", improve the runtime / complexity?</p>