欧几里德算法(Euclid)阐述了一种gcd算法。gcd(greatest common divisor),简言之,我们想求gcd(x,y),假设(x>y),如果存在下式:x = q*y + r,那么则有gcd(x,y) = gcd(y,r) ,其实上式也称为
gcd递归定理,即gcd(a,b) = gcd (b,a mod b)。
这个递归式看似很简单。实则它还是很值得推敲的,首先,它怎么证明?其次,该算法的运行时间为如何?
在密码学中,欧几里德算法有着相当广泛的应用,譬如求乘法逆元,大整数分解等等。。
在<<编程之美>>一书中,给出了不少gcd算法的简单实现。因为gcd算法的实现是递归,所以要特别注意栈溢出。先做个标记,以后会把栈详细分析一下。
最简单的gcd算法:
1
int gcd(int x, int y)
2![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
3
if(y == 0) return x;
4
if(x < y) return gcd(y,x);
5
else return gcd(y, x%y);
6
} ACM中常用的gcd算法:
1![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
int gcd(int a, int b)
{ return a == 0 ? b : gcd(b % a, a); } 经过优化的gcd算法(分成奇偶两种情况):
1
int gcd(int x,int y )
2![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
3
if(x < y) return gcd(y,x); // x>y
4
if( y == 0) return x; // if y=0, x is GCD
5
else
6![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
7
if( !(x%2) )
8![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
9
if( !(y%2) ) //x,y both even
10
return 2*gcd(x >> 1, y >> 1);
11
else // x is even, y is odd
12
return gcd(x >> 1, y );
13
}
14
else
15![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
16
if( !(y%2) ) // x is odd, y is even
17
return gcd(x, y >> 1);
18
else // x, y both odd
19
return gcd(y,x-y);
20
}
21
}
22
}
23![](/Images/OutliningIndicators/None.gif)