通过平方来表示

Question

当我通过平方搜索 Exponentiation时我得到了递归方法,但后来我偶然发现了这个伪代码,我无法完全理解.

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

如果你能用简单的术语给出一些见解,那将会有很大的帮助

Answer 1

代码依赖于以下事实:

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

循环正是这样做的:将指数除以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.