当我通过平方搜索 幂运算时，我在那里找到了递归方法，但是后来我偶然发现了这个伪代码，我无法完全理解。
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。
3^(8+4+1)
3^13 = 3^8 * 3^4 * 3^1
这种分解在二元权力是由完成%2，/2在代码中完成，使用上述exponained的理由。
%2
/2
一步步：
您从开始3^13。那样13%2==1，您将结果乘以3，因为答案 确实 有一个因数3^1。
3^13
13%2==1
3
3^1
然后，将指数除以2，然后将底数（9^6 == 3^12）平方。因为6%2==0，这意味着答案 没有 因素3^2。
9^6 == 3^12
6%2==0
3^2
然后，将指数除以2，然后将底数（81^3 == 3^12）平方。那样3%2==1，您将结果乘以81，因为答案 确实 有一个因数3^4。
81^3 == 3^12
3%2==1
3^4
然后，将指数除以2，然后将底数（6561^1 == 3^8）平方。如此1%2==1，您将结果乘以6561，因为答案 确实 有一个因数3^8。
6561^1 == 3^8
1%2==1
3^8
