快速幂运算(只适用于正整数计算)


a的b次方要计算多久?计算机要执行b次相乘运算是吧,但是可以通过快速幂运算算法来优化运算时间,时间复杂度从O(N)降到可观的O(log₂N)。
原理:
我们首先把b次方用二进制表示,假如b=11,则把他转化二进制则为,二进制中从左到右,这些1分别代表十进制的8, 2, 1,由同底数幂相乘公式可知。现在定义一个,用于存储随着指数不断变化的值,现在表示,然后用一个用于计算总值。可以结合下面代码进行理解:

#include<iostream> 
using namespace std;
long a, b, base, total=1; //a底数, b指数,base不断变化的基数,tatal最终值,初始化为1是因为最终值至少为1
int main()
{
    cin>>a>>b;
    base = a; 
    long q = b;
    while(q>0) //如果指数还存在就计算
    {
        if(q&1) //如果指数的二进制最后一位为1则和其对应位置基数相乘
        total = base*total;
        base = base*base; //基数永远在随着二进制位匹配次数增加
        q>>=1; //指数的二进制右移一位
    }
    cout<<a<<"^"<<b<<"="<<total;
    return 0;
}

以上是普通快速幂的计算,比较好理解,下面是高精度快速幂的代码,输入的n代表次方数,求的是2的n次方-1,这个数叫麦森数,只需要输出最终值的后500位,不足500位的位数补0,不要问我代码为什么是这样的(我都懵懵懂懂的),反正背下来就是了(笑)。
上代码:

#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
int sav[1001], res[1001], base[1001];
void result_1()
{
    memset(sav, 0, sizeof(sav));
    for(int i=1; i<=500; i++)
    for(int j=1; j<=500; j++)
    sav[i+j-1] += res[i]*base[j];
    for(int i=1; i<=500; i++)
    {
        sav[i+1] += sav[i]/10;
        sav[i] %= 10;
    }
    memcpy(res, sav, sizeof(res));
}
void result_2()
{
    memset(sav, 0, sizeof(sav));
    for(int i=1; i<=500; i++)
    for(int j=1; j<=500; j++)
    sav[i+j-1] += base[i]*base[j];
    for(int i=1; i<=500; i++)
    {
        sav[i+1] += sav[i]/10;
        sav[i] %= 10;
    }
    memcpy(base, sav, sizeof(base));
}
int main()
{
    int n;
    cin>>n;
    cout<<(int)(log10(2)*n+1)<<endl;
    base[1] = 2;
    res[1] = 1;
    while(n>0)
    {
        if(n%2) result_1();
        n>>=1;
        result_2();
    }
    res[1]-=1;
    for(int i=500; i>=1; i--)
    i%50==0&&i!=500?cout<<endl<<res[i]:cout<<res[i];
    return 0;
}

声明:Kira's Blog|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - 快速幂运算(只适用于正整数计算)


Truth is I missed those summer days