搞懂快速幂算法和取模定理

1,460次阅读
一条评论

今天又学习了一个算法,断断续续的花了两个小时给搞懂了,不得不感叹,算法真的太强了,简化超级多的步骤,太强了,太强了,太强了👍

首先说下,快速幂解决的是什么问题,核心问题是解决计算机“受不了的数”问题,试想一个场景,如果让你算下 2^{120}后三位的值,你会咋办?可能你会说 so easy,你的解法是硬算、巧算、还是智算。请听我细细道来:

1、幂函数 硬算

使用 pow 函数硬算代码如下:

#include<cmath>
int main(){
    long long int x;
    x = pow(2,120);
    cout<<x<<endl;
    cout<<x%1000<<endl;
    return 1;
}

// 打印
// -9223372036854775808
// -808

咦,为什么出现这种结果呢?那就的说下int 数据类型的大小了,具体可看这篇文章介绍。64位编译器下,int 一 般是占用 4 个字节,long long int 占用 8 个字节,除去首位的符号标志位,所能容纳的最大 2^{8*8-1}-1=9223372036854775807,而 2^{120}远远的超过这个数,所以累死电脑也算不出来的,更不用说怎么算它的后三位了。

来来改进一下,使用一波取模定理来优化优化

2、取模定理 巧算

取模运算解决的多个大数相乘所得结果过大(计算机不支持)而取不了后几位的问题,取模定理我也是第一次听,看了之后发现是真的牛,不亏是数学定理。这里就不细说了,具体可看我的==另一篇文章==,取模定理具体内容:

(a + b) % p = (a % p + b % p) % p (1)
(a - b) % p = (a % p - b % p ) % p (2)
(a * b) % p = (a % p * b % p) % p (3)
a ^ b % p = ((a % p)^b) % p (4)

这里仅需看这里面的(3), (a * b) % p = (a%p * b%p) % p,这个就厉害了,乘积的取模等于各个因子取模相乘然就在取模,相当于把数都控制在 p-1 位,这计算数量就超级小了,有木有~

使用取模运算的代码:

int main(){
    long long int result=1;
//    x = pow(2,120);
    clock_t start_time = clock();
    for(int i=0;i<120;++i){
        result = result*2%1000;
    }
    result = result % 1000;

    clock_t end_time = clock();
    cout<<result<<endl;
    cout<<"计算花费时间:"<<double(end_time - start_time)/CLOCKS_PER_SEC<<endl;
    // start_time和end_time的差值计算的是 CPU 运行程序所花费的时钟单元数量,然后在除以CLOCK_PER_SEC(是:CPU 每秒有多少时钟单元数。)
    return 1;
}

// 打印
// 576
// 计算花费时间3e-06  

这速度也太6了吧,而且还算出结果了,数学定理真的太强了,不负我一直爱着它😂,虽然人生中最重要的考试都是数学考砸了。

感受到数学定理的威力了吧,但这就满足了?取模定理仅仅是将数据都给控制在一定位数以内,让数可以计算出来,但是并没有简化计算次数(还是120次),要是有简化计算步骤的算法就更好了。俗话说没有最快只有更快😆,有请今天的主角,缩短计算次数的快速幂算法登场:

3、快速幂算法 智算

当我看到这个算法的讲解时,拍案而起,仿佛看到一个新的世界向我招手,那就是算法。算法真的太强了,能把一个复杂的问题,化简成一个个小的问题,循环解决,而且速度还很快。

好了,废话不多说,写正事。先说下,我写文章是为了锻炼自己的写作能力,并且加深对知识的理解,可能我的讲解不太清楚。如看不懂的朋友,可以直接看文章底部的参考文章,大佬写的这个快速幂算法更详细,有需要的可以去看看。

3.1、什么是快速幂算法?

快速幂算法又称为二进制取幂(Binary Exponentiation),能够大幅度的减少计算步骤,从而提升运算速度,是一个在log_n 的时间内计算 的小技巧,而暴力的计算需要 n 的时间。

3.2、算法描述

例如我们计算:a^n ,就相当于是 a^{n1}*a^{n2}……*a^{ns},其中n = n1 + n2 +......+ ns。但是当 n 特别大的时候,计算量就很大,所谓的”指数爆炸“。这里我们可以简化下,a^{2b}=({a^b})^2,瞬间计算量就小了,例如:2^{400}=4^{200}=16^{100}=……,计算一下子少了200步,300步……,效率有木有。

知道了取平方可以缩短计算次数,所以我们可以按照 二进制 来表示幂。那我们来看看幂和二进制之间的关系,还是举个例子讲解:例如:3^{13}=3^{(1101)_2}=3^8*3^4*3^1

是不是发现,这里面只有二进制位是1的才乘到里面,是0的跳过。所以我们只需要用10进制转2进制的方法(不断÷2的余数,直到商为0),即可得到幂数对应的二进制数。如果某一二进制位是1,那就将对应的数乘到结果里面,并且底数也翻倍;如果是0,则底数也翻倍。可看下面的推导过程,这个地方有点绕,跟着过一遍就懂了。

# 1、指数(power)13 对一个二进制,底数(base)为3
13/2 = 6 余1 # base变成3*3=9   result=result*3,base=base*base
6/2 = 3 余0  # base变成9*9=81  base=base*base
3/2 = 1 余1  # base变成81*81=6561  result=result*3,base=base*base
1/2 = 0 余1  # base变成6561*6561   result=result*3,base=base*base
# 所以对应的二进制是 1101

# 2、对应计算代码 Python
def quick(base, power):
    result = 1
    b = power
    while(b>0):
        if b&1:   # 相当于是if b%2 == 1:  为奇数
            result = result * base
        base = base * base
        b >>= 1      # 相当于是 b = b/2    b取一半
    print(result)

quick(3, 13)

# 打印
# 1594323

你以为这样就结束了吗?还差一步呢,快速幂只是缩短了计算次数,但是并没有解决计算高幂次的数后三位的问题(如:2^{120})。可能你会想到,如果加上之前的取模运算,那岂不是把数都给缩小了,就可以计算出结果了。

没错,就是这样,快速幂算法+取模定理一个完美的cp搭配,来一波 c++ 代码:

#include<iostream>
#include<ctime>
using namespace std;

int main(){
    long long int result=1;
    int base = 2,power=120;
    clock_t start_time = clock();
    while(power>0){
        if(power & 1){
            result = result*base%1000;
        }
        base = (base*base)%1000;
        power >>= 1;
    }
    result = result%1000;

    clock_t end_time = clock();
    cout<<result<<endl;
    cout<<"计算花费时间:"<<double(end_time - start_time)/CLOCKS_PER_SEC<<endl;
    cout<<"CPU每秒时钟数:"<<CLOCKS_PER_SEC<<endl;
    return 1;
}

// 打印
// 576
// 计算花费时间:1e-06
// CPU每秒时钟数:1000000

哇,终于写完了,好头疼呀😂~

总结:

算法是真的强,效率很高,爱了,努力学习算法中~

参考文章:

https://blog.csdn.net/qq_19782019/article/details/85621386

https://oi-wiki.org/math/quick-pow/#_2

4
西园公子
版权声明:本站原创文章,由西园公子2021-01-31发表,共计3186字。
转载提示:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(一条评论)
载入中...
西园公子 博主
2021-06-16 08:18:16 回复

可以