快速幂算法

Question

当我搜索平方求幂时，我发现了其中的递归方法，但是后来我偶然发现了这段伪代码，我无法完全理解。

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

如果您能用简单易懂的话语提供一些见解，将会非常有帮助。

- user4890159

---

这是用平方法进行模算术的指数运算，即使用重复平方计算 base^exponent mod modulus。 - Nikos M.

为什么要检查指数是否为奇数？ - user4890159

奇数检查是因为指数可能不是偶数（正好可以被二整除），因此余数应该额外添加。 - Nikos M.

应该是 if (base < 0n) - Joakim L. Christiansen

Answer 1

该代码依赖于以下事实：

x^y == (x*x)^(y/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。

- Juan Lopes

---

为什么要检查指数的奇偶性？ - user4890159

Answer 2

假设您想计算 x 的 y 次方，其中 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.

如果在一个有限的整数模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方式是一种将乘法操作转换为加法和位移操作的技术。

- pasaba por aqui

---

谢谢您的规定！ - User3

Answer 3

这里：

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


    }

}

- Nomadyn

---

这不是答案，只是一个实现，而且并不是 OP 所寻求的！ - Ankur Anand