Here is a code form a udemy course that I am currently taking. This piece of code is a recursive solution to solve (a^n)%b
.
int fastExpo(int a, long long n, int MOD) {
if(n == 0)
return 1;
/// (a^n) % MOD
if(n % 2 == 0)
/// a ^ n = ((a ^ 2) ^ (n/2))
return fastExpo((1LL * a * a) % MOD, n / 2, MOD);
/// a ^ n = a * (a ^ (n - 1))
return (1LL * a * fastExpo(a, n - 1, MOD)) % MOD;
}
In this, I didn't understand this line of code: (1LL * a * a) % MOD
. I understand that in case n
is even, (x^n)%MOD = ((x^(n/2))^2)%MOD
, but i didn't get why we are calculating (a^2)%MOD
, while we should be calculating ((a^2)^(1/2))%MOD
. So, can someone explain me how this recursion step is correct and how recursion, in this case, is actually working?
Here when n is even then used
(x^n)%MOD = (((x^2)%MOD)^(n/2))%MOD
which is also true and in code use this.
Because algorithm says (a ⋅ b) mod m = [(a mod m) ⋅ (b mod m)] mod m
Find details here with exaplaination