By Madiyar, 6 years ago, I hope this post will be helpful for someone :).

I use a lot standard c++ gcd function (__gcd(x, y)).
But today, I learnt that on some compiler __gcd(0, 0) gives exception. (Maybe because 0 is divisible by any number?! )

Note for myself and everybody: While using __gcd we must carefully handle (0, 0) case or write own gcd.

upd: riadwaw noted below that we must be careful also with case __gcd(x, 0). c++, Comments (82)
 » Good to know, thanks.
 » Why not use this for computing gcd ? int gcd(int a , int b) { if(b==0) return a; a%=b; return gcd(b,a); } This work on Euclid algorithm. It is much faster then __gcd function.
•  » » 6 years ago, # ^ | ← Rev. 2 →   but shorter to write __gcd(a, b), right?
•  » » » I know that time complexity of my function is O(log(min(a,b))) but often is faster then that. __gcd say this: _EuclideanRingElement __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n) { while (__n != 0) { _EuclideanRingElement __t = __m % __n; __m = __n; __n = __t; } return __m; } I test two c++ program: #include #include typedef unsigned long long ull; ull nzd(ull a, ull b) { if(b==0) return a; a%=b; return nzd(b,a); } ull n,m; int main() { scanf("%llu %llu",&n,&m); printf("%llu\n",nzd(n,m)); } 2. #include #include #include using namespace std; typedef unsigned long long ull; ull n,m; int main() { scanf("%llu %llu",&n,&m); printf("%llu\n",__gcd(n,m)); } On this test cases : https://sites.google.com/site/lovroshr/Home/gcd.zip?attredirects=0&d=1It seen to be a first code faster then second for 0.1 s.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   Not sure what exactly you were measuring, but I'm pretty much sure that the 0.1s of difference comes from a different place. Try to experiment with this and you'll see that your implementation is slower. For example, you can try to modify it and run on 10^6 random test cases and then compare the resutls.
•  » » 6 years ago, # ^ | ← Rev. 2 →   @lavro-sindi, your code: int gcd(int a, int b){ return b == 0 ? a: gcd(b, a%b); } 
•  » » » int gcd(int a, int b) { return b ? gcd(b, a%b) : a; } 
•  » » » » int gcd(int a,int b){return b?gcd(b,a%b):a;}
•  » » » » 9 months ago, # ^ | ← Rev. 3 →   template inline T gcd(T a, T b) { while (b != 0) swap(b, a %= b); return a; } 
•  » » 6 years ago, # ^ | ← Rev. 2 →   I have never tested it, but this realization is recursive, which may be slow. I use this, because it is fun and easy to code: // UPD: ATTENTION! This code may not work, because it is UB. int gcd(int a, int b) { while (b) b ^= a ^= b ^= a %= b; return a; } 
•  » » » Before reading your comment I used to think that my implementation is a little scary: int gcd(int a,int b){ while (a&&b)a>b?a%=b:b%=a; return a+b;} But you definitely beat it:)
•  » » » It's a perversion :).Ordinary while(b) a %= b, swap(a, b); is shorter (and faster on modern computers).
•  » » » » Actually I tested some gcd implementations and here are results:SourceFirst run: 0.994 __gcd 1.747 gcdZban 1.495 gcdA 1.482 gcdT 1.501 gcd 0.505 gcd1 Second run: 0.962 __gcd 1.779 gcdZban 1.537 gcdA 1.49 gcdT 1.5 gcd 0.506 gcd1 
•  » » » » » inline for recursive function? I think it's not correct, is it?
•  » » » » » » 6 years ago, # ^ | ← Rev. 2 →   Why not? First, an inline keyword doesn't force the compiler to inline the function, but only advises to do so. Second, for a recursive function it's possible to inline several levels of recursion and then actually perform a recursive call (just like loop unrolling). In MSVC it's even possible to directly control the level of inlining.
•  » » » » » » Tail recursion can be eliminated and fully inlined. GCD falls into this category.
•  » » » » » » » Thanks, I've understood)
•  » » » » » Sorry, but gcd1 is so fast only because it's wrong.To proove it, let's see, what variables will be equal to after each iteration, if a > 0 and b > 0. if a < b: a, b input a, a 0, a 0, 0 returned value is 0  if a >= b: a, b input a % b, a a % b, a % b 0, a % b 0, 0 returned value is 0 The fastest implementation I've got is faster than built-in, but only a little: template inline T gcd(T a, T b) { T c; while (b) { c = b; b = a % b; a = c; } return a; } 
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   I think this is faster since we dont have to use temporary variable c template inline T gcd(T a, T b) { while (b != 0) swap(b, a %= b); return a; } 
•  » » » 6 years ago, # ^ | ← Rev. 2 →   I'm using this implementation inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } It works just like version with while because of inline (I've tested it). Maybe your code is funny but my is easier to read ;-)
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   Sorry about a little irrelevant question. I wrote some function with inline and it is slower than the same function without inline. I don't know when inline was better.This is my function: bool maximize(int &a, int b) { if (a
•  » » » » » Following the C++ FAQ the keyword inline is a black box. You don't know, will inline function work faster or slower.I have best results with inlining recursive functions like GCD or DFS. Of course performance increasing is rather small, not more than 20% I guess.
•  » » » This is undefined behavior.
•  » » » » Agreed. Upvote parent. Downvote and don't use grandparent's (izban's) version -- his version of the xor swap is not valid C/C++ code.
•  » » » » » Why is it invalid?
•  » » » » » » In C/C++ there is the concept of sequence points, and you as the programmer must make sure that you (among other things) don't attempt to modify the same variable twice between two sequence points.More reading: http://c-faq.com/expr/index.html (esp. item 3.3b) http://stackoverflow.com/questions/4176328/undefined-behavior-and-sequence-points
•  » » » » » » » Very interesting, thank you. I have been writing such code for ~5 years, and I didn't know, that is is UB. Perhaps, you have saved me from a fail on some official competition :)
•  » » » Can you explain this or provide a source for the explanation?
•  » » » 3 years ago, # ^ | ← Rev. 4 →   If you will just look at your xor operations and remember that a^a=0, then you'll know that all this xor is just next function: int gcd(int a, int b) { while (b) { b=a%b; swap(a,b); } return a; } it is easier to code, so...
•  » » » » I think your code is wrong. You should write swap(a, b) instead of a = b
•  » » » » » 3 years ago, # ^ | ← Rev. 3 →   Yeah, thanks. I fixed it now.
•  » » » » Is Euclidean algorithm faster than __gcd(a,b)?
•  » » if u're looking for faster code, i think this'll come in handy too: int gcd(int a, int b) { while(b ^= a ^= b ^= a = a % b); return a; } it's all arithmetic and binary operations.
•  » » » Which is UB anyway
•  » » » » yeah, u're right. although i've been using it for 4-5 years and it never behave abnormally!
•  » » __gcd() is faster!
•  » » int gcd(int a , int b) { if(b==0) return a; a%=b; return gcd(b,a); }
 » I use a lot standard c++ gcd function Again: it's not standard, but gcc-specific.
 » Well, in headers I see that on my computer it's defined in the following way: template inline _LIBCPP_INLINE_VISIBILITY _Integral __gcd(_Integral __x, _Integral __y) { do { _Integral __t = __x % __y; __x = __y; __y = __t; } while (__y); return __x; } So even __gcd(x, 0) won't work
•  » » 6 years ago, # ^ | ← Rev. 4 →   thank you riadwaw.By the way, is this bug? Maybe gcd(0, 0) = undefined, but gcd(x, 0) must be defined.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   the mathematical definition is integers (including ).
 » By the way I heard that if we compute using the Euclid algorithm for N times, it will be not but . Can anybody say something about it?
•  » » 6 years ago, # ^ | ← Rev. 2 →   Seems true. Since we can take C = min(a, b) + 1.
•  » » 6 years ago, # ^ | ← Rev. 2 →   It is easy to prove in the same way as asymptotic of Euclid algorithm is proven.You probably know how asymptotic of Euclid algorithm for 2 numbers is proven. Suppose worst possible case. Take a look at pair (a,b), where a(0,a+c)->(a+c,a+c)->(a+c,2*a+2*c) you will get pair (a+c,2*a+2*c). This pair is not better than (a+c,2*a+c), because c>0. And you made just 2 additional moves.As far as you can do only O(N) moves "decrease X", and every such move gives you only 2 additional steps of Euclid algorithm, this proves your claim.
•  » » » Or by the (perhaps faster) argument that the bigger number always becomes smaller than the smaller number after one iteration of gcd, and for further iterations of gcd the bigger number becomes at most half of its previous value (it’s not hard to see why). So $N + 2 * log(C)$ is an upper bound.
 » Lol, what do you expect to be gcd(0, 0)? It is not well defined, so it should give exception. But fact that gcd(x, 0) is not working is indeed a shame :P.
•  » » 6 years ago, # ^ | ← Rev. 3 →   Well, I expect it to be defined to 0 because it's the only value that will not break equalities gcd(a1, a2, a3 ... an) = gcd(gcd(...gcd(a1,a2), a3), a4, ... an) gcd(ax, ay) = a gcd(x,y) //Up to sign, but I'd say that both x and -x are gcd and that's matter of another discussion, one may change it to abs(a)and (less importantly) gcd(a, a) = a gcd(a, ka) = aIt's as defining a^0, first of all we define a^n and then say "Well, it could not be anything but 1 and it seems to work well". Or same with sum/product of empty list.
•  » » » Let me disagree. It's definitely not like defining empty sums or empty products. In those equalities you wrote, once you have 0 somewhere in gcd computations you keep obtaining, so all calculation from that point are useless. Empty sums and products are very useful and are a good start to make useful computations.First equality will still hold if we assume that gcd(0, 0) = undefined and demand of holding second equality in case of a=0 is like demand of dividing by 0 (or like demand that 5 * 0 / 0 = 5).Frankly saying — useless discussion :P.
•  » » » » Well, I like useless discussions :DBut I don't agree first equation will not hold if gcd(0,0) undefined.Consider case gcd(0,0,5) = 5, not undefined:)BTW I do agree that some expectation make break smth if we define them to expected value (like 5*0/0=5) bit I don't anything that gcd(0,0)=0 will break
•  » » » » » Oh, you're right with first equation :).
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   Actually gcd could be interpered as intersection (or sum, in euclid rings it is the same) of ideals generating by one element. In this case it is obvious that •  » » » » » » 5 years ago, # ^ | ← Rev. 3 →   No it can't, the intersection of two ideals creates the lcm and not the gcd (else we would have a big problem since primes are equivalent to maximal ideals), gcd is the ideal generated by the union of the other two ideals. Your point that it becomes zero is still valid though.
•  » » » » » » » Yes, intersection is lcm. Sum is gcd. Union is not ring at all
•  » » » » » » » » 5 years ago, # ^ | ← Rev. 2 →   The ideal generated by a set is defined to be the smallest ideal containing said set, so yes the ideal generated by the union of two ideals is still an ideal.
•  » » » » » » » » » I missed word generated. Then it is correct.
•  » » » » It is really useful being treated as neutral element in monoid of integer numbers respective to GCD operation.You can use it when you calculate cumulative GCD's of several numbers: you can set initial value to 0 and then iterate in usual way making val = gcd(val, A[i]). Any good GCD implementation will work with this pattern.It's also easier to write GCD segment tree using this property.
•  » » » » » OK, you convinced me guys :).
 » 6 years ago, # | ← Rev. 2 →   U can use this : if(a==0&&b==0) return 1; else return __gcd(a,b); 
 » you Can use __gcd ( a , b ) 
 » Hey, I want to bring this topic once again. I included this line: assert(__gcd(5, 0) == 5 && __gcd(0, 5) == 5 && __gcd(0, 0) == 0); in one of my code and ran it locally and in custom invocation on CF and it went successfully in both cases, but this comment: http://codeforces.com/blog/entry/13410#comment-182865 clearly proves that it shouldn't. So, what is going on? When can we use __gcd safely, when can't we? It depends on specific compiler and we should know which compilers provide safe implementation and which don't, am I right?
•  » » I looked into headers of g++ on my computer (versions 4.8.3 and 4.9.2). This is how __gcd implemented there:  /** * This is a helper function for the rotate algorithm specialized on RAIs. * It returns the greatest common divisor of two integer values. */ template _EuclideanRingElement __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n) { while (__n != 0) { _EuclideanRingElement __t = __m % __n; __m = __n; __n = __t; } return __m; } I'm not sure if it was always implemented this way or it was fixed recently in gcc.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   So it means GNU C++'s __gcd will work with (0, 0) (returning 0) and (x, 0) (returning x, regardless of given (0, x) or (x, 0))
•  » » » » Right.Moreover, if you look into the GNU GCC sources, it was always written this way in libstdc++ and the reason it was added is to be used internally in the implementation of std::rotate algorithm. But it seems the algorithm was rewritten in 2009 and this function is not used internally anymore. Since it's an internal function it may happen that GCC devs will just remove it on the next code cleanup, if they don't have some other reasons to keep it.Regarding the riadwaw's comment, turns out it's the implementation from LLVM's libc++ and there it is also used internally to implement std::rotate algorithm, but they do all the necessary checks to ensure that (__x != 0 && __y != 0) before calling the function.
 » I think, it's one of the shortest and fastest implementations https://pastebin.com/FAe7dfRC
•  » » 6 years ago, # ^ | ← Rev. 2 →   It's wrong implementation. It will fail when b = 0. Fixing it is easy, though the code will not look cool anymore.
 » it is the binary-gcd code that is very fast: binary-gcd code
 » int gcd(int a,int b) { while(b!=0) { a%=b; swap(a,b); } return a; }
»

# include <bits/stdc++.h>

using namespace std; int main() { cout<<__gcd(455,343); return 0; }

 » A bit unrelated but I just wonder where you got it and if there are any more of such special functions in C/C++. I am just a newbie, thus I love learning more. Thank you.
•  » » 5 years ago, # ^ | ← Rev. 4 →   It comes from practice. While I was solving a problem, I discovered this bug.By Special function, what you mean? Is it special functions of C/C++ that you can use? Clickor C++ related bugs and special cases? Click Click Click Click I hope this will help you, a few links on my mind.
 » Hi, my Microsoft Visual Studio thinks that __gcd is undefined... Any solutions to that?
•  » » visual studio compiler different than gcc. __gcd is a feature in gcc compiler, its not a std feature
 » can __gcd(x,y) we use with x, y are long long ?
•  » » You may check it by yourself , no?
 » What is the time complexity of __gcd(x,y). Does it work on euclid's theoram?????
•  » » yes
•  » » what is the time complexity of euclid's theoram ?
 » It's not working in codeblocks giving not declared in this scope,please give suggestion to solve it.
 » while(1==1) { k=__gcd(a,n); if(n==0) { cout<<1<
 » 16 months ago, # | ← Rev. 2 →   In C++17 you can simply use std::gcd(x, y) or std::lcm(x, y).
 » Maybe __gcd is not a standard function?However, std::gcd` is a standard function in C++17.
 » Thanks.