Thread: euclids algorithm

  1. #1
    Registered User
    Join Date
    Mar 2009
    Posts
    19

    euclids algorithm

    Hi everyone

    I have to write a c program that calculates the greatest common divisor of two positive numbers , using the euclides algorithm . I have to implement two functions , one that works recursively to find the gdc and one that works with WHILE .

    The main has to call both functions and print the gcd found by each one PLUS how many steps each function needed to complete the task . By steps , i mean how many times the recursive function was called in the first function
    and how many times the WHILE looped in the second function

    Here is my solution . I would really appreciate any corrections or tips

    Thanks in advance

    Code:
    #include <stdlib.h>
                         
    int gcdrecurs(int m,int n,int *steps1 ) 
    {
      int temp , r ;
    
      *steps1 = *steps1 + 1;
      r = m % n;
      if (r == 0) 
      {
        return n;
      } 
      else 
      {
        return gdcrecurs(n , r , steps1 );
      }
    
    }
                         
    
    int gdcwhile(int m , int n , int *steps2)
    {
          int temp ;
          *steps2 = 0 ; 
          while (n !=0 )
          {
               *steps2 = *steps2 + 1 ;
               temp = m ;
               m = n ;
               n = temp % n ;
          }
           return  m;
    }
    
    main() 
    {
      int a1 , a2  , temp ,  gdc1 , gdc2 , steps1 , steps2 ; 
      printf("type two positive numbers\n");
      scanf("%d",&a1);
      scanf("%d",&a2)
      if (a1 < a2) 
      {
        temp = a1;
        a1 = a2;
        a2 = temp ;
      } 
      steps1 = 0;
      gdc1 = gcdrecurs(a1,a2,steps1);
      printf("the gdc is %d and  %d steps were needed using recursion" ,gdc1,steps1);
      gdc2 = gdcwhile(a1,a2,steps2);
      printf("the gdc is %d and %d steps were needed using while loop",gdc,steps2);
      return 0;
    
    }

  2. #2
    Make Fortran great again
    Join Date
    Sep 2009
    Posts
    1,413
    main() should be an int type, also, you don't need brackets for one line statements in if-then-else structures, i.e:
    Code:
    if ... then
    something
    else
    something else

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Epy
    you don't need brackets for one line statements in if-then-else structures
    But if you want to continue using those braces even then, go ahead. You're in good company either way. (Though I think that the crowd that always uses them makes for better company )
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    Registered User
    Join Date
    Mar 2009
    Posts
    19
    Thanks for replying

    I have one more question for the first function

    Code:
    int gcdrecurs(int m,int n,int *steps1 ) 
    {
      int temp , r ;
    
      *steps1 = *steps1 + 1;
      r = m % n;
      if (r == 0) 
      {
        return n;
      } 
      else 
      {
        return gdcrecurs(n , r , steps1 );
      }
    
    }
    shouldn't the return statement be

    return gdcrecurs(n,r,&steps1) - mind the & -


    since steps1 is passed by reference ???? But it wont compile like that , it will compile without the & before the steps1 . Why is that ?

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    No, because steps1 is already a pointer to int.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    steps1 is of type int*
    &steps1 is of type int**

    what type the gdcrecurs expects?
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  7. #7
    Registered User
    Join Date
    Mar 2009
    Posts
    19
    i think it shoud expect an int since the final outcome should be a greatest common divisor

  8. #8
    Registered User
    Join Date
    Mar 2009
    Posts
    19
    sorry my mistake

  9. #9
    Registered User
    Join Date
    Mar 2009
    Posts
    19
    you meant what it expects in steps1 right ?


    Well steps1 is supposed to count how many times the function is called ( by it self + 1 ) . So it should be an int passed by reference in order not to lose the value between recursive calls , right ?

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by johngav
    So it should be an int passed by reference in order not to lose the value between recursive calls , right ?
    Yes, but "it" refers to the int that steps1 points to.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Registered User
    Join Date
    Mar 2009
    Posts
    19
    i'n not sure i get what you mean .

    steps1 points to an int that is initialised to zero

    steps1=0 in function main

    i

  12. #12
    Registered User
    Join Date
    Mar 2009
    Posts
    19
    i think i also have to correct my main() . Am i right ( mind the bold )

    Code:
    .....
    steps1 = 0;
      gdc1 = gcdrecurs(a1,a2,&steps1);
      printf("the gdc is %d and  %d steps were needed using recursion" ,gdc1,steps1);
      gdc2 = gdcwhile(a1,a2,&steps2);
      printf("the gdc is %d and %d steps were needed using while loop",gdc,steps2);
      return 0;

  13. #13
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Right. steps1 points to an int. Adding another & would add another "points to" to your description, which isn't what you want.

  14. #14
    Registered User
    Join Date
    Jan 2008
    Posts
    28
    yep. that's what you need since you're passing the address of the var to the function.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 3
    Last Post: 11-13-2005, 02:53 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Binary Euclid's Algorithm
    By exluddite in forum C++ Programming
    Replies: 7
    Last Post: 09-26-2004, 08:08 PM
  4. Euclid's algorithm
    By Unregistered in forum C Programming
    Replies: 7
    Last Post: 10-03-2001, 10:59 PM