整数快速乘法/快速幂+矩阵快速幂+Strassen算法

2017年02月24日 18点热度 0人点赞 0条评论

快速幂算法可以说是ACM一类竞赛中必不可少,并且也是非常基础的一类算法,鉴于我一直学的比较零散,所以今天用这个帖子总结一下

快速乘法通常有两类应用:一、整数的运算,计算(a*b) mod c  二、矩阵快速乘法

一、整数运算:(快速乘法、快速幂)

先说明一下基本的数学常识:

(a*b) mod c == ( (a mod c) * (b mod c) ) mod c //这最后一个mod c 是为了保证结果不超过c

对于2进制,2n可用1后接n个0来表示、对于8进制,可用公式 i+3*j == n (其中 0<= i <=2 ),对于16进制,可用 i+4*j==n(0 <= i <=3)来推算,表达形式为2i 后接
j 个0。

 

接下来让我们尽可能简单的描述快速乘法的思想:

a*b

快速乘法的基本思想 ,是二进制和乘法分配律的结合,(不由得想起浮点数不满足结合律,严重吐槽!!!╮(╯-╰)╭),比如说,13 ==(1101)2  ,4*13等于4*(1101)2
用分配律展开得到4*13 == 4*(1000+100+1)2,我们不难观察出,快速幂可以通过判断当前的位(bit)是1还是0,推断出是否需要做求和操作,每次移动到下一位(bit)时,就对ans进行*2操作,等待是否求和。由于除以2和位移操作是等效的,因此这也可以看作是二分思想的应用,这种算法将b进行二分从而减少了不必要的运算,时间复杂度是log(n)。

 

a^b

快速幂其实可以看作是快速乘法的特例,在快速幂中,我们不再对ans进行*2操作,因为在a^b中b的意义已经从乘数变成了指数,但是我们可以仍然把b写成二进制,举例说明:此时,我们将4*13改为4^13,13=(1101)2
二进制13写开我们得到(1000+100+1),注意,这里的所有二进制是指数,指数的相加意味着底数相乘,因此有4^13 == 48 * 44 * 41。再注意到指数之间的2倍关系,我们就可以用很少的几个变量,完成这一算法。这样,我们就将原本用循环需要O(n)的算法,改进为O(logN)的算法。

 

按照惯例,给出尽可能简洁高效的代码实现 (以下所有int都可用long long 代替

首先,给出快速乘法的实现:

整数快速乘法/快速幂+矩阵快速幂+Strassen算法
1 //快速乘法 
2 int qmul(int a,int b){// 根据数据范围可选择long long 
3     int ans=0;
4     while(b){
5         if( b&1)ans+=a;//按位与完成位数为1的判断
6         b>>=1;a<<=1;//位运算代替/2和*2
7     }
8     return ans;
9 }
整数快速乘法/快速幂+矩阵快速幂+Strassen算法

如果涉及到快速乘法取模,则需要进行一些微小改动

改动所基于的数学原理,请参考红色字体标出的数学常识

整数快速乘法/快速幂+矩阵快速幂+Strassen算法
1 //快速乘法取模 
2 int qmul_mod(int a,int b,int mod){
3     int ans=0;
4     while(b){
5         if((b%=mod)&1)ans+=a%=mod;//这里需要b%=mod 以及a%=mod 
6         b>>=1;a<<=1;
7     }
8     return ans%mod;  //ans也需要对mod取模 
9 }
整数快速乘法/快速幂+矩阵快速幂+Strassen算法

 

接下来是快速幂的实现:

整数快速乘法/快速幂+矩阵快速幂+Strassen算法
 1 //快速幂 a^b 
 2 int qpow(int a,int b){
 3     if(a==0)return 0;//这是个坑,校赛被坑过,很多网上的实现都没写这一点
 4     int ans=1;
 5     while(b){
 6         if(b&1)ans*=a;//和快速乘法的区别
 7         b>>=1;a*=a;//区别,同上
 8     }
 9     return ans;
10 } 
整数快速乘法/快速幂+矩阵快速幂+Strassen算法

以及含有取模的快速幂:

整数快速乘法/快速幂+矩阵快速幂+Strassen算法
int qpow_mod(int a,int b,int mod){
    if(a==0)return 0;
    int ans=1;
    while(b){
        if(b&1)ans=(ans%mod)*(a%mod);//如果确定数据不会爆的话,可写成 ans*=a%=mod;
        b>>=1;a*=a%=mod;//等价于a=(a%mod)*(a%mod),且将一个模运算通过赋值代替,提高了效率
    }
    return ans%mod;//数据不会爆的话,这里的%运算会等价于第5中不断重复的 ans%mod
}
整数快速乘法/快速幂+矩阵快速幂+Strassen算法

 

如果我们对于性能还有更进一步的要求,那么也就是减少取模运算了,那么我们需要确定数据范围不会爆掉

在这样的前提下,我们可以只用原先1/4的取模运算量完成快速幂

整数快速乘法/快速幂+矩阵快速幂+Strassen算法
int qpow_mod(int a,int b,int mod){
    if(!a)return 0;
    int ans=1;
    while(b){
        if(b&1)ans*=a%=mod;//这里的模运算只有一个
        b>>=1;a*=a;//这里的模运算没有了
    }
    return ans%mod;
}
整数快速乘法/快速幂+矩阵快速幂+Strassen算法

这些天找了好久,终于找到了纯粹的整数快速幂题目,按照惯例,给一波传送门:

poj1995:http://poj.org/problem?id=1995

 

这个题。。。没什么好说的,但是需要注意,用1/4模运算量的那种写法,数据会爆,所以必须写成完全取模的运算,这样程序会慢一点。。。呜呜呜,63ms水过,这是目前我做的最慢的了,如果大神知道如何在16ms及以下A掉它,欢迎联系我谢谢~o(* ̄▽ ̄*)ブ

整数快速乘法/快速幂+矩阵快速幂+Strassen算法

实现的代码如下:

整数快速乘法/快速幂+矩阵快速幂+Strassen算法 View
Code

 

先更新到这,有时间再更新矩阵的Strassen算法以及矩阵快速幂,,大家稍后见(●'◡'●)

2016-06-13 16:47:56

大家好,我又回来啦

二、矩阵运算:(快速幂)(Strassen算法有空再说)

矩阵的快速幂运算,其实思路和上面的整数快速幂是一样的,对指数进行二分,不过我们对于快速幂本身,可能既可以写成函数,也可以写成运算符重载,所以这里我写的是运算符的重载,毕竟重载练得少,得多练一练

首先我们可以定义一个矩阵数据结构,也可以直接用二维数组

1 #define N 100
2 struct matrix{
3     int m[N][N];
4 };

然后我们重载^运算符,完成矩阵m的b次幂的快速幂运算

这里为了我自己代码习惯,我重载了*和*=两种运算符,当然,在写的时候跪在了忘了写函数声明上,毕竟C++不是Java,对于函数声明的顺序有依赖,so~大家记得写函数声明呦

代码如下

整数快速乘法/快速幂+矩阵快速幂+Strassen算法
 1 //矩阵的数据结构
 2 struct matrix{
 3     int m[N][N];
 4 };
 5 matrix operator * (matrix ,matrix);//重载声明
 6 matrix operator *= (matrix,matrix);
 7 matrix operator ^ (matrix a,int b){
 8     matrix ans;
 9     for(int i=0;i)
10         for(int j=0;j//初始化为单位矩阵 
11     if(b&1)ans*=a;
12     b>>=1;a*=a;
13     return ans;
14 }
15 matrix operator * (const matrix a,const matrix b){//朴素矩阵乘法
16     matrix ans;
17     for(int i=0;i)
18         for(int j=0;j)
19             for(int k=0;k)
20                 ans.m[i][j]=a.m[i][k]+b.m[k][j];
21     return ans;
22 }
23 matrix operator *= (matrix a,const matrix b){
24     return a=b*b;
25 }
整数快速乘法/快速幂+矩阵快速幂+Strassen算法
未经允许不得转载!整数快速乘法/快速幂+矩阵快速幂+Strassen算法

update

纸上得来终觉浅, 绝知此事须躬行。