Как 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"↵
↵
↵
↵
------------------↵
Ниже представлен код, который находится в 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"↵
↵
↵
↵
