证明最大公约数Stein算法(高精度算法)

E:even 奇数  O:odd 偶数

若(a,b)为(e,e)，则gcd(a,b)=2*gcd(a/2,b/2)

若(a,b)为(e,o)，则gcd(a,b)=gcd(a/2,b)

若(a,b)为(o,o)[a>=b]，则gcd(a,b)=gcd(a,b-a)

证明：

I.若a=c*d b=c*e 则gcd(a,b)=c*gcd(d,e)

这里c=2。

证明：

对于第一个质数，c拥有该质数的个数为ci,d拥有该质数的个数为di,e拥有该质数的个数为ei，而a拥有该质数的个数为ci+di,b拥有该质数的个数为ci+ei。对于任何质数，都有min(ci+di，ci+ei)=ci+min(di,ei),所以gcd(a,b)=c*gcd(d,e)。

如a=56,b=16,c=2,对于质数2， ai=2,bi=4,ci=1,di=1,ei=3,min(2，4)=1+min(1,3)。

II.若a=c*d，但gcd(c,b)=1，则gcd(a,b)=gcd(d,b)

这里c=2。

证明：

对于一个质数，c拥有该质数的个数为ci, d拥有该质数的个数为di，b拥有该质数的个数为bi，而a拥有该质数的个数为ci+di，其中min(ci,bi)=0。对于任何质数，都有min(ci+di,bi)= min(di,bi)（

当ci=0,min(di,bi)=min(di,bi),成立；

当bi=0,min(ci+di,0)=min(di,0),成立）,

所以gcd(a,b)=gcd(d,b)。

III. gcd(a,b)=gcd(b,a-bx)

这里x=1

证明：

设gcd(a,b)=d,gcd(b,a-bx)=e,则

∵d|a,d|b

∴d|a-bx

∴d|gcd(b,a-bx)，即d|e

∵e|b,e|a-bx

∴e|bx+(a-bx)，即e|a

∴e|gcd(a,b)，即e|d

∴d=e。证毕。

（来自Jollwish方法）

各种情况分析：

1.(e,e):(x,y)->(x/2,y/2)->…->[(e,o)/(o,e)/(o,o)]

只在开头出现

2.(o,e):(x,y)->(x,y/2)->…->[(o,o)]

偶数不断除以2知道变为奇数

3.(o,o):(x,y)->(x,y-x) [(o,e)]

(o,o)操作一遍变为(o,e)，所以出现次数出现次数较少

所以只在开头判断是否为(e,e)；每次先判断是否为(o,e)再判断是否为(o,o)

设定(a,b)中a必须为奇数。则一开始若为(e,o)，通过两数交换变为(o,e)。当(o,o)时，若a<=b，则(a,b)->(a,b-a);若a>b，则(a,b)->(b,a-b)。

Another Way：

(o,e)中的偶数不停除以2，直到变为奇数，变为(o,o)；而(o,o)通过一次操作变为(o,e)，重复操作，直到(o,e)中的偶数为0。

这个方法速度更快一点点。

高精度的实现：

高精度加法，高精度减法，高精度除法(高除低，除以2的特殊情况：对于每一位，若为奇数则下一位加1，若为偶数无操作；然后该位除以2)