Hd7's blog

Calculate pow function with mod?
By Hd7, history, 5 years ago, In English

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?

  • Vote: I like it
  • -27
  • Vote: I do not like it

»
5 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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. :)

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply