[stettybet0]

I'm currently using an implementation of the Euclidean algorithm in a program I am developing in order to take a decimal answer and display it as a fraction. For example, I entered 2/18, the program would use the Euclidean algorithm to display the answer as 1/9, instead of .1111111111 (indefinitely repeating). Every number combination I've tried works fine, with the exception of 2/3. Whenever I enter 2/3 (or 4/6, 6/9, etc.), the program always displays the answer as 2/2. So, the question is, is the Euclidean algorithm not capable of correctly calculating 2/3, or is it just that my implementation of the Euclidean algorithm is incorrect?

[Advertisements]

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);
}

[PaulOF]

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);
}