adviser's blog

Alert : wrong gcd inbuild function in c++
By adviser, history, 2 years ago, In English

I was solving a question on gcd : (https://codeforces.com/contest/798/problem/C). here the inbuild function of gcd in c++ i.e __gcd(a,b) gives the wrong answer. the gcd of -2 and 4 should be 2. but inbuild function in sublime gives answer -2. can anyone explain why? later when i searced i founded that __gcd(a,b) == __gcd(|a|,|b|) but there is no where written that you only have to pass non negative number in GCD funtion in c++. thank you in advance.

  • Vote: I like it
  • -20
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

As i am newbie please don't just do downvote and go. if you cannot help atleast don't downvote. I am learning things. and it will take some time for me to learn and reach red

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 3   Vote: I like it +11 Vote: I do not like it

    Some functions with negative number can work strange in C++ (gcd, %). In case of gcd, i recommend to use function abs() if negative numbers are possible.

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    It depends on the compiler, you also face such kind of problem in the inbuilt power function of c++

    → Reply
»
2 years ago, # |
  Vote: I like it +20 Vote: I do not like it

The implementation might differ depending on compiler, but this is the implementation of __gcd in MinGW 10.2.0 for example:

Under spoiler cause image is big

As you can see, the implementation doesn't care about positives or negatives. If you trace the code for your specific input, you'll see why it's -2.

→ Reply
»
2 years ago, # |
  Vote: I like it +22 Vote: I do not like it

If you want to get the abs of the answer, use std::gcd in C++17 instead.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    i am using c++17 only. still getting that answer

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +41 Vote: I do not like it

      That's because you are using __gcd(a,b) instead of gcd(a,b).

      → Reply
»
2 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Try to use gcd instead of __gcd:

#include <bits/stdc++.h>
using namespace std;
int main() {
    int a = -2, b = 4;
    cout << __gcd(a,b) << endl;
    cout << gcd(a,b) << endl;
}

Output:

-2
2
→ Reply