Stein算法由J. Stein1961年提出,这个方法也是计算两个数的最大公约数。和欧几里德算法不同的是,Stein算法只有整数的移位和加减法,这对于程序设计者是一个福音。
首先需要了解的是:一个奇数的所有约数都是奇数。我们来研究一下最大公约数的性质,我们发现有gcd( k*m,k*n ) = k*gcd( m,n)这么一个非常好的性质(证明就省去了)。说他好是因为他非常符合我们化小的思想。我们试取k=2 ,则有 gcd( 2m,2n ) = 2 *gcd(m,n)。这使我们很快联想到将两个偶数化小的方法。那么一奇一个偶以及两个奇数的情况我们如何化小呢?
我们来看看一奇一偶的情况:设有2x和y两个数,其中y为奇数。因为y的所有约数都是奇数,所以a = gcd( 2m,n)是奇数。根据2x是个偶数不难联想到,a应该是x的约数。我们来证明一下:(2m)%a=0,设2m=n*a,因为a是奇数,2x是偶数,则必有n是偶数。又因为m=(n/2)*a,所以m%a=0,即a是m的约数。因为a也是n的约数,所以a是m和n的公约数,有gcd(2m,n ) <=gcd(m,n)。因为gcd(m,n)明显是2m和n的公约数,又有gcd(m,n) <=gcd(2m,n),所以 gcd(2m,n) =gcd(m,n)。至此,我们得出了一奇一偶时化小的方法。
再来看看两个奇数的情况:设有两个奇数m和n,似乎m和n直接向小转化没有什么太好的办法,我们可以绕个道,把m和n向偶数靠拢去化小。设m>n,我们注意到m+n和m-n是两个偶数,则有gcd( m+n,m-n) = 2 * gcd( (m+n)/2,(m-n)/2 ),那么 gcd(m,n) 与gcd(m+n,m-n) 以及 gcd( (m+n)/2,(m-n)/2 )之间是不是有某种联系呢?为了方便设 x=(m+n)/2 ,y=(m-n)/2 ,容易发现x+y=m ,x-y=n 。设 a = gcd(x,y),则 x%a=0,y%a=0 ,所以(x+y)%a=0,(x-y)%a=0 ,即m%a=0 ,n%a=0 ,所以a是m和n的公约数,有gcd(m,n)<= gcd(m,n)。再设 b = gcd(m,n)肯定为奇数,则 m%b=0,n%b=0,所以 (m+n)%b=0 ,(m-n)%b=0,又因为m+n和m-n都是偶数,跟前面一奇一偶时证明a是m的约数的方法相同,有((m+n)/2)%b=0,((m-n)/2)%b=0 ,即 x%b=0 ,y%b=0,所以b是x和y的公约数,有 gcd(m,n) <= gcd(x,y)。所以 gcd(m,n) =gcd(x,y) = gcd( (m+n)/2,(m-n)/2 )。
我们来整理一下,对两个正整数 m>n:
1.均为偶数 gcd(m,n) =2gcd(m/2,n/2);
2.均为奇数 gcd(m,n) = gcd( (m+n)/2,(m-n)/2 );
2.m奇n偶
3.m偶n奇
现在我们已经有了递归式,还需要再找出一个退化情况。我们用这个:gcd(m,m) = m。
联系客服