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 :slight_smile:

7 Likes

awesome explanation, thanks!

@damn_me:

This is really an awesome explaination.Thank you.

1 Like

@shiva_google Thanks… happy to help :stuck_out_tongue:

Thanks… :slight_smile: