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

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

Студворк — интернет-сервис помощи студентам

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

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

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);
}

@diagon · 13.10.2011, 19:21

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

C++
1
2
3
4
5
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++
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;
}

@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++
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;
     }
}

@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++
1
2
3
4
5
6
7
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++
1
2
3
4
5
6
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++
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;
    }
  }

GREGOR_812 · 03.03.2015, 22:40

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 секунд
а как скорость работы проверить?

Новые блоги и статьи Все статьи Все блоги /
Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек SDL3 и Box2D из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия SDL 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual. . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»

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

Решение

Решение

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

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	14.10.2011, 10:02
	А тесты где собственно ? Как тестировал, что тестировал ? Сферического коня в вакууме ? Бинарный алгоритм очевидно заточен на то что числа 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
	дак вы можете почитать об алгоритме Евклида у Максима Иванова Отличный сборник алгоритмов имхо 0

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

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

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