Power - The Idea

Notice this: $x^{10} = (x^5)^2$. If you compute $x^5$ once, you can square it to get $x^{10}$. That's 1 multiplication instead of 5.

This is exponentiation by squaring. When $n$ is even, compute $x^{n/2}$ and square it. When $n$ is odd, compute $x^{(n-1)/2}$, square it, and multiply by $x$ once more.

Each step cuts $n$ roughly in half. Instead of $O(n)$ steps, you do $O(\log n)$ steps. For $n = 10^9$, that's about 30 multiplications instead of a billion.