By Madiyar, 4 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: AlexDmitriev noted below that we must be careful also with case __gcd(x, 0).

•
• +79
•

 » 4 years ago, # |   +20 Good to know, thanks.
 » 4 years ago, # |   0 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.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +32 but shorter to write __gcd(a, b), right?
•  » » » 4 years ago, # ^ |   +7 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.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +29 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.
•  » » 4 years ago, # ^ | ← Rev. 2 →   -15 @lavro-sindi, your code: int gcd(int a, int b){ return b == 0 ? a: gcd(b, a%b); } 
•  » » » 4 years ago, # ^ |   +7 int gcd(int a, int b) { return b ? gcd(b, a%b) : a; } 
•  » » » » 3 years ago, # ^ |   -26 int gcd(int a,int b){return b?gcd(b,a%b):a;}
•  » » 4 years ago, # ^ | ← Rev. 2 →   +30 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; } 
•  » » » 4 years ago, # ^ |   +23 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:)
•  » » » 4 years ago, # ^ |   +5 It's a perversion :).Ordinary while(b) a %= b, swap(a, b); is shorter (and faster on modern computers).
•  » » » » 4 years ago, # ^ |   +26 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 
•  » » » » » 4 years ago, # ^ |   0 inline for recursive function? I think it's not correct, is it?
•  » » » » » » 4 years ago, # ^ | ← Rev. 2 →   +8 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.
•  » » » » » » 4 years ago, # ^ |   0 Tail recursion can be eliminated and fully inlined. GCD falls into this category.
•  » » » » » » » 4 years ago, # ^ |   0 Thanks, I've understood)
•  » » » » » 4 years ago, # ^ |   +24 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; } 
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 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 ;-)
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +5 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
•  » » » » » 4 years ago, # ^ |   0 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.
•  » » » 4 years ago, # ^ |   +1 This is undefined behavior.
•  » » » » 4 years ago, # ^ |   0 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.
•  » » » » » 4 years ago, # ^ |   0 Why is it invalid?
•  » » » » » » 4 years ago, # ^ |   +13 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
•  » » » » » » » 4 years ago, # ^ |   0 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 :)
•  » » » 2 years ago, # ^ |   0 Can you explain this or provide a source for the explanation?
•  » » » 12 months ago, # ^ | ← Rev. 4 →   +10 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...
•  » » » » 12 months ago, # ^ |   0 I think your code is wrong. You should write swap(a, b) instead of a = b
•  » » » » » 12 months ago, # ^ | ← Rev. 3 →   -10 Yeah, thanks. I fixed it now.
•  » » 4 years ago, # ^ |   -21 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.
•  » » » 4 years ago, # ^ |   0 Which is UB anyway
•  » » » » 4 years ago, # ^ |   0 yeah, u're right. although i've been using it for 4-5 years and it never behave abnormally!
•  » » 3 years ago, # ^ |   0 __gcd() is faster!
 » 4 years ago, # |   +34 I use a lot standard c++ gcd function Again: it's not standard, but gcc-specific.
 » 4 years ago, # |   +19 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
•  » » 4 years ago, # ^ | ← Rev. 4 →   +3 thank you AlexDmitriev.By the way, is this bug? Maybe gcd(0, 0) = undefined, but gcd(x, 0) must be defined.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   -8 the mathematical definition is integers (including ).
 » 4 years ago, # |   +5 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?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +5 Seems true. Since we can take C = min(a, b) + 1.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +10 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.
 » 4 years ago, # |   -13 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.
•  » » 4 years ago, # ^ | ← Rev. 3 →   +28 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.
•  » » » 4 years ago, # ^ |   +5 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.
•  » » » » 4 years ago, # ^ |   +18 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
•  » » » » » 4 years ago, # ^ |   +13 Oh, you're right with first equation :).
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   +39 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
•  » » » » » » 3 years ago, # ^ | ← Rev. 3 →   0 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.
•  » » » » » » » 3 years ago, # ^ |   0 Yes, intersection is lcm. Sum is gcd. Union is not ring at all
•  » » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » » » » » 3 years ago, # ^ |   0 I missed word generated. Then it is correct.
•  » » » » 4 years ago, # ^ |   +15 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.
•  » » » » » 4 years ago, # ^ |   +5 OK, you convinced me guys :).
 » 4 years ago, # | ← Rev. 2 →   -16 U can use this : if(a==0&&b==0) return 1; else return __gcd(a,b); 
 » 4 years ago, # |   +8 you Can use __gcd ( a , b ) 
 » 4 years ago, # |   +5 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?
•  » » 4 years ago, # ^ |   +13 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.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 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))
•  » » » » 4 years ago, # ^ |   +16 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 AlexDmitriev'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.
 » 4 years ago, # |   0 I think, it's one of the shortest and fastest implementations https://pastebin.com/FAe7dfRC
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 It's wrong implementation. It will fail when b = 0. Fixing it is easy, though the code will not look cool anymore.
 » 4 years ago, # |   -8 it is the binary-gcd code that is very fast: binary-gcd code
 » 4 years ago, # |   -14 int gcd(int a,int b) { while(b!=0) { a%=b; swap(a,b); } return a; }
»
4 years ago, # |
-19

# include <bits/stdc++.h>

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

 » 3 years ago, # |   +1 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.
•  » » 3 years ago, # ^ | ← Rev. 4 →   +3 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.
 » 3 years ago, # |   +3 Hi, my Microsoft Visual Studio thinks that __gcd is undefined... Any solutions to that?
•  » » 3 years ago, # ^ |   0 visual studio compiler different than gcc. __gcd is a feature in gcc compiler, its not a std feature
 » 3 years ago, # |   -10 can __gcd(x,y) we use with x, y are long long ?
•  » » 3 years ago, # ^ |   +8 You may check it by yourself , no?
 » 2 years ago, # |   0 What is the time complexity of __gcd(x,y). Does it work on euclid's theoram?????
•  » » 23 months ago, # ^ |   0 yes
•  » » 5 months ago, # ^ |   -14 what is the time complexity of euclid's theoram ?
 » 11 months ago, # |   0 It's not working in codeblocks giving not declared in this scope,please give suggestion to solve it.