but shorter to write __gcd(a, b), right?

@lavro-sindi, your code:

int gcd(int a, int b){
    return b == 0 ? a: gcd(b, a%b);
}

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;
}

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.

__gcd(_EuclideanRingElement __m, _EuclideanRingElement n) { while (n != 0) { _EuclideanRingElement __t = __m % __n; __m = __n; __n = __t; } return __m; } why? __gcd use Euclid algorithm too

thank you riadwaw.

By the way, is this bug? Maybe gcd(0, 0) = undefined, but gcd(x, 0) must be defined.

Seems true. Since we can take C = min(a, b) + 1.

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<b. It was received from (b,a+b). This one was received from (a+2*b,a+b). Previous one was (2*a+3*b,a+2*b)... You know from the proof, that Fibonacci numbers are actually worst possible case, and it takes log(C) to count GCD of 2 Fibonacci numbers less than C, and also to count GCD of any 2 numbers less then C.

Now if you have more than 2 numbers — let's do all the same moves in reverse order. If you have a pair (a,a+c), and currently working with number on position X, you should move to (a+c,2*a+c), like in Euclid algorithm with 2 numbers. Then you have a choise — you could either say "ok, 2*a+c was number on position X in input", and move to X-1, receiving pair (0,a+c), or say "a+c was number on position X in input" (then you'll move to X-1, receiving pair (0,2*a+c)), or you may keep going with this pair. It is clear that choosing 2*a+c for position X is worse, because choosing a+c gives you pair with larger numbers:) If you will decide to move from X to X-1 with 2*a+c, then in 3 moves (a+c,2*a+c)->(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.

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) = a

It'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.

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<typename _EuclideanRingElement>
    _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.

It's wrong implementation. It will fail when b = 0. Fixing it is easy, though the code will not look cool anymore.

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?
Click

or C++ related bugs and special cases?
Click
Click
Click
Click

I hope this will help you, a few links on my mind.

You may check it by yourself , no?

yes

It has UB and it was already mentioned above. Please read comments before necroposting.

Because you should implement it like this: int gcd(int a, int b) { if(b==0) return a; return gcd(b,a%b); }. I don't know what does your initial code do.