Euclid’s algorithm

转自

       欧几里德，公元前4世纪的伟大数学家。Euclid’s algorithm第一次发表在他的经典著作《Elements》中。这也是能发现的最早的正式的对算法的描述，在此之前，算法一直被非正式的描述成执行各种计算指令的过程。直至今日这个算法依然被广泛应用。

欧几里德算法一般被用来计算两个整数的最大公约数(Greatest Common Divisor), 下面我们用gcd(a,b)表示计算a,b的最大公约数。那么欧几里德算法可以表示为下面的一个等式：

gcd(a,b) = gcd(b,a mod b)

这里对输入做些要求：a,b 为非负整数，并且不能同时为零。因为如果b<0，则gcd(a,b) = gcd(a, |b| )。

证明：

设 a = qb + r 其中 0 <= r < b 并且 gcd(a, b) = d，则 d|a, d|b，所以d|r = a - qb。假设存在d’>d，且d’|b, d’|r，所以d’|a =  qb+r，所以d’也为a, b的公约数，与d = gcd(a, b)矛盾。所以 d = gcd(b, r) = gcd(b, a mod b) = gcd(a, b)。 得证。

举例：

gcd(2322,654) = gcd(654,360) = gcd(360,294) = gcd(294,66) = gcd(66,30) = gcd(30,6) = gcd(6,0) = 6

算法的自然语言描述：

算法的伪代码：

ALGORITHM Euclid(m,n)

//Computers gcd(m,n) by Euclid’s algorithm

//Input: Two nonnegative, not-both-zero integers m and n

//Ouput: Greatest common divisor of m and n

while n != 0 do

    r = m mod n

    m = n

    n = r

return m

简单的Java代码实现：

public class Algorithm {

public static int gctEuclid(int m, int n) {
int r;
while (n != 0) {
r = m % n;
m = n;
n = r;
}
return m;
}

public static void main(String[] args) {
System.out.print(Algorithm.gctEuclid(60, 24));
}

}

以上都是最基本的关于欧几里德算法内容。我们看看这个算法有意思的地方。

欧几里德算法除了可以计算gcd以外，还可以帮我们求出d的关于a和b的线形组合。可以表述为如下公式（）：

as + bt = gcd(a, b)

例如  2322 x 20 + 654 x (-71) = 6

我们来看看具体的计算过程：

我们假设

a - q0b = r0

b - q1r0 = r1

r0 - q2r1 = r2

…

rn-3 - qn-1rn-2 = rn-1

rn-2 = qnrn-1

以上其实就是欧几里德算法的迭代过程。我们从头开始把每一个等式右边的rk带入下一个等式：

 b - q1(a - q0b) = k1a + l1b = r1

(a - q0b) - q2(k1a + l1b) = k2a + l2b = r2

(k1a + l1b) - q3(k2a + l2b) = k3a + l3b = r3

…

(kn-3a + ln-3b) - qn(kn-2a + ln-2b) = kn-1a + ln-1b = rn-1

 我们以a = 756，b = 595举例，并记录下各个迭代过程中的 r, q, k, l 值如下：

r	q	k	l
756		1	0
595	1	0	1
161	3	1	-1
112	1	-3	4
49	2	4	-5
14	3	-11	14
7	2	37	-47
0

这时你会发现一个有意思的规律，用上一行的K,l的值分别减去本行q乘以本行K,l的值，可以计算出下一行k,l的值。 例如：第三行 k = 1 - 1 x 0 = 1，l = 0 - 1 x 1 = -1；又如第6行 k = -3 - 2 x 4 = -11，l = 4 - 2 x (-5) = 14

最后我们可以看到：gcd(756,595) = 7 = 756 x 37 + 595 x (-47)