Jump to content

Welcome to Geeks to Go - Register now for FREE

Geeks To Go is a helpful hub, where thousands of volunteer geeks quickly serve friendly answers and support. Check out the forums and get free advice from the experts. Register now to gain access to all of our features, it's FREE and only takes one minute. Once registered and logged in, you will be able to create topics, post replies to existing threads, give reputation to your fellow members, get your own private messenger, post status updates, manage your profile and so much more.

Create Account How it Works
Photo

Euclidean algorithm can't handle 2/3?


  • Please log in to reply

#1
stettybet0

stettybet0

    Trusted Tech

  • Technician
  • 2,579 posts
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?
  • 0

Advertisements


#2
PaulOF

PaulOF

    Member

  • Member
  • PipPip
  • 20 posts
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);
}
  • 0






Similar Topics

0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users

As Featured On:

Microsoft Yahoo BBC MSN PC Magazine Washington Post HP