Как gcd делается в c++?

Ниже представлен код, который находится в algorithm:

_EuclideanRingElement __gcd(_EuclideanRingElement __m,
                            _EuclideanRingElement __n)
{
  while (__n != 0) {
    _EuclideanRingElement __t = __m % __n;
    __m = __n;
    __n = __t;
  }
  return __m;
}

Как видно, в данном коде есть явный фрагмент, который выполняет обмен элементами.

Как gcd делают в одну строчку?

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

Может показаться, что в данном коде нет никакого обмена, но при вызове рекурсии компилятору нужно запихнуть переменные в новые участки памяти. К счастью, компиляторы умные и умеют "разворачивать" такие рекурсии, уменьшая время работы. Однако даже в таком случае код выполняет фактически ту же операцию обмена.

Ну как же не обменивать?

template<typename T>
inline T gcd(T a, T b)
{
    if (b == 0) return a;
    while(a %=b) if (!(b %= a)) return a;
    return b;
}

Данный код как раз не выполняет тот самый обмен. Вместо этого тут есть нечто вроде 2 частей кода, одна из них предполагает, что $$$a$$$ — большее число, а вторая, что $$$b$$$ — большее число. Как нетрудно додумать после операции взятия остатка так оно и будет.

На практике, на своём компьютере я получил небольшое увеличение в скорости (около 10%) по сравнению с обычным __gcd из algorithm. Однако, делая запуски во вкладке "Запустить" я смог заметить изменения лишь где-то в 2-3%, что уже можно списать на разброс в случайных данных.

Какой же итог?

Сильно много вычислительной мощи Вы не получите, использовав мой код. А если вам вдруг нужен быстрый gcd, то вам стоит загуглить "binary gcd"