关于binary gcd的笔记

代码实现

之前没有听说过这个东西，google了一番之后根据自己的理解尝试实现了一下，代码如下：

int binary_gcd(int a,int b){
    if(a==b) return a;
    if((~a&1)&&(b&1)) return(binary_gcd(a>>1,b));
    if((~b&1)&&(a&1)) return(binary_gcd(a,b>>1));
    if((~a&1)&&(~b&1)) return(binary_gcd(a>>1,b>>1)<<1);
    if(a>b) return binary_gcd((a-b)>>1,b);
    else return binary_gcd((b-a)>>1,a);
}

正确性分析

临界分析

算法的临界有两个，一个是a=b,一个是a,b中有一个为0
首先是a=b,emmm...既然a=b，那么a，b的最大公约数当然就是他们本身。

与wiki示例代码差异的分析
再说a,b中有一个为0，这是我在写完代码比对wiki示例时发现的，我个人认为这种情况不会出现。（还找OJ交了评测也是Accepted)
首先，它的上一级调用的情形不可能为binary_gcd((a-b)>>1,b)这种，因为在这种情况下已经出现a=b这一临界条件，即算法会先于出现a,b有一个参数为0时结束。
再说binary_gcd(a>>1,b)这种情形，这种情况的前提是a为偶数，b为奇数。而出现a>>1为零的情况是a为1，与a为偶数矛盾。
还剩下一种情况是binary_gcd(a>>1,b>>1)这个时候a,b都为偶数，也不可能产生a>>1=0的结果。

最后我google what is gcd of 0 and other num找到了答案。
What is the greatest common divisor of 0 and (5 or any non-zero no.)?
因为除零操作是非法的，0/n则是允许的，而gcd(a,b)=gcd(b,b%a),即gcd(0,a)=a;

综上所述，特判a,b为0的输入是为了防止输入中含0参数时导致算法陷入死循环。这应该算是一个小细节了吧，没有这方面的知识基础可能听取WA声一片都不知道为什么T.T

正确性分析

依旧是分情况讨论
算法根据输入的奇偶性进行分了四种情况，下面依次讨论
最简单的一个是两个数都为偶数，这种情况下找出一个公因数2，算法继续。
然后是一奇一偶的情况，假设a为偶数，b为奇数，则有gcd(a,b)=gcd(a/2,b)
证明如下：
假设gcd(a,b)%2=0,即b=2k,与b为奇数矛盾。
故2不是gcd(a,b)的因数，所以gcd(a,b)=gcd(a/2,b)
最后是两者都为奇数的情况。
算法首先判断a,b的大小关系，这可以避免递归调用中出现负数的情况。
然后因为a,b都为奇数，所以a-b为偶数，即((a-b)>>1)%2=0
接下来证明gcd(a,b)=gcd((a-b)>>1,b)

$$x=gcd(a,b)\\ a=k_1x(k_1\subset\mathbb{N^+})\\ b=k_2x(k_2\subset\mathbb{N^+})\\ gcd(k1,k2)=1\\ \frac{a-b}{2}=\frac{k_1-k_2}{2}x\\ 又∵(a-b)\bmod2= 0\\ ∴\frac{k_1-k_2}{2}\subset\mathbb{N^+}\\ 至此，可以证明x为（a-b)>>1和b的公因数，现证明x即为最大公因数。\\ 即证gcd(\frac{k1-k2}{2},k2)=1\\ 假设x为偶数，则与a,b为奇数矛盾，故x为奇数\\ 因为b为奇数,x为奇数，所以k2为奇数\\ 又因为\frac{k1-k2}{2}为偶数，所以k2与\frac{k1-k2}{2}没有偶公因数。① \\ 若k2有奇因数，则该因数为奇数\\ 若\frac{k1-k2}{2}有奇因数，则该因数为偶数\\ 综上所述，k2与\frac{k1-k2}{2}也没有奇公因数。②\\ 由①②可知，gcd（\frac{k1-k2}{2},k2）=1\\ 最后，即证明了gcd(a,b)=gcd((a-b)>>1,b)\\$$

由此，（可能）完成了binary_gcd算法正确性的证明

性能分析

直观感受上，虽然传统的gcd算法递归层数往往不会有binary_gcd那么多，但binary_gcd几乎所有的运算都是位运算，因此性能上会更好。