【学习笔记】快速幂运算(只适用于正整数计算)

点击量: 229 次


a的b次方要计算多久?计算机要执行b次相乘运算是吧,但是可以通过快速幂运算算法来优化运算时间,时间复杂度从O(N)降到可观的O(log₂N)。

原理:
这主题图片会放大,用不了数学公式,以后不拿这个博客写了
我们首先把b次方用二进制表示,假如b=11,则把他转化二进制则为1011,二进制中从左到右,这些1分别代表十进制的8, 2, 1,由同底数幂相乘公式a^xa^y = a^(x+y)可知a^11=a^8a^2a^1。现在定义一个base = a,用于存储随着指数不断变化的值,现在表示a^1 = a,然后用一个tatal用于计算总值。可以结合下面代码进行理解:

#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;
    if(q==0) total = 0;
    else
    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;
}
 一串神奇的代码
【学习笔记】堆和堆排序 
上一篇:一串神奇的代码
下一篇:【学习笔记】堆和堆排序


已有 2 条评论


  1. repostone
    repostone

    用上代码就感觉复杂啦。

     回复
    1. Kira
      Kira

      啊嘞? qian.png

       回复
点击开始摧毁这篇水文,方向键控制,空格发弹,Esc退出


pao.gifchui.gifpen.gifpai.gifhan.pngxia.pnghuaji.pngwa.pngbi.pngxin.pngleng.pnghua.pngmeng.pngjingya.pngqian.pnghan1.pngquan.pngnu.pnggan.pngdaxiao.pngku.pngqu.png



Proudly published with Typecho))).

Living (*>ω<*)

Copyright @ 2019 Kira's Blog



哎呀,穷死了,求赞赏!

支付宝
微信
QQ
0:00