- 首先,按照数学上的辗转相除法计算最大公约数固然可以,但是如果两个数都是非常大的数,那么除法的代价很昂贵;另外,如果将除法转换为减法,即f(x,y)=f(y,x-y)可以很大程度上减少除法的开销,但是可能导致迭代此处太多,算法代价仍然昂贵,现在结合这两者的思想,给出一个最佳的算法,特别适合Big Int的计算,算法思想如下:
- 如果 y=k*y1;x=k*x1;
- 那么有f(x,y) = k*f(x1,y1);
- 另外,如果
- x=p*x1;且p为素数,且y%p != 0;那么f(x,y)=f(x1,y);
- 由于在计算机中移位操作很方便,代价很小,效率也很高,所以我们考虑p=2的情况下进行求取,代码如下:
- bool isEven(int x)
- {
- if ( x%2 == 0 )
- {
- return true;
- }
- else
- {
- return false;
- }
- }
- int MaxGcd(int x,int y)
- {
- if ( x<y )
- {
- return MaxGcd(y,x);
- }
- if (y==0)
- {
- return x;
- }
- else
- {
- if (isEven(x))
- {
- if ( isEven(y) )
- {
- return (MaxGcd(x>>1,y>>1)<<1);
- }
- else
- {
- return MaxGcd(x>>1,y);
- }
- }
- else
- {
- if ( isEven(y) )
- {
- return MaxGcd(x,y>>1);
- }
- else
- {
- return MaxGcd(y,x-y);
- }
- }
- }
- }
- //该片段来自于http://www.codesnippet.cn/detail/1908201410240.html
来源: http://www.codesnippet.cn/detail/1908201410240.html