# EXPONENTIATION- LCH15JEF

I just intend explaining it for better understanding. Exponentiation in the author’s solution is occurring this manner.

Suppose you want to calculate 2^23. Rewrite it as:
2^23= (2^20). (2^3)
= (2^2)^10.(2^3)
= (4)^10. (2^3)

So, basically what author is doing,

``````    long long NF = 1%MOD;
while ( s[j] >= '0' && s[j] <= '9' )
{
long long WNF = 1;
for (int k=1; k<=10; k++)  // this loop is taking care of powers of 10
WNF = mult(NF, WNF);
NF = WNF;
for (int k=1; k <= s[j]-'0'; k++)
NF = mult(NF, F);  // taking care of values
j++;
}
``````

For the first iteration when s[j] is 2 (taking the same above example), WNF=1 AND NF=4(after the execution of sec for loop). Now, in the next iteration, this 4 gets raised to the power of 10.

``````WNF= MULT(NF,WNF);
``````

NF here is 4 currently, WNF =1, now when k=1 in the for loop, WNF = mult(4,1)=4 then WNF= mult(4,4)=16, then for k=2, WNF= mukt(16,4)… and so on till k=10. Thus WNF is now (4)^10. This is because we are breaking up the powers in multiples of 10. Now, in the second for loop, we have NF = mult(4^10,2^3);

So, this is how exponentiation is occurring. Try few cases by your own by breaking the powers in multiples of 10.

I was just trying out this case and it made the whole thing little more clear to me.

Lets calculate:

``````2^234: (2^200).(2^30).(2^4)
= (4^100).(8^10).(2^4)
Then the sequence in which it is getting evaluated is:
Nf=4,
in the next read of 3 of 234, WNf becomes 4^10 and Thus, by the assignment statement NF = 4^10 which further(sec for loop) becomes (4^10).(2^3).
Then, in the next read of 4 of 234, WNF becomes: ((4^10)^10).((2^3)^10). Thus, Nf= ((4^10)^10).((2^3)^10) which further (sec for loop in the same while), NF= ((4^10)^10).((2^3)^10).(2^4) which is the same value we want.
``````

Hope it clears, how powers of 10 are evaluated at every step.
Let me know if any mistakes are there or more clearance is needed…

Happy to help 7 Likes

awesome explanation, thanks!

This is really an awesome explaination.Thank you.

1 Like

@shiva_google Thanks… happy to help Thanks… 