Time efficiency of Power operation?

Question

I was just wondering about power operations and their time efficiency. Since a power operation is effectively:

x^n = x*x*x...[n times]

Does that mean calculation of x^n takes approximately O(n) time (assuming that multiplication is O(1), which I'm not sure it is)? Or do modern programming languages/hardware architecture have optimizations that reduce that to O(1) or something similar? If there are optimizations that exist, please explain (or post a link to an explanation).

Answer 1

There's an optimization based on successive squaring that allows you to compute powers in a logarithmic number of multiplications. For example, instead of computing b⁸ as b*b*b*b*b*b*b*b, you can compute

b² = b * b
b⁴ = b² * b²
b⁸ = b⁴ * b⁴

See SICP 1.2.4 Exponentiation for more details. I also have a post on my blog that shows a fast exponentiation implementation in Scheme.