Iterative solution to compute powers

I am working on developing an efficient iterative code to compute mⁿ. After some thinking and googling I found this code;

public static int power(int n, int m)
// Efficiently calculates m to the power of n iteratively
{
int pow=m, acc=1, count=n;
while(count!=0)
{
 if(count%2==1)
    acc=acc*pow;
 pow=pow*pow;
 count=count/2;
}
return acc;
}

This logic makes sense to me except the fact that why are we squaring value of pow towards the end each time. I am familiar with similar recursive approach, but this squaring is not looking very intuitive to me. Can I kindly get some help her? An example with explanation will be really helpful.

Solution

This is a very tricky solution to understand. I am solving this problem in leetcode and have found the iterative solution. I have spent a whole day to understand this beautiful iterative solution. The main problem is this iterative solution does not work as like its recursive solution.

Let's pick an example to demonstrate. But first I have to re-write your code by replacing some variable name as the name in your given code is very confusing.

// Find m^n
public static int power(int n, int m)
{
    int pow=n, result=1, base=m;
    while(pow > 0)
    {
        if(pow%2 == 1)  result = result * base;
        base = base * base;
        pow = pow/2;
    }
    return result;
}

Let's understand the beauty step by step. Let say, base = 2 and power = 10.

Calculation		Description
2^10= (2*2)^5 = 4^5	even	We have changed the base to 4 and power to 5. So it is now enough to find 4^5. [base multiplied with itself and power is half
4^5= 4*(4)^4 = 4^5	odd	We separate single 4 which is the base for current iteration. We store the base to result variable. We will now find the value of 4^4 and then multiply with the result variable.
4^4= (4*4)^2 = 16^2	even	We change the base to 16 and power to 2. It is now enough to find 16^2
16^2= (16*16)^1 = 256^1	even	We change the base to 256 and power to 1. It is now enough to find 256^1
256^1 = 256 * 256^0	odd	We separate single 256 which is the base for current iteration. This value comes from evaluation of 4^4.So, we have to multiply it with our previous result variable. And continue evaluating the rest value of 256^0.
256^0	zero	Power 0. So stop the iteration.

So, after translating the process in pseudo code it will be similar to this,

If power is even:
    base = base * base
    power /= 2
If power is odd:
    result = result * base 
    power -= 1

Now, let have another observation. It is observed that floor(5 / 2) and (5-1) / 2 is same. So, for odd power, we can directly set power / 2 instead of power -= 1. So, the pseudo code will be like the below,

if power is both odd or even:
    base = base * base
    power /= 2
If power is odd:
    result = result *  base

I hope you got the behind the scene.