can anyone explain repeated squaring method of computing a^b%m, I have referred various links, but everywhere only the algorithm is written no one explains how it works.
Anyone please explain repeated squaring method in detail with its working.
You know that (a^n)^2 = a^(2n). So if you have say b=8
a^8=(a^4)^2=((a^2)^2)^2.
This is the logic. however if b is not a power of 2 say 10 then
a^10 = (a^5)^2
a^5 = ((a^4)*a = ((a^2)^2)*a.
This is how you do it . Repeatedly calculate a^(n/2) till n is 1.
ll fast_exp(int base, int exp) {
ll res=1;
while(exp>0) {
if(exp%2==1) res=(resbase)%MOD;
base=(basebase)%MOD;
exp/=2;
}
return res%MOD;
}
why we are doing different thing for odd exp.
We do it different for odd exp. as a odd number cannot be expressed as some 2*z , z->integer. So that difference comes.