copyPasteCoder's blog

Is __gcd(x,y) slower that gcd(x,y)?
By copyPasteCoder, history, 30 hours ago, In English

For the problem 2043D - Problem about GCD,

  • 298543362 — using $$$gcd$$$ function — gives AC (578 ms)
  • 298543382 — using __$$$gcd$$$ function — gives TLE

I was earlier told that by my friends and mentors that __gcd is faster than gcd. Can anyone tell where did I go wrong $$$?$$$
  • Vote: I like it
  • +39
  • Vote: I do not like it

»
30 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

I had a similar experience, and like you, I took a time limit with __gcd time limit and exported it with GCD. This is because GCD uses the recursion method and takes much less time than normal

→ Reply
  • »
    »
    30 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So, can this make that much difference $$$?$$$
    On doing private mashup, I got running time as 1312ms (more than twice).

    → Reply
»
30 hours ago, # |
  Vote: I like it +15 Vote: I do not like it

Link Here someone had the opposite result than you.

→ Reply
»
29 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

It's weird, from my testing, it seems like:

gcd(X % Y, Y) < __gcd(X, Y) < gcd(X, Y)

in terms of runtime

→ Reply
»
26 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

I had the same experience, but I saw this post before submission so I changed __gcd to gcd after getting TLE and got accepted. But this makes me confused about which one to use!!

→ Reply
  • »
    »
    9 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    apparently std::gcd(a%b, b) is the fastest

    → Reply