学步园

扩展的gcd算法即除了计算gcd(m,n)还要计算整数x和y，使之满足gcd(m,n) = m.x + n.y。 下面的算法中使用迭代方式。 extendedGCD2方法是extendedGCD的简化版本，考虑到在初值向量r{-1} = [1 0], r{0} = [0 1]下，满足递推关系：r{i} = r{i-2} - q{i}.r{i-1}。

采用Euclid's算法时，不仅要r（余数）的值，还需要q(商)的值。

本例实现参考了Wikipedia中介绍的迭代方法：http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

/**<br /> *<br /> * @author ljs 2011-5-17<br /> *<br /> * solve extended gcd using Euclid's Algorithm and Iterative Method<br /> *<br /> */<br /> public class ExtGCD_Euclid {<br /> /**<br /> * caculate x,y to satisfy Bezout Identity: m.x + n.y = gcd(m,n)<br /> * @param m<br /> * @param n<br /> * @return {d,x,y} for: d = m.x + n.y;<br /> */<br /> public static int[] extendedGCD(int m,int n){<br /> m = (m<0)?-m:m;<br /> n = (n<0)?-n:n;</p> <p> if(n == 0 ){<br /> return new int[]{m,1,0};<br /> }</p> <p> int r = m % n;<br /> int q = m / n;<br /> if(r ==0)<br /> return new int[]{n,0,1};<br /> else{<br /> m=n;<br /> n=r;<br /> r = m % n;<br /> int lastq = q;<br /> q = m / n;<br /> if(r==0){<br /> return new int[]{n,1,-lastq};<br /> }else{<br /> int coeffM1=1;<br /> int coeffN1=-lastq;<br /> //r2 = n - q2.r1<br /> int coeffM2=-q;<br /> int coeffN2=1+lastq * q;</p> <p> while(n!=0){<br /> m=n;<br /> n=r;<br /> r = m%n;<br /> q = m / n;<br /> if(r==0){<br /> break;<br /> }else{<br /> //for k-th loop, r{k} = r{k-2} - q{k}.r{k-1}, here q{k} is quotient = m{k} / n{k}<br /> int coeffM3=coeffM1 - q*coeffM2;<br /> int coeffN3=coeffN1 - q*coeffN2;<br /> coeffM1 = coeffM2;<br /> coeffN1 = coeffN2;<br /> coeffM2 = coeffM3;<br /> coeffN2 = coeffN3;<br /> }<br /> }<br /> return new int[]{n,coeffM2,coeffN2};<br /> }<br /> }<br /> }</p> <p> /**<br /> * simplified from the above extendedGCD(m,n)<br /> * @see also "http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm"<br /> * @param m<br /> * @param n<br /> * @return {d,x,y} for: d = m.x + n.y;<br /> */<br /> public static int[] extendedGCD2(int m,int n){<br /> m = (m<0)?-m:m;<br /> n = (n<0)?-n:n;</p> <p> int r00=1,r01=0; //[1 0]<br /> int r10=0,r11=1; //[0 1]</p> <p> int d = 0;<br /> int x = r00;<br /> int y = r01;<br /> while(n!=0){<br /> int remainder = m%n;<br /> int quotient = m/n;</p> <p> if(remainder == 0){<br /> x = r10;<br /> y = r11;<br /> }else{<br /> int tmp0 = r00 - quotient*r10;<br /> int tmp1 = r01 - quotient*r11;<br /> r00=r10;<br /> r01=r11;<br /> r10 = tmp0;<br /> r11 = tmp1;<br /> } </p> <p> m = n;<br /> n = remainder;<br /> }<br /> d = m;</p> <p> return new int[]{d,x,y};<br /> }</p> <p> public static void print(int m,int n,int[] extGCDResult){<br /> m = (m<0)?-m:m;<br /> n = (n<0)?-n:n;<br /> System.out.format("extended gcd of %d and %d is: %d = %d.{%d} + %d.{%d}%5s%n",m,n,extGCDResult[0],m,extGCDResult[1],n,extGCDResult[2],(m*extGCDResult[1] + n * extGCDResult[2] == extGCDResult[0])?"OK":"WRONG!!!");<br /> }</p> <p> public static void main(String[] args) {</p> <p> int m = -18;<br /> int n= 12;<br /> print(m,n,extendedGCD(m,n));<br /> print(m,n,extendedGCD2(m,n));</p> <p> //co-prime<br /> m = 15;<br /> n= 28;<br /> print(m,n,extendedGCD(m,n));<br /> print(m,n,extendedGCD2(m,n));</p> <p> m = 6;<br /> n= 3;<br /> print(m,n,extendedGCD(m,n));<br /> print(m,n,extendedGCD2(m,n));</p> <p> m = 6;<br /> n= 3;<br /> print(m,n,extendedGCD(m,n));<br /> print(m,n,extendedGCD2(m,n));</p> <p> m = 6;<br /> n= 0;<br /> print(m,n,extendedGCD(m,n));<br /> print(m,n,extendedGCD2(m,n));</p> <p> m = 0;<br /> n= 6;<br /> print(m,n,extendedGCD(m,n));<br /> print(m,n,extendedGCD2(m,n));</p> <p> m = 0;<br /> n= 0;<br /> print(m,n,extendedGCD(m,n));<br /> print(m,n,extendedGCD2(m,n));</p> <p> m = 1;<br /> n= 1;<br /> print(m,n,extendedGCD(m,n));<br /> print(m,n,extendedGCD2(m,n));</p> <p> m = 3;<br /> n= 3;<br /> print(m,n,extendedGCD(m,n));<br /> print(m,n,extendedGCD2(m,n));</p> <p> m = 2;<br /> n= 2;<br /> print(m,n,extendedGCD(m,n));<br /> print(m,n,extendedGCD2(m,n));</p> <p> m = 1;<br /> n= 4;<br /> print(m,n,extendedGCD(m,n));<br /> print(m,n,extendedGCD2(m,n));</p> <p> m = 4;<br /> n= 1;<br /> print(m,n,extendedGCD(m,n));<br /> print(m,n,extendedGCD2(m,n));</p> <p> m = 10;<br /> n= 14;<br /> print(m,n,extendedGCD(m,n));<br /> print(m,n,extendedGCD2(m,n));</p> <p> m = 14;<br /> n= 10;<br /> print(m,n,extendedGCD(m,n));<br /> print(m,n,extendedGCD2(m,n));</p> <p> m = 10;<br /> n= 4;<br /> print(m,n,extendedGCD(m,n));<br /> print(m,n,extendedGCD2(m,n));</p> <p> m = 273;<br /> n= 24;<br /> print(m,n,extendedGCD(m,n));<br /> print(m,n,extendedGCD2(m,n));</p> <p> m = 120;<br /> n= 23;<br /> print(m,n,extendedGCD(m,n));<br /> print(m,n,extendedGCD2(m,n));</p> <p> }<br /> }<br />