揭秘快速乘算法

桃扇骨 2023-02-14 13:08 1阅读 0赞

**目录**

参考链接1

参考链接2

一、什么是快速乘算法

二、快速乘算法的优点

三、用一个例子揭秘快速乘

四、快速乘算法实现（C++版）

五、趁热打铁——聊聊快速幂算法

--------------------

## [参考链接1][1] ##

## [参考链接2][2] ##

--------------------

# 一、什么是快速乘算法 #

当两个大数进行相乘进行取模（a\*b%c）时，运算a\*b可能会爆long long的范围(如果会python的同学做这种题目的时候或许不用为此困扰)，这时候就需要用到 **快速乘** 算法解决算术溢出的问题。

# 二、快速乘算法的优点 #

1.乘法容易爆范围，但是由于过程中不断取模，所以加法不会爆范围。

2.在计算机中，加法比乘法计算速度快；快速乘算法的本质是把乘法分解为加法，所以计算速度更快。

# 三、用一个例子揭秘快速乘 #

**快速乘**是利用乘法分配律将a\*b分解成多个式子相加（将后面一个乘数转化为二进制的形式计算）求解。例如：12\*11=12\*1011(2)=12\*2^3+12\*2^1+12\*2^0=96+24+12=132

比如算 12\*11 % 5 ，第一个乘数 12 不变，第二个乘数 11 看作二进制的 1011（2）。

用 与（&）运算和移位（<<，>>）运算依次得出 11 的各位数字为 1（2^0） 、1 （2^1）、0（2^2） 、 1（2^3）

当位数为0时不用计算，因为与12相乘得0；当位数为 1 时与12相乘依次得 12、24、48（2^1位上为0，所以不考虑）、 96

计算可转化为 （（12%5）+（24%5）+（96%5））%5=（2+4+1）%5=2

成功避免了大数相乘得过程

# 四、快速乘算法实现（C++版） #

typedef long long LL;
    LL mult_mod(LL a,LL b,LL mod)
    {
     LL res=0;  //注意此处初始化为0不是1
     while(b){
      if(b&1)res=(res+a)%mod;
      a=(a+a)%mod;  //注意此处是加不是乘： 24 %5、48 %5、96 %5
      b=b>>1;//或者 b=b/2;
     }
     return res;
    }

# 五、趁热打铁——聊聊快速幂算法 #

比如算 12^11 %5

(12^1 \* 12^2 \* 12^8) %5=( (12^1 %5) \* (12^2 %5)\* (12^8 %5))%5=3

LL pow_mod(LL a,LL b,LL mod)  //快速幂
    {
      LL res=1;
      while(b){
        if(b&1)res=mult_mod(res,a,mod); //应用快速乘算法
        res%=mod;
        a=mult_mod(a,a,mod);// a依次为 12^2 %5,12^4 %5,12^8 %5
        a%=mod;
        b=b>>1; //或b=b/2;
      }
      return res;
    }

[1]: https://www.cnblogs.com/960571726y/p/10564138.html
[2]: https://www.jianshu.com/p/ec0b97676c3e