通过平方来表示
当我通过平方搜索Exponentiation时我得到了递归方法，但后来我偶然发现了这个伪代码，我无法完全理解。
function powermod(base, exponent, modulus) { if (base < 1 || exponent < 0 || modulus 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)
循环正是这样做：将指数除以2，同时对基数求平方。
一个例子：
让我们考虑计算3 ^ 13的结果。 您可以将指数（13）写为二进制幂的总和： 3^(8+4+1) 。 然后： 3^13 = 3^8 * 3^4 * 3^1 。
二进制幂的这种分解是通过代码中的%2 ， /2完成的，使用上面给出的基本原理。
一步步：
你从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因子。
假设你想用Z中的y计算x ^ y。注意y = y / 2 + y％2（使用“/”作为整数除以“％”作为模数）。
a) if y == 0 then x^y=1; if y==1 then x^y=x; if y==-1 then x^y=1/x. b) If y%2 == 0 then x^y = (x^2)^(y/2) => square x (x'=x^2), divide y by two (y'=y/2), and apply recursively the algorithm to calculate x'^y' = x^y. c) If y%2 == 1 then x^y = (x^2)*((x^2)^(y/2)) => square x (x'=x^2), divide y by two (y'=y/2), and apply recursively the algorithm to calculate x'^y', and after x^y = x'*(x'^y').
这样，只使用整数除法和平方值，您可以计算任何指数。
示例：x ^ 19
1) 19%2==1 [rule c] => x^19=x'*(x'^9) where x' = x^2. 2) 9%2==1 [rule c] => x'^9=x''*(x''^4) where x'' = x'^2. 3) 4%2==0 [rule b] => x''^4=x'''^2 where x''' = x''^2. 4) 2%2==0 [rule b] => x'''^2 = x''''^1 where x''''=x'''^2. 5) x''''^1 [rule a] is immediate.
如果微积分是在整数mod n的有限域上完成的，则逻辑是相同的。
附录
实际上，相同的逻辑可以用于更简单的微积分和更容易理解的数字乘以整数：x * y的问题。
a) if y == 0 then x*y=0; if y==1 then x*y=x; if y==-1 then x*y=-x. b) If y%2 == 0 then x*y = (x*2)*(y/2) => multiply x by 2 (x'=x*2), divide y by two (y'=y/2), and apply recursively the algorithm to calculate x'*y' = x*y. c) If y%2 == 1 then x*y = (x*2)+(x*2)*(y/2) => multiply x (x'=x*2), divide y by two (y'=y/2), apply recursively the algorithm to calculate x'*y', and after x*y = x'+x'*y'.
int方式，产品减少到加法和转移操作。
这里：
public class maths { private float Base; private float Exponent; private float Modulus; private float Result; public float powermod(float base, float exponent, float modulus) { if (base < 1 || exponent < 0 || modulus < 1) { return -1; } while (exponent > 0) { if ((exponent % 2) == 1) { Result = (Result * base) % modulus; } base = (base * base) % modulus; exponent = floor(exponent / 2); } return Result; } public static void main(String[] args) { maths m = new maths(); System.out.println( m.powermod(0, 1, 2)); System.out.println( m.powermod(1, 2, 3)); System.out.println(m.powermod(3, 3, 3)); System.out.println(m.powermod(4, 4, 4)); } }