平方求幂

  • Z时代
  • 2024-01-10
  • 分类：问答

当我通过平方搜索

幂运算时，我在那里找到了递归方法，但是后来我偶然发现了这个伪代码，我无法完全理解。

function powermod(base, exponent, modulus) {
    if (base < 1 || exponent < 0 || modulus < 1)
        return -1
    result = 1;
    while (exponent > 0) {
       if ((exponent % 2) == 1) {
           result = (result * base) % modulus;
       }
       base = (base * base) % modulus;
       exponent = floor(exponent / 2);
    }
    return result;
}

如果您可以简单地给出一些见解，那将会有很大的帮助

回答：

该代码依赖于以下事实：

x^y == (x*x)^(y/2)

循环正是这样做的：在对底进行平方时将指数除以二。

让我们考虑计算3 ^ 13的结果。您可以将指数（13）写成二进制幂的和：3^(8+4+1)。然后：3^13 = 3^8 * 3^4 * 3^1。

这种分解在二元权力是由完成%2，/2在代码中完成，使用上述exponained的理由。

您从开始3^13。那样13%2==1，您将结果乘以3，因为答案 有一个因数3^1。

然后，将指数除以2，然后将底数（9^6 == 3^12）平方。因为6%2==0，这意味着答案 因素3^2。

然后，将指数除以2，然后将底数（81^3 == 3^12）平方。那样3%2==1，您将结果乘以81，因为答案 有一个因数3^4。

然后，将指数除以2，然后将底数（6561^1 == 3^8）平方。如此1%2==1，您将结果乘以6561，因为答案

有一个因数3^8。

以上是 平方求幂 的全部内容， 来源链接： utcz.com/qa/397822.html

回到顶部