Why is pow(x, y, z) more efficient than (x ^ y) % z?

Question

In many programming languages, the first one is faster. Why is this?

Try read this one, similar to your question http://stackoverflow.com/questions/2940367/what-is-more-efficient-using-pow-to-square-or-just-multiply-it-with-itself — Jun Rikson, Jan 20 '15 at 00:33

score 3 · Accepted Answer · answered Feb 23 '15 at 15:00

pow(x,y,z) is usually implemented like this (Java):

int pow(int x, int y, int mod) {
    long res = 1, p = x;
    while (y > 0) {
        if (y%2 == 1) {
            res = (res*p)%mod;
        }
        p = (p*p)%mod;
        y /= 2;
    }
    return (int)res;
}

It has O(log y) complexity which is much better comparing to O(y) in case of straightforward implementation with y multiplications.

Second benefit is that some languages will use long arithmetic when result of operation exceeds size of machine word (32 or 64 bits). So, in case of straightforward implementation potentially huge number x^y will be computed first and only then modulo z will be taken.

Why is pow(x, y, z) more efficient than (x ^ y) % z?

1 Answers1