Euclid's algorithm

[Unregistered]

ok i have to write a program that reduces fractions by using the euclidean algorithm....

i need help figuring out how to implement this algorithm into "C" code this is what my program looks like so far.......
/*project2*/
#include<stdio.h>
int main ()
{
int x,
y,
a,
b,
c,
result = 1;

printf("Enter a fraction\n");
scanf("%d/%d", &x, &y);
printf( "You entered %d/%d\n", x, y );

a = x / y;
b = x % y;
c = y;


if(x < y)
printf("That fraction reduces to %d/%d\n", &x, &y);
if(x = y)
printf("That fraction reduces to 1\n");
if(x > y)
{
while( result != 0)
result = b;
x = y;
y = result;




return 0;

}







Please.....any help(comments, hints) would be very much appreciated

[Unregistered]

i tried this......What am i doing wrong?????

if(x > y)
{
while( result != 0)
{
result = x % y;
x = y;
y = result;

}
gcf = x;
printf("that fraction reduces to %d/%d\n",&gcf, &a);
}

[zen]

Almost, but your loop wont prevent result from becoming zero, it'll only stop when it becomes zero. Something like this should work -

#include <stdio.h>


int main()

 {
          int a =12, b=20;
	  int gcd;
	  int result,x,y;
	  
   	  x=a;
	  y=b;

	  while(result!=0)
	  {
		  gcd=result;
		  result =x%y;
		  x=y;
		  y=result;
	  }

	  printf("%d/%d = %d/%d",a,b,a/gcd,b/gcd);


	  return 0;

}

[zen]

...that wouldn't work if there was no initial remainder. This is better -

#include <stdio.h>

int main()

 {
      int a =12,b=20;
	  int gcd;
	  int result,x,y;
	  
   	  x=a;
	  y=b;

	  if(a%b)
	  {
		while(result!=0)
		{
		  gcd=result;
		  result =x%y;
		  x=y;
		  y=result;
		}
	  }
	  else
		  gcd=b;

	  printf("%d/%d = %d/%d",a,b,a/gcd,b/gcd);


	  return 0;

}

[Unregistered]

Arent you testing the value of result without initializing it in the while loop ?

[kwigibo]

I cant help to notice that this question on this algorithm has been posted many times before. Perhaps the Cboard FAQ needs updating a bit. Am I the only one who finds all this repetition annoying?

[zen]

Arent you testing the value of result without initializing it in the while loop ?

Yes, to be safe the line

y=b;

should be

result=y=b;

Although as long as result is initialised to any non-zero value the code should work.

There also should be some code that checks for divide by zero.

[pinko_liberal]

there is another interesting algorithm to find out the gcd of two positive numbers
if u,v are even
gcd(u,v)=2gcd(u/2,v/2)
if u is even and v is odd
gcd(u,v)=gcd(u/2,v)
if both are odd
gcd(u,v) is =gcd(u-v,v)
note u-v is even and |u-v|<=max(u,v) (if u>=,v>=0)