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).
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 b8 as bbbbbbb*b, you can compute
b2 = b * b
b4 = b2 * b2
b8 = b4 * b4
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.