Эксперт С++
4264 / 2238 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
1

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

13.10.2011, 18:41. Показов 92839. Ответов 44
Метки нет (Все метки)

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

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

C
1
2
3
4
5
6
7
8
9
10
//обычный алгоритм Евклида через остатки
long Nod(long a, long b)
{
    while (a && b)
        if (a >= b)
           a %= b;
        else
           b %= a;
    return a | b;
}
C
1
2
3
4
5
6
7
8
9
10
// Алгоритм Евклида через разности
long Nod(long a, long b)
{
    while (a && b)
        if (a >= b)
           a -= b;
        else
           b -= a;
    return a | b;
}

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// Бинарный алгоритм Евклида
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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);
}
19
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
13.10.2011, 18:41
Ответы с готовыми решениями:

Найти НОД для одномерного массива, используя алгоритм Евклида
Вопрос в том как найти НОД для одномерного массива, используя алгоритм Евклида?

Найти НОД двух целых положительных чисел А и В, используя алгоритм Евклида
Описать функцию NOD2(A,B) целого типа,находящую наибольший общий делитель(НОД) двух целых...

Алгоритм Евклида для вычисления НОД
Алгоритм Евклида для вычисления наибольшего общего делителя двух натуральных чисел, формулируется...

Алгоритм Евклида вычисления НОД - проверить корректность вычислений
Проверьте, пожалуйста, мое решение, кому не составит труда? Просто решил, а правильно или нет -...

44
Higher
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
13.10.2011, 19:21 2
Лучший ответ Сообщение было отмечено как решение

Решение

Такой тоже должен быстро работать
C++
1
2
3
4
5
int gcd( int a, int b )
{
   while( b^=a^=b^=a%=b );
   return a;
}
Правда оптимизирующие компиляторы его преимущества на нет сводят...
7
Эксперт С++
4264 / 2238 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
13.10.2011, 20:09  [ТС] 3
diagon, по моим тестам ваш алгоритм немного медленнее четырех предыдущих и с нулями на входах проблемы. Но алгоритм у вас красивый и супер компактный! По тестам у меня первый алгоритм самый быстрый из всех.
Хочется построить наиболее быстрый алгоритм.

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

Кстати, все четыре алгоритма расположены в порядке возрастания потраченного на алгоритм времени.
0
Эксперт С++
7175 / 3234 / 80
Регистрация: 17.06.2009
Сообщений: 14,164
14.10.2011, 10:02 4
А тесты где собственно ?
Как тестировал, что тестировал ?
Сферического коня в вакууме ?

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

И прогони его много раз в цикле
Бинарный алгоритм уделает твой самый первый код в разы
1
Эксперт С++
4264 / 2238 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
14.10.2011, 11:56  [ТС] 5
odip, это и так прекрасно понимаю. Может надо было с большими числами больше тестов провести, тогда бинарный алгоритм показался бы лучше, наверное, но как-нибудь в другой раз уже, что хотел, для себя уже выяснил. Первая моя цель была теоретически обосновать законность применения бинарного алгоритма и после этого попытаться его как можно эффективнее реализовать. Вроде все получилось хорошо.

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

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

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


Добавлено через 52 минуты
Спасибо, Nameless One
2
74 / 74 / 13
Регистрация: 21.10.2010
Сообщений: 376
14.10.2011, 18:25 6
дак вы можете почитать об алгоритме Евклида у Максима Иванова
Отличный сборник алгоритмов имхо
0
Эксперт С++
4264 / 2238 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
14.10.2011, 20:38  [ТС] 7
Цитата Сообщение от Hi4ko Посмотреть сообщение
дак вы можете почитать об алгоритме Евклида у Максима Иванова
Отличный сборник алгоритмов имхо
К сожалению, там ничего нового... Но зато есть 5 красивых алгоритмов вычисления НОД в данной теме
0
194 / 20 / 5
Регистрация: 05.08.2010
Сообщений: 229
14.10.2011, 21:11 8
Лучший ответ Сообщение было отмечено как решение

Решение

Еще ко всей куче добавлю:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#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;
}
3
Эксперт С++
1067 / 846 / 60
Регистрация: 30.04.2011
Сообщений: 1,659
14.10.2011, 22:10 9
Цитата Сообщение от Thinker Посмотреть сообщение
diagon, по моим тестам ваш алгоритм немного медленнее четырех предыдущих и с нулями на входах проблемы. Но алгоритм у вас красивый и супер компактный! По тестам у меня первый алгоритм самый быстрый из всех.
Хочется построить наиболее быстрый алгоритм.

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

Кстати, все четыре алгоритма расположены в порядке возрастания потраченного на алгоритм времени.
Совершенно верно. Через остатки - самый быстрый.
0
Higher
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
15.10.2011, 04:17 10
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
Совершенно верно. Через остатки - самый быстрый.
Ну, у меня и есть вариант через остатки, только в нем более оптимизированная реализация( проверяется только одно условие и для свапа переменных используется xor)
0
Заблокирован
15.10.2011, 11:31 11
bambino, зачем static_cast и typedef?
0
53 / 53 / 2
Регистрация: 06.04.2011
Сообщений: 209
15.10.2011, 17:09 12
Thinker, а можно узнать, почему вы на каждой итерации цикла проверяете if (a >= b) в данном коде?
C++
1
2
3
4
5
6
while (a && b)
        if (a >= b)
           a %= b;
        else
           b %= a;
    return a | b;
Не проще ли сделать так? (взято из книги):
C++
1
2
3
4
5
6
7
8
9
10
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;
     }
}
0
Эксперт С++
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
6 / 6 / 0
Регистрация: 17.09.2011
Сообщений: 81
16.11.2011, 20:39 14
Я пока начинающий программист. Но мне известен такой алгоритм:
C++
1
2
3
4
5
6
7
while(a!=b)
{
    if(a > b) 
        a = a - b;
    else
        b = b - a;
}
0
53 / 53 / 2
Регистрация: 06.04.2011
Сообщений: 209
16.11.2011, 20:48 15
GhostVIRUS, тут вроде бы говорится о самом быстром алгоритме А сколько итераций цикла будет в твоём алгоритме если a = 10000000000 и b = 3 ?
0
6 / 6 / 0
Регистрация: 17.09.2011
Сообщений: 81
16.11.2011, 20:54 16
Я так и думал
0
0 / 0 / 0
Регистрация: 31.01.2013
Сообщений: 6
08.08.2014, 15:10 17
Можно и так:
C++
1
2
3
4
5
6
int gcd(int a, int b)
{
     while (a && b)
          a > b ? a %= b : b %= a;
     return a | b;
}
0
4814 / 2275 / 287
Регистрация: 01.03.2013
Сообщений: 5,936
Записей в блоге: 26
08.08.2014, 16:10 18
Цитата Сообщение от Thinker Посмотреть сообщение
мои тесты показывают, что два первых алгоритма работают быстрее бинарного
Отлично, если алгоритм выполняется на компе. Там на аппаратном уровне процессора есть и деление, и остатки от него, и еще много чего. А когда я писал для восьмибитной AVR Tiny13 на ассемблере код, в котором требовалось перевести двухбайтовое число в строку, я отнимал по 10000, 1000 и т.п. и считал разряды, потому что в системе команд не было ни деления ни умножения. Это я к тому, что скорость выполнения кода зависит от того, в какие ассеблерные инструкции он скомпилируется, а последнее зависит и от кода, и от опций компилятора, и от платформы.
1
831 / 639 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
09.08.2014, 17:43 19
C++
1
2
3
4
5
6
7
8
9
10
11
unsigned gcd(unsigned a, unsigned b)
  {
  if(!b)
    return a|!a;
 
  while(1)
    {
    if(!(a%=b))   return b;
    if(!(b%=a))   return a;
    }
  }
0
27 / 27 / 5
Регистрация: 23.04.2014
Сообщений: 130
03.03.2015, 22:40 20
C++
1
2
3
4
5
6
7
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, (a % b));
}
Добавлено через 39 секунд
а как скорость работы проверить?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
03.03.2015, 22:40
Помогаю со студенческими работами здесь

Построить алгоритм Маркова, который ищет НОД (Алгоритм Евклида)
Здравствуйте, ребята, выручайте. Весь инет перерыл, всю голову сломал, но не могу сделать. Суть в...

НОД . Рекурсивный алгоритм Евклида
1. Даны два натуральных числа X и Y. Найти их наибольший общий делитель, используя рекурсивный...

Алгоритм Евклида для нахождения НОД
Уважаемые форумчане, никак не получается написать алгоритм Евклида, возможно не хватает знаний,...

НОД двух чисел алгоритм Евклида
Найти найбольший общий делитель двух чисел по алгоритму Евклида. Использовать рекурсию.


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru