一个求最大公约数的二进制算法

看到一个求最大公约数的二进制算法，但是没看懂， 请高手指教：

inline int GCD(int x,int y)   
{
        int i,j;
        if(x==0) return y;
        if(y==0) return x;
        for(i=0;0==(x&1);++i)x>>=1;
        for(j=0;0==(y&1);++j)y>>=1;
        if(j<i) i=j;
        while(1){
                if(x<y)x^=y,y^=x,x^=y;
                if(0==(x-=y)) return y<<i;
                while(0==(x&1))x>>=1;
        }
}

45 个解决方案

#1

辗转相除法的变种咯- -!

#2

x和y的公约数 == x和y-x的公约数
然后重复利用x是奇数,每次把y-x中的2的因子给去掉

当x>y的时候交换x和y,继续循环直到x=y为止

#3

辗转相减移位法

#4

把公因子2的幂都给提出来
然后再辗转相减

#5

主要用于大数求Gcd，效率可以高很多。

#6

牛啊！！！

#7

引用 5 楼 litaoye 的回复:

主要用于大数求Gcd，效率可以高很多。

顶

#8

这个复杂度还是O(n^2)。反例依然还是连续两项fibonacci数。
真要做O(n*log(n)^2)的话有，但是写起来就恶心了。GMP里用的似乎就是低二次的。

#9

引用 4 楼 michael122 的回复:

把公因子2的幂都给提出来
然后再辗转相减

严重支持4楼！

#10

引用 8 楼 fancymouse 的回复:

这个复杂度还是O(n^2)。反例依然还是连续两项fibonacci数。
真要做O(n*log(n)^2)的话有，但是写起来就恶心了。GMP里用的似乎就是低二次的。

请指点低二次的思路

#11

引用 10 楼 sbwwkmyd 的回复:

引用 8 楼 fancymouse 的回复:
这个复杂度还是O(n^2)。反例依然还是连续两项fibonacci数。
真要做O(n*log(n)^2)的话有，但是写起来就恶心了。GMP里用的似乎就是低二次的。

请指点低二次的思路

自己看论文：On Schönhage’s algorithm and subquadratic integer gcd computation

基本思路就是把gcd问题转化为一个2*2的矩阵问题。然后把高精数分成高低两个等长部分，然后高低分别递归做那个2*2矩阵，然后想办法合并。当然，实现细节非常抓狂。

#12

FancyMouse牛啊

#13

灰常牛

#14

看看，学习一下

#15

inline int GCD(int x,int y)   
{
        int i,j;
        if(x==0) return y;
        if(y==0) return x;
        for(i=0;0==(x&1);++i)x>>=1;   // 去掉所有的2
        for(j=0;0==(y&1);++j)y>>=1;   // 去掉所有的2
        if(j<i) i=j;
        while(1){
                if(x<y)x^=y,y^=x,x^=y;   // 若 x < y 交换 x, y
                if(0==(x-=y)) return y<<i;  // 若x == y， gcd == x == y (就是在辗转减，while(1)控制)
                while(0==(x&1))x>>=1; // 去掉所有的2
        }
}

#16

能给一个你所说方法的资料吗，算法名称或者网上资源都行，我仔细读读。 谢谢。

引用 2 楼 arucart 的回复:

x和y的公约数 == x和y-x的公约数
然后重复利用x是奇数,每次把y-x中的2的因子给去掉

当x>y的时候交换x和y,继续循环直到x=y为止

#17

引用 11 楼 fancymouse 的回复:

自己看论文：On Schönhage’s algorithm and subquadratic integer gcd computation

基本思路就是把gcd问题转化为一个2*2的矩阵问题。然后把高精数分成高低两个等长部分，然后高低分别递归做那个2*2矩阵，然后想办法合并。当然，实现细节非常抓狂。

谢谢指点

#18

该回复于2010-07-29 18:17:14被版主删除

#19

hao tie shou cang

#20

该回复于2010-08-03 17:11:07被版主删除

#21

《离散数学及其应用》里面的东西

#22

不错 不错..个人觉得算法比较新颖

#23

就是辗转相除啊

#24

弱弱的问一句：

在计算机性能如此高的今天，没有什么使用价值吧？

#25

引用 24 楼 chao2chen 的回复:

弱弱的问一句：

在计算机性能如此高的今天，没有什么使用价值吧？

人都是贪的。对于性能的追求总是没有止境的。

顺便n^2和nlog(n)^2那是很大的差别。1亿位规模的数据前者就是完全不能算。后者至少拿个最新的处理器几天可以搞定

#26

厉害。收藏此帖。

#27

引用 24 楼 chao2chen 的回复:

弱弱的问一句：

在计算机性能如此高的今天，没有什么使用价值吧？

呵呵

#28

[code]
int GCD(int x,int y)
{
  y==0?x:GCD(y,x%y);
}

#29

该回复于2010-08-02 14:34:43被版主删除

#30

//总觉得这个代码有点像孔乙己的茴香豆的“茴”有几种写法一样。不过古怪的代码还是有研究的必要的
//中心思想用的是求差判定.
inline int GCD(int x,int y)   
{
        int i,j;
        if(x==0) return y;
        if(y==0) return x;
        for(i=0;0==(x&1);++i)x>>=1;//是否为偶数，是，除以2，同时对i赋值，去掉所有的因子2
        for(j=0;0==(y&1);++j)y>>=1;//是否为偶数，是，除以2，同时对j赋值，去掉所有的因子2
        if(j<i) i=j;
        while(1){
                /*按位异或，交换两值。但是非常不提倡这么写。具体参见《Java解惑》の谜题7.*/
                if(x<y)x^=y,y^=x,x^=y;
                //两个奇数相减直到找到相等的值为止，X此时肯定为偶数，
                if(0==(x-=y)) return y<<i;             
                while(0==(x&1))x>>=1;
        }
}

#31

/* 
 * File:   main.c
 * Author: root
 *
 * Created on 2010年7月31日, 下午2:20
 */

#include <stdio.h>
#include <stdlib.h>

/*
 * 
 */
int main(int argc, char** argv) {
    int x,y;
    printf("请输入两个正整数\n");
    scanf("%d%d",&x,&y);
    printf("X=%d Y=%d\n",x,y);
     int i,j;
        if(x==0) return y;
        if(y==0) return x;
        for(i=0;0==(x&1);++i)x>>=1;
        for(j=0;0==(y&1);++j)y>>=1;
        if(j<i) i=j;
        while(1){           
                if(x<y)x^=y,y^=x,x^=y;
                if(0==(x-=y))
                {
                    int k=y<<i;
                    printf("最大公约数是%d\n",k);
                    break;
                }
                while(0==(x&1))x>>=1;
                }


    return (EXIT_SUCCESS);
}

#32

/* 
 * File:   main.c
 * Author: root
 *
 * Created on 2010年7月31日, 下午1:59
 */

#include <stdio.h>
#include <stdlib.h>

/*
 * 
 */
int main(int argc, char** argv) {
    int x,y;
    printf("请输入两个正整数：\n");
    scanf("%d%d",&x,&y);
    printf("X=%d Y=%d\n",x,y);

    while(1)
    {
        if(x%y==0)
        {
            printf("最大公约数是%d\n",y);
            break;
        }
        else
        {
            int k=x%y;
            if(y%k==0)
            {
                printf("最大公约数是%d\n",k);
                break;
            }
            else
            {
                x=k;
                y=y%k;
            }

        }
    }
    return (EXIT_SUCCESS);
}

#33

求最大公约数的几种方法在《编程之美》里好像有提过。

#34

//总觉得这个代码有点像孔乙己的茴香豆的“茴”有几种写法一样。不过古怪的代码还是有研究的必要的
//中心思想用的是求差判定.
inline int GCD(int x,int y)   
{
        int i,j;
        if(x==0) return y;
        if(y==0) return x;
        for(i=0;0==(x&1);++i)x>>=1;//是否为偶数，是，除以2，同时对i赋值，去掉所有的因子2
        for(j=0;0==(y&1);++j)y>>=1;//是否为偶数，是，除以2，同时对j赋值，去掉所有的因子2
        if(j<i) i=j;
        while(1){
                /*按位异或，交换两值。但是非常不提倡这么写。具体参见《Java解惑》の谜题7.*/
                if(x<y)x^=y,y^=x,x^=y;
                //两个奇数相减直到找到相等的值为止，X此时肯定为偶数，
                if(0==(x-=y)) return y<<i;             
                while(0==(x&1))x>>=1;
        }
}
顶起~

#35

引用 30 楼 yukiooy 的回复:

C/C++ code

//总觉得这个代码有点像孔乙己的茴香豆的“茴”有几种写法一样。不过古怪的代码还是有研究的必要的
//中心思想用的是求差判定.
inline int GCD(int x,int y)   
{
        int i,j;
        if(x==0) return y;
        if(y==0) return x;
        for(……

顶起~

#36

楼主给你看一段类似的代码

/****************************************************
模乘(俄罗斯农夫算法:)
返回a*b%n的结果
原理 A*B=(A/2)*(B*2)=(A/4)*(B*4).........
把B二进制展开:A*B=sum(a_i*B*2^i)( 0<i<Len(A) )
例如:  7*8={1*8*2^0 + 1*8*2^1 + 1*8*2^2 }
同理:A*B %n =sum(a_i*B*2^i) %n
            ={ sum(a_i*b_i %n) } %n
*****************************************************/
unsigned __int64 mod_product(unsigned __int64 a,unsigned __int64 b,unsigned __int64 n)
{      
        unsigned __int64 r;
        r=0;
        a%=n;  //初始a=a%n
        b%=n;  //初始b=b%n
        
           
  while(b)//对b进行二进制展开
  {
                   if(b&1)//b的二进制展开中为1的为才计算b_i * A mod n 并累计到r中
       {
                        if(r+a<r)r=r-n+a; //发生加法溢出
                        else r+=a;
                        if(r>=n)r-=n;
       }        
    //以下是对a乘法2
                if((a<<1)<a)
    {
     a=a-n+a;//发生溢出,则mod n
                }
    else
    {
     a<<=1;
                }

    if(a>=n)a-=n; //mon n
                
    b>>=1;        //对b除2
  }

        return r;             //r=a*b %n
}

#37

                //两个奇数相减直到找到相等的值为止，X此时肯定为偶数，
                if(0==(x-=y)) return y<<i;  

是这里没看懂么？
两个奇数。有公约数M（M肯定为奇数）；而最后return y是等于M的，在把先前约分约掉的偶数给乘上，就成了最大公约数了。

#38

看不懂算法，觉得还是“欧几里得”算法计算起来比较简单一个while里就3步。

#39

欧几里得”算法:

inline int GCD(int m, int n) 
{
   int r;

   while(1)
   {
      r = m % n;
      
      if(r == 0) return n;
      
      m = n;
      n = r;
   }
}

#40

上面的算法还要排除一下除以0的错误。

#41

楼主的算法是Stein算法

Stein算法如下：

如果A=0，B是最大公约数，算法结束 
如果B=0，A是最大公约数，算法结束 
设置A1 = A、B1=B和C1 = 1 
如果An和Bn都是偶数，则An+1 =An /2，Bn+1 =Bn /2，Cn+1 =Cn *2(注意，乘2只要把整数左移一位即可，除2只要把整数右移一位即可) 
如果An是偶数，Bn不是偶数，则An+1 =An /2，Bn+1 =Bn ，Cn+1 =Cn (很显然啦，2不是奇数的约数) 
如果Bn是偶数，An不是偶数，则Bn+1 =Bn /2，An+1 =An ，Cn+1 =Cn (很显然啦，2不是奇数的约数) 
如果An和Bn都不是偶数，则An+1 =|An -Bn|，Bn+1 =min(An,Bn)，Cn+1 =Cn 
n++，转4 

#42

优化一下
inline int GCD(int m, int n) 
{
   if(m == 0) return n;

   if(n == 0) return m;
   
   int r;

   while(r = m % n)
   { 
      m = n;
      n = r;
   }

   return n;
}

#43

计算大数的情况下Stein算法效率比较高。

#44

引用 30 楼 yukiooy 的回复:

while(1){
                /*按位异或，交换两值。但是非常不提倡这么写。具体参见《Java解惑》の谜题7.*/
                if(x<y)x^=y,y^=x,x^=y;

‘,’操作符在呢

#45

-module(gcd).
-export([gcd/2]).
gcd(X,Y)->
	case (X rem Y =:=0) of 
	true->Y;
	false->gcd(Y,X rem Y)
	end.