Calculate pow function with mod?

Revision en1, by Hd7, 2019-10-05 18:58:27

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?

Tags #power exponentiation

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Hd7 2019-10-05 18:58:27 749 Initial revision (published)