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

Tilted Forum Project Discussion Community (https://thetfp.com/tfp/)

- Tilted Technology (https://thetfp.com/tfp/tilted-technology/)

- - [c++] Euclidean Algorithm (https://thetfp.com/tfp/tilted-technology/53661-c-euclidean-algorithm.html)

TSerra

04-26-2004 11:31 AM

[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

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

All times are GMT -8. The time now is 09:28 AM.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76