Implementation of the in-built __gcd method in C++

Question

Does the in-built __gcd method in stl-algorithm library use Euclid's algorithm in its implementation?

You're asking about the implementation details of a routine that is itself an implementation detail of a specific version of the library. `__gcd` is not a standard function, and if it were standard, its precise algorithm probably wouldn't be. — user2357112, Jul 27 '14 at 13:24

score 7 · Accepted Answer · answered Jul 27 '14 at 13:24

The source code seems to be

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

So yes, it does use the Euclidean algorithm.

EDIT: I misread the question slightly, this is the implementation in the headers for g++ 4.9.1.

Implementation of the in-built __gcd method in C++

1 Answers1

Linked