Как 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"