r.estrela's blog

Is there a long long built in __gcd in c++?
By r.estrela, history, 2 years ago, In English

Do i need to code a function everytime i wanna get the gcd of two long long variables or there is a easier solution?

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

Comments Comments (7)
| Write comment?
»
2 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

gcd<int64_t>(x,y)

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
__gcd <long long> (x, y)
→ Reply
»
2 years ago, # |
  Vote: I like it +32 Vote: I do not like it

Is __gcd wrong with two long long variables? I always use it and have not seen any problems. A test case would be helpful. Thank you

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

Why rely on an obscure, non-standard function (that might not work everywhere) when you can just implement the Euclidean algorithm yourself with only three lines of code (not counting braces)? If even that amount of typing bothers you, you can add it to your template.

long long GCD(long long x, long long y)
{
    if (y == 0) return x;
    return GCD(y, x%y);
}
→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I know in some cases, it's necessary to have a fast gcd algorithm (I have heard of something like binary gcd before I believe), especially because there is modular arithmetic in the standard euclidian gcd algorithm. This probably isn't an issue for him but it's not impossible that he's searching for a fast version of gcd with long longs?

    → Reply