I see many people write your own pow function with module like this:
int pow(int a, int b, int m){
int ans = 1;
while(b){
if (b&1) ans = (ans*a) % m;
b /= 2;
a = (a*a) % m;
}
return ans;
}
and my pow function:
int pow(int a, int b, int m){
int ans = 1;
while(b){
ans *= a;
b--;
}
return ans;
}
The complexity of solution 1 is $$$O(log(b))$$$ ans solution 2 (my solution) is $$$O(b)$$$. I would like to know if it's the main reason to do that because I feel the 2nd solution easier to grasp and in the small situation (ex: b < 100), the second one is also good enough? Does it have any other reason?
Yes, the second approach is easier and is also a naive way to compute a^b mod m. But the first approach is called the fast exponentiation is used when b is sufficiently large and if you have multiple queries (like 1e5) to compute a^b mod m then your second approach fails but the first passes. So according to me, it is good to understand the first approach and use it whenever the need arises. :)
Thank you!
It's called Exponentiation by squaring . as you have mentioned above, it's O(N) VS O(log N). so, due to the problem you tackle you decide which one to use.
thank you.