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