一个博客

随便写写

0%

初等变换法求逆元的优化

发表于

之前老师说了我的方法效率可能不如递归的，所以我想了一下初等变换法能够优化成什么样。

明确目标

首先明确我们的目标，我们要求的只是乘法逆元，不是要求x和y，所以我们不需要求y，所以第一步就是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int inv(int a,int b){
	int m[2][2]={
	    {a,1},
	    {b,0}
	};
	for(int i=0,j=1;m[i][0];i^=1,j^=1){
	    int k=m[i][0]/m[j][0];
	    m[i][0]%=m[j][0];
	    m[i][1]-=k*m[j][1];
	    if(m[i][0]==1)
	        return (m[i][1]+b)%b;
	}
	return -1;
}

就这一步，我们就已经减少了一半的乘法运算了，看来或许可行。

循环展开

我原来的算法用了i和j反复异或1，来达到在0和1反复跳转实现辗转，但是我们可以发现，不管进行多少次辗转，a、b最终状态必定是0和1，上一个状态是常数和1，我们需要的也就是为1的那一列下的分量，所以可以写成：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int inv(int a,int b){
	int m[2][2]={
	    {a,1},
	    {b,0}
	};
	while(1){
	    m[0][1]-=m[0][0]/m[1][0]*m[1][1];
	    m[0][0]%=m[1][0];
	    m[1][1]-=m[1][0]/m[0][0]*m[0][1];
	    m[1][0]%=m[0][0];
	    if(m[0][0]==1)
	        return (m[0][1]+b)%b;
	    if(m[1][0]==1)
	        return (m[1][1]+b)%b;
	}
}

这样就需要保证传入的a和b互质，不然就是死循环。

除法取余优化

本来到上面应该差不多了，但是我依稀记得，底层的实现里面，除法是同时获取商和余数的，然后我就查到了<stdlib.h>里面有个函数叫div，能返回一个结构体，包含商和余数，那就还能优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int inv(int a,int b){
	div_t n;
	int m[4]={a,b,1,0};
	while(1){
	    n=div(m[0],m[1]);
	    m[0]=n.rem;
	    m[2]-=m[3]*n.quot;
	    n=div(m[1],m[0]);
	    m[1]=n.rem;
	    m[3]-=m[2]*n.quot;
	    if(m[0]==1)
	        return (m[2]+b)%b;
	    if(m[1]==1)
	        return (m[3]+b)%b;
	}
}

这样应该就是最终版本了，不过能不能优化就不知道了。

效率分析

效率分内存和时间，内存上不用说了，递归每次递归都要开个栈，递归占用内存肯定比迭代多的。

时间上，递归实现每次递归需要执行

  • 1次判断
  • 1次取余
  • 1次除法
  • 1次乘法
  • 1次减法

迭代实现，注意迭代的一次循环内执行了两次辗转，每两次辗转执行了

  • 2次判断
  • 2次取余
  • 2次除法
  • 2次乘法
  • 2次减法

时间复杂度几乎一样了，如果div真的能同时取余的话那就相当于比递归实现少了每次的取余，不过用正常写法效率也不低了，实际使用最好不要用div的写法。

总结，初等变换法时间上和递归法的时间复杂度几乎相同，内存占用是常量级别，递归法内存取决于递归深度，递归法能够同时求出x和y，不过初等变换法也能够通过x很轻易地求出y，$y=\frac{a*x-1}{b}$。