# Euclidean algorithm can't handle 2/3?

Started by
stettybet0
, Nov 22 2008 01:22 PM

###
#1
Posted 22 November 2008 - 01:22 PM

###
#2
Posted 18 January 2009 - 04:08 PM

Hi,

This topic is so old that you may well have found your answer elsewhere by now, but just in case you haven't...

Euclid's Algorithm returns the greatest common divisor of two integers. You want to reduce a fraction to "lowest terms" and that means you need to find the biggest thing that will divide both the numerator and denominator, (the greatest common divisor), and then divide each by it. If your gcd function is working properly, then this technique will work properly for any fraction that has a non-zero denominator. (Incidentally, it is actually worthwhile to make sure your fractions always have a denominator that is strictly greater than 0. That way the sign of the fraction is the sign of the numerator, a convenient state of affairs.)

In the case of 2/3, the gcd of 2 and 3 is 1 (because nothing larger than 1 divides both of them without remainder). I suspect that your gcd function is working properly but that you are somehow not using its answer properly to generate the reduced fraction you are looking for. Here is a bit of working code I just cobbled together... perhaps it will help. If you don't read C and it would be helpful to see it in a different language, let me know and I will see what I can do.

Paul

(:{=

aaarrrrgggggghhhhhh.... this thing messes up my beautiful indenting.

#include<stdlib.h>

#include<stdio.h>

int gcd(int a, int b)

{

int retval;

if (a < 0)

a = -a;

if (b < 0)

b = -b;

if (b == 0)

retval = a;

else

retval = gcd(b, a%b); /*a%b is the remainder you get when you divide a by b. /*

return retval;

}

int main(int argc, char **argv) /* tester. Treat the first two

command line arguments as numerator

and denominator. Print out the equivalent

fraction reduced to

"lowest terms" */

{

int top, bottom;

int g;

if (argc != 3)

{

fprintf(stderr, "\nUsage: %s numerator denominator\n", argv[0]);

exit(1);

}

top = atoi(argv[1]);

bottom = atoi(argv[2]);

if (bottom == 0)

{

fprintf(stderr, "\nPlease choose a non-zero denominator.\n");

exit(1);

}

g = gcd(top, bottom);

top = top / g;

bottom = bottom / g;

printf("Your fraction is equivalent to %d/%d\n", top, bottom);

}

This topic is so old that you may well have found your answer elsewhere by now, but just in case you haven't...

Euclid's Algorithm returns the greatest common divisor of two integers. You want to reduce a fraction to "lowest terms" and that means you need to find the biggest thing that will divide both the numerator and denominator, (the greatest common divisor), and then divide each by it. If your gcd function is working properly, then this technique will work properly for any fraction that has a non-zero denominator. (Incidentally, it is actually worthwhile to make sure your fractions always have a denominator that is strictly greater than 0. That way the sign of the fraction is the sign of the numerator, a convenient state of affairs.)

In the case of 2/3, the gcd of 2 and 3 is 1 (because nothing larger than 1 divides both of them without remainder). I suspect that your gcd function is working properly but that you are somehow not using its answer properly to generate the reduced fraction you are looking for. Here is a bit of working code I just cobbled together... perhaps it will help. If you don't read C and it would be helpful to see it in a different language, let me know and I will see what I can do.

Paul

(:{=

aaarrrrgggggghhhhhh.... this thing messes up my beautiful indenting.

#include<stdlib.h>

#include<stdio.h>

int gcd(int a, int b)

{

int retval;

if (a < 0)

a = -a;

if (b < 0)

b = -b;

if (b == 0)

retval = a;

else

retval = gcd(b, a%b); /*a%b is the remainder you get when you divide a by b. /*

return retval;

}

int main(int argc, char **argv) /* tester. Treat the first two

command line arguments as numerator

and denominator. Print out the equivalent

fraction reduced to

"lowest terms" */

{

int top, bottom;

int g;

if (argc != 3)

{

fprintf(stderr, "\nUsage: %s numerator denominator\n", argv[0]);

exit(1);

}

top = atoi(argv[1]);

bottom = atoi(argv[2]);

if (bottom == 0)

{

fprintf(stderr, "\nPlease choose a non-zero denominator.\n");

exit(1);

}

g = gcd(top, bottom);

top = top / g;

bottom = bottom / g;

printf("Your fraction is equivalent to %d/%d\n", top, bottom);

}

### Similar Topics

#### 0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users