Самый быстрый алгоритм Евклида вычисления НОД

@Thinker · Регистрация: 26.08.2011

Заинтересовал вопрос о различных реализациях алгоритма Евклида для неотрицательных целых чисел. Ниже привожу алгоритмы, собственноручно написанные, исходя из теоретического материала. Каждый алгоритм можно модифицировать в ту или иную сторону.

Считается, что бинарный алгоритм работает быстрее, но мои тесты показывают, что два первых алгоритма работают быстрее бинарного. Может ли кто перепроверить на скорость на своих компиляторах, а то очень интересно и не видится никаких преимуществ бинарного алгоритма.

C

//обычный алгоритм Евклида через остатки
long Nod(long a, long b)
{
    while (a && b)
        if (a >= b)
           a %= b;
        else
           b %= a;
    return a | b;
}

C

// Алгоритм Евклида через разности
long Nod(long a, long b)
{
    while (a && b)
        if (a >= b)
           a -= b;
        else
           b -= a;
    return a | b;
}

C

// Бинарный алгоритм Евклида
long Nod(long a, long b)
{
    long deg = 0;
    if (a == 0 || b == 0)
        return a | b;
    while (((a | b) & 1) == 0)
    {
        deg++;
        a >>= 1;
        b >>= 1;
    }
    while (a && b)
    {
        if (b & 1)
            while ((a & 1) == 0)
                a >>= 1;
        else
            while ((b & 1) == 0)
                b >>= 1;
        if (a >= b)
            a = (a - b) >> 1;
        else
            b = (b - a) >> 1;
    }
    return ((a | b) << deg);
}

Еще один бинарный алгоритм, но он самый медленный из всех предыдущих.

C

long Nod(long a, long b)
{
    long buf, deg = 0;
    if (a == 0 || b == 0)
        return a | b;
    while (((a | b) & 1) == 0)
    {
        deg++;
        a >>= 1;
        b >>= 1;
    }
    if (a)
        while ((a & 1) == 0)
            a >>= 1;
    while (b)
    {
        while ((b & 1) == 0)
            b >>= 1;
        if (a < b)
            b -= a;
        else
        {
            buf = a - b;
            a = b;
            b = buf;
        }
        b >>= 1;
    }
    return (a << deg);
}

@diagon · 13.10.2011, 19:21

Такой тоже должен быстро работать

C++

int gcd( int a, int b )
{
   while( b^=a^=b^=a%=b );
   return a;
}

Правда оптимизирующие компиляторы его преимущества на нет сводят...

@Thinker · 13.10.2011, 20:09 **[ТС]**

diagon, по моим тестам ваш алгоритм немного медленнее четырех предыдущих и с нулями на входах проблемы. Но алгоритм у вас красивый и супер компактный! По тестам у меня первый алгоритм самый быстрый из всех.
Хочется построить наиболее быстрый алгоритм.

А самое интересное это то, что если он и правда наиболее быстрый, плюс ко всему на его базе легко строится расширенный алгоритм Евклида, чего о других алгоритмах нельзя сказать. Тогда первый алгоритм самый лучший получается.

Кстати, все четыре алгоритма расположены в порядке возрастания потраченного на алгоритм времени.

@odip · 14.10.2011, 10:02

А тесты где собственно ?
Как тестировал, что тестировал ?
Сферического коня в вакууме ?

Бинарный алгоритм очевидно заточен на то что числа a и b делятся на некоторую степень 2
Сделай например такой тест
n= random(4,10)
a= n*random(1,1000)
b= n*random(1,1000)
d= NOD(a,b)

И прогони его много раз в цикле
Бинарный алгоритм уделает твой самый первый код в разы

@Thinker · 14.10.2011, 11:56 **[ТС]**

odip, это и так прекрасно понимаю. Может надо было с большими числами больше тестов провести, тогда бинарный алгоритм показался бы лучше, наверное, но как-нибудь в другой раз уже, что хотел, для себя уже выяснил. Первая моя цель была теоретически обосновать законность применения бинарного алгоритма и после этого попытаться его как можно эффективнее реализовать. Вроде все получилось хорошо.

Сообщение от odip

Сферического коня в вакууме ?

Давайте без иронии, не смешно. Поэтому и создал тему, может кто более объективно протестирует, так как сложность всех алгоритмов тяжело вычислить, тут разные классы случаев надо рассматривать.

Добавлено через 7 минут
господа модераторы, а можно эти алгоритмы и алгоритм из поста 2 куда-нибудь поместить, чтобы любой желающий мог легко найти? А то 5 неплохих алгоритмов вычисления НОД могут кануть в небытие.

Комментарий модератора

Тут: Большая коллекция решенных задач

Добавлено через 52 минуты
Спасибо, Nameless One

@Hi4ko · 14.10.2011, 18:25

дак вы можете почитать об алгоритме Евклида у Максима Иванова
Отличный сборник алгоритмов имхо

@Thinker · 14.10.2011, 20:38 **[ТС]**

Сообщение от Hi4ko

дак вы можете почитать об алгоритме Евклида у Максима Иванова
Отличный сборник алгоритмов имхо

К сожалению, там ничего нового... Но зато есть 5 красивых алгоритмов вычисления НОД в данной теме

@bambino · 14.10.2011, 21:11

Еще ко всей куче добавлю:

C++

#include <iostream>
 
template <int x, int y>
struct gcd
{
private:
  const static int _value1 = y,
                   _value2 = x % y;
  typedef gcd<static_cast<int>(_value1),
              static_cast<int>(_value2)>
              next_step_type;
 
public:
  const static int value = next_step_type::value;
};
 
template <int x>
struct gcd<x, 0>
{
  const static int value = x;
};
 
int main(){
  std::cout << gcd<2344, 5432>::value << std::endl;
  return 0;
}

@ValeryLaptev · 14.10.2011, 22:10

Сообщение от Thinker

diagon, по моим тестам ваш алгоритм немного медленнее четырех предыдущих и с нулями на входах проблемы. Но алгоритм у вас красивый и супер компактный! По тестам у меня первый алгоритм самый быстрый из всех.
Хочется построить наиболее быстрый алгоритм.

А самое интересное это то, что если он и правда наиболее быстрый, плюс ко всему на его базе легко строится расширенный алгоритм Евклида, чего о других алгоритмах нельзя сказать. Тогда первый алгоритм самый лучший получается.

Кстати, все четыре алгоритма расположены в порядке возрастания потраченного на алгоритм времени.

Совершенно верно. Через остатки - самый быстрый.

@diagon · 15.10.2011, 04:17

Сообщение от ValeryLaptev

Совершенно верно. Через остатки - самый быстрый.

Ну, у меня и есть вариант через остатки, только в нем более оптимизированная реализация( проверяется только одно условие и для свапа переменных используется xor)

@~~LosAngeles~~ · 15.10.2011, 11:31

bambino, зачем static_cast и typedef?

@stdcout · 15.10.2011, 17:09

Thinker, а можно узнать, почему вы на каждой итерации цикла проверяете if (a >= b) в данном коде?

C++

while (a && b)
        if (a >= b)
           a %= b;
        else
           b %= a;
    return a | b;

Не проще ли сделать так? (взято из книги):

C++

std::size_t gcd(std::size_t a, std::size_t b)
{
     std::size_t temp;
     while (b)
     {
          temp = a % b;
          a = b;
          b = temp;
     }
}

@Thinker · 15.10.2011, 19:37 **[ТС]**

Сообщение от stdcout

Thinker, а можно узнать, почему вы на каждой итерации цикла проверяете if (a >= b) в данном коде?

В вашем алгоритме учтено свойство остатков r1>r2>..., на этом основан ваш алгоритм и это я прекрасно знаю тоже (с теорией чисел знаком). Мои тесты показали, что такой вариант медленнее работает, поэтому остановился на варианте с if. Но, именно предложенный вами вариант я использую за основу расширенного алгоритма Евклида, позволяющего (помимо нод) искать частное решение уравнения
ax+by = (a,b)

Вообще исходя из обычного алгоритма Евклида и бинарного можно легко создавать гибридные алгоритмы.

@GhostVIRUS · 16.11.2011, 20:39

Я пока начинающий программист. Но мне известен такой алгоритм:

C++

while(a!=b)
{
    if(a > b) 
        a = a - b;
    else
        b = b - a;
}

@stdcout · 16.11.2011, 20:48

GhostVIRUS, тут вроде бы говорится о самом быстром алгоритме

А сколько итераций цикла будет в твоём алгоритме если a = 10000000000 и b = 3 ?

@GhostVIRUS · 16.11.2011, 20:54

Я так и думал

@mlepehin · 08.08.2014, 15:10

Можно и так:

C++

int gcd(int a, int b)
{
     while (a && b)
          a > b ? a %= b : b %= a;
     return a | b;
}

@_Ivana · 08.08.2014, 16:10

Сообщение от Thinker

мои тесты показывают, что два первых алгоритма работают быстрее бинарного

Отлично, если алгоритм выполняется на компе. Там на аппаратном уровне процессора есть и деление, и остатки от него, и еще много чего. А когда я писал для восьмибитной AVR Tiny13 на ассемблере код, в котором требовалось перевести двухбайтовое число в строку, я отнимал по 10000, 1000 и т.п. и считал разряды, потому что в системе команд не было ни деления ни умножения. Это я к тому, что скорость выполнения кода зависит от того, в какие ассеблерные инструкции он скомпилируется, а последнее зависит и от кода, и от опций компилятора, и от платформы.

@Qwertiy · 09.08.2014, 17:43

C++

unsigned gcd(unsigned a, unsigned b)
  {
  if(!b)
    return a|!a;
 
  while(1)
    {
    if(!(a%=b))   return b;
    if(!(b%=a))   return a;
    }
  }

GREGOR_812 · 03.03.2015, 22:40

C++

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, (a % b));
}

Добавлено через 39 секунд
а как скорость работы проверить?

Самый быстрый алгоритм Евклида вычисления НОД

Решение

Решение

@Thinker 4264 / 2238 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	13.10.2011, 20:09 [ТС]	3
	diagon, по моим тестам ваш алгоритм немного медленнее четырех предыдущих и с нулями на входах проблемы. Но алгоритм у вас красивый и супер компактный! По тестам у меня первый алгоритм самый быстрый из всех. Хочется построить наиболее быстрый алгоритм. А самое интересное это то, что если он и правда наиболее быстрый, плюс ко всему на его базе легко строится расширенный алгоритм Евклида, чего о других алгоритмах нельзя сказать. Тогда первый алгоритм самый лучший получается. Кстати, все четыре алгоритма расположены в порядке возрастания потраченного на алгоритм времени. 0

@odip 7175 / 3234 / 80 Регистрация: 17.06.2009 Сообщений: 14,164
	14.10.2011, 10:02	4
	А тесты где собственно ? Как тестировал, что тестировал ? Сферического коня в вакууме ? Бинарный алгоритм очевидно заточен на то что числа a и b делятся на некоторую степень 2 Сделай например такой тест n= random(4,10) a= nrandom(1,1000) b= nrandom(1,1000) d= NOD(a,b) И прогони его много раз в цикле Бинарный алгоритм уделает твой самый первый код в разы 1

@Hi4ko 74 / 74 / 13 Регистрация: 21.10.2010 Сообщений: 376
	14.10.2011, 18:25	6
	дак вы можете почитать об алгоритме Евклида у Максима Иванова Отличный сборник алгоритмов имхо 0

@Thinker 4264 / 2238 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	14.10.2011, 20:38 [ТС]	7
	Сообщение от Hi4ko дак вы можете почитать об алгоритме Евклида у Максима Иванова Отличный сборник алгоритмов имхо К сожалению, там ничего нового... Но зато есть 5 красивых алгоритмов вычисления НОД в данной теме 0

@ValeryLaptev 1067 / 846 / 60 Регистрация: 30.04.2011 Сообщений: 1,659
	14.10.2011, 22:10	9
	Сообщение от Thinker diagon, по моим тестам ваш алгоритм немного медленнее четырех предыдущих и с нулями на входах проблемы. Но алгоритм у вас красивый и супер компактный! По тестам у меня первый алгоритм самый быстрый из всех. Хочется построить наиболее быстрый алгоритм. А самое интересное это то, что если он и правда наиболее быстрый, плюс ко всему на его базе легко строится расширенный алгоритм Евклида, чего о других алгоритмах нельзя сказать. Тогда первый алгоритм самый лучший получается. Кстати, все четыре алгоритма расположены в порядке возрастания потраченного на алгоритм времени. Совершенно верно. Через остатки - самый быстрый. 0

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	15.10.2011, 04:17	10
	Сообщение от ValeryLaptev Совершенно верно. Через остатки - самый быстрый. Ну, у меня и есть вариант через остатки, только в нем более оптимизированная реализация( проверяется только одно условие и для свапа переменных используется xor) 0

@~~LosAngeles~~ Заблокирован
	15.10.2011, 11:31	11
	bambino, зачем static_cast и typedef? 0

@Thinker 4264 / 2238 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	15.10.2011, 19:37 [ТС]	13
	Сообщение от stdcout Thinker, а можно узнать, почему вы на каждой итерации цикла проверяете if (a >= b) в данном коде? В вашем алгоритме учтено свойство остатков r1>r2>..., на этом основан ваш алгоритм и это я прекрасно знаю тоже (с теорией чисел знаком). Мои тесты показали, что такой вариант медленнее работает, поэтому остановился на варианте с if. Но, именно предложенный вами вариант я использую за основу расширенного алгоритма Евклида, позволяющего (помимо нод) искать частное решение уравнения ax+by = (a,b) Вообще исходя из обычного алгоритма Евклида и бинарного можно легко создавать гибридные алгоритмы. 0

@stdcout 53 / 53 / 2 Регистрация: 06.04.2011 Сообщений: 209
	16.11.2011, 20:48	15
	GhostVIRUS, тут вроде бы говорится о самом быстром алгоритме А сколько итераций цикла будет в твоём алгоритме если a = 10000000000 и b = 3 ? 0

@GhostVIRUS 6 / 6 / 0 Регистрация: 17.09.2011 Сообщений: 81
	16.11.2011, 20:54	16
	Я так и думал 0

@_Ivana 4814 / 2275 / 287 Регистрация: 01.03.2013 Сообщений: 5,936 Записей в блоге: 26
	08.08.2014, 16:10	18
	Сообщение от Thinker мои тесты показывают, что два первых алгоритма работают быстрее бинарного Отлично, если алгоритм выполняется на компе. Там на аппаратном уровне процессора есть и деление, и остатки от него, и еще много чего. А когда я писал для восьмибитной AVR Tiny13 на ассемблере код, в котором требовалось перевести двухбайтовое число в строку, я отнимал по 10000, 1000 и т.п. и считал разряды, потому что в системе команд не было ни деления ни умножения. Это я к тому, что скорость выполнения кода зависит от того, в какие ассеблерные инструкции он скомпилируется, а последнее зависит и от кода, и от опций компилятора, и от платформы. 1