no-swap gcd (small performance increase)

Revision ru4, by DortyTheGreat, 2024-05-01 16:56:53

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru6 Russian DortyTheGreat 2024-05-01 16:58:59 6
ru5 Russian DortyTheGreat 2024-05-01 16:57:38 22
ru4 Russian DortyTheGreat 2024-05-01 16:56:53 0 (опубликовано)
ru3 Russian DortyTheGreat 2024-05-01 16:56:30 3 Мелкая правка: 'устить" я не смог заме' -> 'устить" я смог заме'
ru2 Russian DortyTheGreat 2024-05-01 16:56:03 2 Мелкая правка: 'gorithm:\n~~~~~\n_' -> 'gorithm:\n\n~~~~~\n_'
ru1 Russian DortyTheGreat 2024-05-01 16:55:48 1832 Первая редакция (сохранено в черновиках)