Using the following observation, one can create a recursive algorithm that computes x^n for an integer n using squaring and multiplication:

[The second line is incorrect, for the power should be –n. — Me@2012-07-14] 

A brief analysis shows that such an algorithm uses log_2 (n) squarings and at most log_2 (n) multiplications. For n > about 4 this is computationally more efficient than naively multiplying the base with itself repeatedly.

— Wikipedia on Exponentiation by squaring

2012.07.14 Saturday ACHK