[c++] Euclidean Algorithm - Tilted Forum Project Discussion Community

TSerra · 04-26-2004, 11:31 AM

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

KnifeMissile · 04-26-2004, 11:39 AM

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...

TSerra · 04-26-2004, 11:48 AM

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

TSerra · 04-26-2004, 12:15 PM

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) {
int remainder;

while (remainder!=0) {
remainder = a % b;
a = b;
b = remainder;
}

return a;
}

KnifeMissile · 04-26-2004, 12:26 PM

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) {&#10	return b == 0 ? a : GCD( b, a % b);&#10}

It's needlessly recursive, so I would say that your implementation is better (and that you should stick with it!) but mine looks more fun...

KnifeMissile · 04-26-2004, 12:48 PM

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...

Yakk · 04-26-2004, 01:02 PM

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.

KnifeMissile · 04-26-2004, 01:09 PM

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...

04-26-2004, 11:31 AM	#1 (permalink)
TSerra Upright	[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

04-26-2004, 12:15 PM	#4 (permalink)
TSerra Upright	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) { int remainder; while (remainder!=0) { remainder = a % b; a = b; b = remainder; } return a; }

04-26-2004, 12:26 PM	#5 (permalink)
KnifeMissile Location: Waterloo, Ontario	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) {&#10 return b == 0 ? a : GCD( b, a % b);&#10} It's needlessly recursive, so I would say that your implementation is better (and that you should stick with it!) but mine looks more fun...

04-26-2004, 01:02 PM	#7 (permalink)
Yakk Wehret Den Anfängen! Location: Ontario, Canada	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. __________________ Last edited by JHVH : 10-29-4004 BC at 09:00 PM. Reason: Time for a rest.

04-26-2004, 11:39 AM	#2 (permalink)
KnifeMissile Location: Waterloo, Ontario	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...

04-26-2004, 11:48 AM	#3 (permalink)
TSerra Upright	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

04-26-2004, 12:48 PM	#6 (permalink)
KnifeMissile Location: Waterloo, Ontario	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...

04-26-2004, 01:09 PM	#8 (permalink)
KnifeMissile Location: Waterloo, Ontario	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...