|
[c++] Euclidean Algorithm
Hello!
Does anyone have any C++ source code that uses a simple euclidean algorithm to calculate the GCD of two integers? I tried searching but couldn't turn up what I was looking for... Thanks, Tom |
Do you just not know the various algorithms for finding the greatest common divisor or can't you just implement them, yourself? They're pretty simple and shouldn't take you long to do...
|
I have the technical aspects of the Euclidean, but I'm not sure how to translate the definition from a math textbook into c++ code.
I just thought there might be a pre-written c++ function out there that I could stick into a program and take advantage of. Thanks, Tom |
You're right, once I took the time to sit down and think about it, I came up with this, which seems to work alright.
Thanks, Tom Code:
int gcd(int a, int b) { |
Good for you! There's a small bug in your code (remainder is uninitialized) but, otherwise, it should work... You can either initialize your variables, change your while() loop into a do{}while() loop, or both...
I was about to suggest this: Code:
unsigned int GCD( unsigned int a, unsigned int b) {
 return b == 0 ? a : GCD( b, a % b);
} |
Actually, now that I look at it, both our implementations assume that b > a, which is lame. You shouldn't have to care which order you pass your integers to a GCD function but I'm sure you can fix that, while you're there...
|
Knife, actually they don't.
If b>a, his GCD code (and I assume yours) swaps a and b in the first iteration, and goes on from there. |
I think you're right. For some reason, I thought that the modulo operator might do something weird if modulus was greater than the numerator but, in retrospect, it should all be fine...
|
| All times are GMT -8. The time now is 08:06 PM. |
Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2025, vBulletin Solutions, Inc.
Search Engine Optimization by vBSEO 3.6.0 PL2
© 2002-2012 Tilted Forum Project