平方求幂 [英] Exponentiation by squaring

问题描述

我在搜索通过平方求幂时，我在那里找到了递归方法，但后来却迷迷糊糊在这个伪代码上，我无法完全理解.

While i was searching for Exponentiation by squaring i got the recursive method there but then i stumbled upon this pseudo code , Which i'm unable to understand fully.

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;
} 

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

if you can give some insight in simple terms it will be of great help

推荐答案

代码依赖于以下事实:

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

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

The loop is doing exactly that: dividing the exponent by two while squaring the base.

示例:

让我们考虑计算3 ^ 13的结果.您可以将指数(13)编写为二进制幂的总和:3^(8+4+1).然后:3^13 = 3^8 * 3^4 * 3^1.

Let's consider computing the result of 3^13. You can write the exponent (13) as a sum of binary powers: 3^(8+4+1). Then: 3^13 = 3^8 * 3^4 * 3^1.

使用上面解释的原理，通过代码中的%2和/2完成对二进制幂的分解.

This decomposition in binary powers is done by the %2, /2 done in the code, using the rationale exponained above.

分步操作:

从3^13开始.作为13%2==1，您将结果乘以3，因为答案确实具有因数3^1.

You start with 3^13. As 13%2==1, you multiply the result by 3, because the answer does have a factor 3^1.

然后将指数除以2，然后将底数(9^6 == 3^12)平方.作为6%2==0，这意味着答案没有没有因数3^2.

Then you divide the exponent by 2 and square the base (9^6 == 3^12). As 6%2==0, this means the answer doesn't have a factor 3^2.

然后将指数除以2，然后将底数(81^3 == 3^12)平方.作为3%2==1，您将结果乘以81，因为答案确实具有因数3^4.

Then you divide the exponent by 2 and square the base (81^3 == 3^12). As 3%2==1, you multiply the result by 81 because the answer does have a factor 3^4.

然后将指数除以2，然后将底数(6561^1 == 3^8)平方.作为1%2==1，您将结果乘以6561，因为答案确实具有因数3^8.

Then you divide the exponent by 2 and square the base (6561^1 == 3^8). As 1%2==1, you multiply the result by 6561 because the answer does have a factor 3^8.

这篇关于平方求幂的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！