Search code examples
c++greatest-common-divisor

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

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

Solution

  • 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.