CODEWITHSUNDEEP
c++algorithmdo-whilemodulus
David Loughnane
David Loughnane

Reputation: 153

c++ Greatest Common Divisor

I am very new to C++ and am attempting create a function to implement the Euclidean algorithm that returns the greatest common divisor for two integer inputs.

The current approach I am taking keeps crashing - can you help me understand why?

int main() {    
    int a = 0;
    int b = 0;

    cin >>  a;
    cin >> b;

    do {
        if ( a > b ) a = a % b;
        else if ( a < b ) b = b % a;
        else if ( a == b ) break;
    } while ( ( a || b ) != 0 ); 

    return 0;
}

Thanks,

David

Upvotes: 4

Views: 4815

Answers (4)

frogatto
frogatto

Reputation: 29285

Let's have a closer look at your codes, maybe you are curious what does while ( ( a || b ) != 0 ) do?

We now should evaluate ( a || b ) != 0. In C/C++ evaluation begins from right to left, but () has more priority, so at run-time we would have:

bool r1 = a || b;  // intermediate result
bool r2 = r1 != 0;
while(r2);

Steps:

  • a || b is evaluated to true when either a or b have non-zero value.
  • r1 will be casted to integer
    • true becomes 1
    • false becomes 0
  • r1 != 0 is evaluated and results an boolean value (true or false)
  • while decides whether it should loop or not.

Upvotes: 1

Enpi
Enpi

Reputation: 281

Your while condition is wrong. You cant simplify it like that.

while ( ( a || b ) != 0 );

It should look like this.

while ( ( a != 0 ) && ( b != 0 ) );

By the way, you could make an much easier approach. Something like this

int main() {

int a, b, r;

cin >> a;
cin >> b;

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

cout << "The GCD is " << a << endl;

}

And there is another way, it doesnt requiere code the algorithm. Just use the libstdc++ algorithm library. Libstdc++

Upvotes: 1

FireRain
FireRain

Reputation: 113

Your term ( a || b ) != 0 will not resolve as you expect.
What you want to do is (a != 0) && (b != 0)
Or as Cheers and hth. - Alf suggests just a && b.

Upvotes: 3

Armen Tsirunyan
Armen Tsirunyan

Reputation: 133072

while ( ( a || b ) != 0 );

this is wrong. It should be

while ( a != 0 && b != 0 );

On a side note, the Euclid's algorithm can be concisely implemented recursively:

int gcd(int a, int b)
{
   return b == 0 ? a : gcd(b, a%b);
}

Upvotes: 13

Related Questions