为什么 pow(x, y, z) 比 (x ^ y) % z 更有效率？

Question

在许多编程语言中，第一种更快。这是为什么？

Answer 1

pow(x,y,z)通常是这样实现的(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;
}

它具有 O(log y) 复杂度，在使用 y 乘法直接实现的情况下，与 O(y) 相比要好得多。

第二个好处是，当运算结果超过机器字（32 或 64 位）大小时，某些语言将使用长算法。因此，在直接实施的情况下，可能会首先计算巨大的数字 x^y，然后才取模 z。