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;

}

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

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 )

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 ?

No, because steps1 is already a pointer to int.

steps1 is of type int*
&steps1 is of type int**

what type the gdcrecurs expects?

i think it shoud expect an int since the final outcome should be a greatest common divisor

sorry my mistake

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 ?

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.

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

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;

Right. steps1 points to an int. Adding another & would add another "points to" to your description, which isn't what you want.

yep. that's what you need since you're passing the address of the var to the function.