[算法]求最大公约数：二进制欧几里德算法(Binary Euclid's Algorithm)

soloforce

zz from:http://www.cut-the-knot.org/blue/binary.shtml

Euclid's algorithm is tersely expressed by the recursive formula
[color="Blue"](1)        gcd(N,M) = gcd(M, N mod M),

where (N mod M) is the remainder of division of N by M. We postulate gcd(N,0) = N in accordance with the end condition of Euclid's algorithm. Our example appears as
        gcd(2322,654) = gcd(654,360) = gcd(360,294) = gcd(294,66) = gcd(66,30) = gcd(30,6) = gcd(6,0) = 6.

Other properties of gcd are expressed in such a similarly concise form

[color="Blue"]   1. gcd(KN, KM) = K gcd(N, M)
   2. If gcd(N,M) = 1 then gcd(N,MK) = gcd(N,K)
   3. gcd(N, M) = gcd(N - M, M)

There are many ways to prove these. For instance, the first and second follow from the Fundamental Theorem of Arithmetic; the second (in a more direct manner) is also a consequence of a generalization of Proposition VII.30 the third one follows from the basic properties of modular arithmetic and division. A binary algorithm for finding gcd(N,M) is based on the following

   1. If N and M are even, gcd(N, M) = 2 gcd(N/2, M/2),
   2. If N is even while M is odd, then gcd(N, M) = gcd(N/2, M),
   3. If both N and M are odd, then (since N-M is even) |N-M| < max(N,M). Replace the largest of the two with |N-M|.

The algorithm is known as binary because, unlike the original one, it does not use general division of integers but only division by 2. Since in a computer numbers are represented in the Binary system anyway, you should not be surprised to learn that there is a special machine instruction that implements division by 2 in a highly efficient manner. This is known as the right shift wherein the rightmost bit is discharged, the remaining bits are shifted one place to the right and the leftmost bit is set to 0.

Another handy operation is a bitwise conjunction &. N & 1 is either 1 or 0 for any integer N. It's 1 iff N is odd. Bitwise conjunction is also implemented in hardware, i.e., as a machine instruction.

The binary algorithm was discovered by R.Silver and J.Tersian in 1962 and has been published by G.Stein in 1967. Convergence of the algorithm, if not obvious, can be shown by induction. Property 3. above assures that induction is applicable.

soloforce

上述算法的ANSI/C语言实现

1. 
   
2. unsigned binary_gcd (unsigned x, unsigned y)
   
3. {
   
4.   unsigned temp;
   
5.   unsigned common_power_of_two = 0;
   
6.   if (x == 0) return y; /* special cases */
   
7.   if (y == 0) return x;
   
8.   /* Find the largest power of two
   
9.      that divides both x and y. */
   
10.   while (((x | y) & 1) == 0)
    
11.     {
    
12.       x = x >> 1; /* or: "x >>= 1" */
    
13.       y = y >> 1;
    
14.       ++common_power_of_two;
    
15.     }
    
16.   while ((x & 1) == 0) x = x >> 1;
    
17.   while (y)
    
18.     {
    
19.       /* x is odd and y is nonzero here. */
    
20.       while ((y & 1) == 0) y = y >> 1;
    
21.       /* x and y are odd here. */
    
22.       temp = y;
    
23.       if (x > y) y = x - y;
    
24.       else y = y - x;
    
25.       x = temp;
    
26.       /* Now x has the old value of y, which is odd.
    
27.          y is even, because it is the difference of
    
28.          two odd
    
29.          numbers; therefore it will be right-shifted
    
30.          at least once on the next iteration. */
    
31.     }
    
32.   return (x << common_power_of_two);
    
33. }

复制代码

soloforce

欧几里德算法自然语言（汉语）描述：

1. 
   
2. １ ） 　 若 ａ ＝ ０ ，则 ｄ ← ｂ ，跳到第 ９ 步；
   
3. ２ ） 　 若 ｂ ＝ ０ ，则 ｄ ← ａ ，跳到第 ９ 步；
   
4. ３ ） 　 若 ａ ＜ ｂ ，则交换 ａ 和 ｂ 　；
   
5. ４）　   ｄ ← （ａ MOD ｂ）；   
   
6. ５ ） 　 ａ ← ｂ 　；
   
7. ６ ） 　 ｂ ← ｄ 　；
   
8. ７ ） 　 若 ｄ ＜ ０ ，跳转到第 ４ 步；
   
9. ８ ） 　 ｄ ← ｂ 　；
   
10. ９ ） 　结束。

复制代码

二进制欧几里德算法自然语言（汉语）描述：

1. 
   
2. １ ） 　 　 若 ａ ＝ ０ ，则 ｄ ＝ ｂ 。转到 １ ２；
   
3. ２ ） 　 　 若 ｂ ＝ ０ ，则 ｄ ＝ ａ 。转到 １ ２；
   
4. ３ ） 　 　 令正整数 ｐ ＝ ０；
   
5. ４ ） 　 　 若 ａ 和 ｂ 都是偶数，则 ａ ← (a/2)，ｂ ← (b/2)，ｐ ← ｐ ＋ １；
   
6. ５ ） 　 　 若 ａ 和 ｂ 仍都是偶数，转到 ４ ；
   
7. ６ ） 　 　 若 ａ 是偶数，ｂ 是奇数，则 ａ ← (a/2)；
   
8. ７ ） 　 　 若 ａ 仍是偶数，转到 ６ ；
   
9. ８ ） 　 　 若 ａ 是奇数，ｂ 是偶数，则 ｂ ← (b/2)　；
   
10. ９ ） 　 　 若 ｂ 仍是偶数，转到 ８ ；
    
11. １ ０ ） 　 若 ａ 和 ｂ 都不是偶数，则 ａ ← ｂ ，ｂ ← | ａ － ｂ |；
    
12. １ １ ） 　 若 ｂ ≠ ０ ，转到 ８；
    
13. １ ２ ） 　 ｄ ← ａx (２的P次方) ；
    
14. １ ３ ） 　 结束。

复制代码

证明略

gotop2004

不佩服不行的

d00m3d

Lolita 要当数学老师吗？

wildoxlee

int gcd(int a, int b)
{
if(b=0) return(a);
gcd(b, a%b);
}

nico65

本人水平差看不懂了，6 楼写的看得还有点懂，是不是"辗转相除法"的意思啊？

Iambitious

对我很有帮助阿

brotherhao

是的,这个就是辗转相除法.

初等数论的教材中都会有介绍的.

当然,楼主介绍的也很深刻.

huzhe

辗转相除法，在西方叫欧几里得除法。本人更喜欢wildoxlee兄的 递归 算法，精炼！