大数模 幂运算 算法

首先我们先把问题简化一下,看看如何快速求a^b.

先看看我们熟知的两个数学公式:

a^(2c) = (a^c)^2;

a^(2c+1) = a*((a^c)^2);

我们就利用这两个数学公式来解决这个问题,比如a=3,b=13时,我们把b写成二进制的形式13(10)=1101(2),我们从低位到高位运算,每运算一位可以将b右移一位,上面的例子可以转化成3^13 = 3^1 * 3^4 * 3^8,结合上面的两个数学公式我们可以写出如下的代码

#include<iostream>
using namespace std;

int pow(int a,int b)
{
    int result=1;
    while (b) {
        if (b&1) {
            result *=a;
        }
        a*=a;
        b>>=1;
    }
    return result;
}

int main()
{
    int result=pow(3,13);
    cout<<result<<endl;
    return 0;
}

如上面的叙述叙述中可以看出快速pow算法的时间复杂度取决于b的二进制位数,而传统的一位一位累乘的pow算法的时间复杂度取决于b的大小,例如上述例子中,两种算法的运算次数分别为4次,和13次。随着b的增大,效率上的差距是显然的

下面进入我们的主题—大数模幂运算快速算法(a^b % m)

要计算这个,我们首先还要知道一个数学公式:

a^b % m = (…((a % m) * a) % m) ……* a) % m其中a%m有b个

下面我还用上面b=13的例子,利用这个公式来证明下

a^13 % m = ((a^8) % m) * ((a^4) % m) * ((a^1) % m)

证明:

由a^b % m = (…((a % m) * a) % m) ……* a) % m其中a%m有b个得

a^8 % m = (…((a % m) * a) % m) ……* a) % m其中a%m有8个
a^4 % m = (…((a % m) * a) % m) ……* a) % m其中a%m有4个

a^1 % m = (…((a % m) * a) % m) ……* a) % m 其中a%m有1个

所以((a^8) % m) * ((a^4) % m) * ((a^1) % m) = (…((a % m) * a) % m) ……* a) % m 其中a%m有13个 = a^13 % m ;

这种算法称为 加法链(addition chaining)或二进制平方和乘法方法。它用二进制表示了一个简单明了的加法链。
证毕。

由上面我们证明的公式和第一个pow的例子,容易写出代码如下:

int runFermatPow(int a,int b,int m)
{
    int result=1;
    while (b) {
        if (b&1) {
            result*=a;
        }
        a=(a*a)%m;
        b>>=1;
    }
    return result%m;
}

解释:当b=1101(2)时,从第1位开始result累乘,a = (a*a)%m加上循环可以看成表达式(a%m)^2 % m….因为(a%m)^2 % m = a^2 % m ,所以我们可以把a^13%m看成((a^1) % m) ,((a^4) % m) ,((a^8) % m)的累乘,最后对m取模。

但累乘很容易造成溢出,所以我们可以把代码改成如下形式:

int runFermatPow(int a,int b,int m)
{
    int result=1;
    while (b) {
        if (b&1) {
            result=(result*a)%m;
        }
        a=(a*a)%m;
        b>>=1;
    }
    return result;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注