Power function

In C/C++ (and also other languages), we have the built in power function to raise a number to a given power. What if we need to calculate the power of a number to 100, like \(2^{100}\)? This is often the case in competitive programming. Maybe we'll run a loop 100 times and calculate it, but this is so inefficient. So, we need to find a power function which can calculate the power to a given number really fast.

Let's consider the expression \(2^{100}\). We can rewrite this to \((2^{50})^{2}\) and the result will not change. Now, we have a smaller power to calculate, right? We can again, rewrite the previous expression to \(((2^{25})^{2})^{2}\). Note that, it was possible to rewrite the expression by halving the power inside the parenthesis only because the power was even. If we were try and rewrite an odd power, it wouldn't be possible. We cannot divide an odd number to half evenly (e.g 25 cannot be divided by 2 evenly). What can we do then? We can just multiply the number itself to balance the power (increase the power by one, to make it odd). Let's rewrite the last expression:
$$
((2^{24+1}))^{2})^{2}
\\ = ((2*2^{24}))^{2})^{2}
\\ = ((2*(2^{12})^{2})^{2})^{2}
$$ The result is still the same. We can go on like this until the power becomes zero. We can see that this pattern keeps repeating and after each step, its calculating a smaller state, its a recursive problem! Here's a picture taken from http://www.shafaetsplanet.com/planetcoding/?p=936 demonstrating the recurring steps.

Implementation in code:

int POW(int x, int p) {
   // x^0 = 1 where x is any number
   if (p == 0) return 1;
   
   // if the power is not even, then multiply the number
   // itself to balance it as stated in the post
   if (p % 2 != 0) {
    int n = POW(x, p/2);
    return x * n * n;
   } else {
    int n = POW(x, p/2);
    return n * n;
   }
}