Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Is my code for gcd function valid?

  1. May 28, 2007 #1
    i have to write the function gcd for c programme.
    here's my code:
    Code (Text):

    int gcd(int m, int n)
    {
     int s,r,x,y;
     
     if (m>=n)
      {
        r=m-(m/n)*n;
        for(x=m,y=n;r!=0;x=y,y=r)
         r=x-(x/y)*y;
       }
      if(n>m)
      {
        r=n-(n/m)*n;
      for(x=n,y=m;r!=0;x=y,y=r)
          r=x-(x/y)*y;
     }
    return(r);
    }
     
    so is this correct? im using the fact that the divison of two integers returns an integer solution, i.e without the remainder, and ofcourse euclid's algorithm.
    p.s
    this is a part of a programme that i need to do in order to check for pythaogrean triplets, so it's not supposed to run alone.

    thanks in advance.
     
  2. jcsd
  3. May 28, 2007 #2
    Code (Text):
    int gcd(int m, int n)
    {
     int s,r,x,y;
     
     if (m>=n)
      {
        r=m-(m/n)*n;
        for(x=m,y=n;r!=0;x=y,y=r)
         {
          s=r;
         r=x-(x/y)*y;
          }
       }
      if(n>m)
      {
        r=n-(n/m)*n;
      for(x=n,y=m;r!=0;x=y,y=r)
          {
          s=r;
          r=x-(x/y)*y;
          }
     }
    return(s);
    }
     
    i think that now it works ok, what do you think?
     
  4. May 29, 2007 #3

    ranger

    User Avatar
    Gold Member

    Yea, its working. But you need to add a case that covers when there is no remainder. Like when I do 10 and 5, the program returns 0 as the gcd.

    Heres a stand alone program that I wrote, utilizing the modulus function.
    Code (Text):

    / * Euclid's method of finding the greatest common divisor of two integers*/
    #include <stdio.h>

    int gcd(int num1, int num2);
    int swap(int *pa, int *pb);

    int main()
    {
        int m,n,gcd_num;
       
        printf("Enter two integers\n");
        scanf("%d %d", &m, &n);
        if(m <= 0 || n <= 0) {
            printf("Zero input detected\n");
            exit(1);
        }
        if(m <= n) swap(&m, &n);
        gcd_num = gcd(m,n);
        printf("\nThe greatest common divisor of %d and %d is %d\n",m,n,gcd_num);
        return 0;
    }

    int swap(int *pa, int *pb)
    {
        int temp = *pa;
        *pa = *pb;
        *pb = temp;
        return;
    }

    int gcd(int m, int n)
    {
        int r;
       
        [b]if(m%n == 0)
        r = n;[/b]
       
        while((m%n!=0))
        {
        r = m%n;
        printf("Trying %d\n",r);
        m=n;
        n=r;
        }
        return r;
    }
     
    The bold lines takes care of the case when there is no remainder.
     
    Last edited: May 29, 2007
  5. May 30, 2007 #4
    now i need to write a programme that will get as input, 'n' and 'max' it should look on triples such that 1<=a<b<c<=max and check wether they satisfy a^n+b^n=c^n, if so the triple will be printed, and at the end there will be printed the number of triples.
    i need no duplicates of triples such as: 3,4,5 or 4,3,5 which are the same and that gcd(a,b)=1.
    now he i wrote the programme, but im finding difficult where to put the condition that a<b<c, here's what i did so far:
    Code (Text):

    #include <stdio.h>
    int gcd(int m,int n)
    {
      int r,s,x,y;
      if(m>=n){
        r=m-(m/n)*n;
        if(r==0)
          s=n;
      for(x=m,y=n;r!=0;x=y,y=r)
         {
           s=r;
           r=x-(x/y)*y;      
         }
       
      }
      if(n>m){
        r=n-(n/m)*m;
        if(r==0)
          s=m;
        for(x=m,y=n;r!=0;x=y,y=r)
         {
           s=r;
           r=x-(x/y)*y;      
         }
      }
    return(s);
    }
    int pow(int a, int t)
    {
      int q,p;
        for(p=1,q=1;q<=t;q++)
          p=a*p;

    return(p);
    }
    main()
    {
      int d,f=0,n,max,a,b,c;
     printf("insert the degree you wish to check for n-th pythogrean triplets\n");
     scanf("%d", &n);
     printf("insert the maximal number you want to check for\n");
     scanf("%d", &max);
     if(max>2){
       
       for(a=1;a<=max;a++)
         {
           for(b=2;b<=max;b++)
             {
       for(c=3;a<b,b<c,c<=max;c++)
         {
           if((pow(a,n)+pow(b,n)==pow(c,n))&& gcd(a,b)==1){
             f++;
             printf("the triplet is: %d, %d, %d \n", a,b,c);
           }
           if(pow(a,n)+pow(b,n)==pow(c,n)&& (gcd(a,b))!=1){
             f++;
              printf("the triplet is: %f, %f, %f \n", a/(gcd(a,b)),b/(gcd(a,b)),c/(gcd(a,b)));
           }
         }
             }
         }
     }

       
         

           if(max<=2)
            printf("there isn't such triplet \n");
     printf("the number of triplets in the specified domain is: %d \n", f);
     }
     
    any hints where should i put this condition, i put it in the third loop, but it doesnt seem to work.
    your help is appreciated.
     
  6. Jun 1, 2007 #5
    here's an abbreviated code, without specifting the gcd and pow functions:
    Code (Text):


      int d,f=0,n,max,a,b,c;
     printf("insert the degree you wish to check for n-th pythogrean triplets\n");
     scanf("%d", &n);
     printf("insert the maximal number you want to check for\n");
     scanf("%d", &max);
     if(max>2){
       
       for(a=1;a<=max;a++)
         {
           for(b=2;b<=max;b++)
             {
       for(c=3;a<b,b<c,c<=max;c++)
         {
           if((pow(a,n)+pow(b,n)==pow(c,n))&& gcd(a,b)==1){
             f++;
             printf("the triplet is: %d, %d, %d \n", a,b,c);
           }
           if(pow(a,n)+pow(b,n)==pow(c,n)&& (gcd(a,b))!=1){
             f++;
              printf("the triplet is: %f, %f, %f \n", a/(gcd(a,b)),b/(gcd(a,b)),c/(gcd(a,b)));
           }
         }
             }
         }
     }

       
         

           if(max<=2)
            printf("there isn't such triplet \n");
     printf("the number of triplets in the specified domain is: %d \n", f);
     }
     
    i hope someone can give me some hint.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Is my code for gcd function valid?
  1. Critique my C++ code (Replies: 11)

Loading...