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

Question

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

performancepow

3

在许多编程语言中，第一个更快。为什么呢？

- Astrid Yu

尝试阅读这个问题，类似于你的问题：https://dev59.com/D3A85IYBdhLWcg3wF_q0 - Jun Rikson

模块指数运算。 - Mark Adler

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jarlax · Accepted Answer

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次乘法相比要好得多。

其次，当操作结果超过机器字长（32位或64位）时，一些语言将使用长算术。因此，在直接实现的情况下，可能会先计算巨大的数字x^y，然后再取模z。