Exponentiation by Squaring (computing x^n in Theta(log n))

Computing $x^{n}$ with the four basic operations needs only $\Theta(\log n)$ multiplications, not $\Theta(n)$: repeatedly square the base while halving the exponent, multiplying in an extra $x$ whenever a bit of $n$ is $1$.