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

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

@xall · 29.06.2018, 15:00

Здравствуйте, если кто ещё бывает на этой теме. Долго разбирался, как действует бинарный алгоритм (не привык я работать с битами).
Насколько я понял, первый цикл while отсекает все степени двойки, а второй фактически работает через разности, с дополнительными циклами, которые должны бы заменить остаток от деления, но в половине случаев простаивают. Попытался оптимизировать как понял:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int gcd(int a, int b)
{   
    char shift_a{}, shift_b{}; // shift_a = 0, shift_b = 0; - для C
    if (a && b)
    {
        while (!(a & 1)) {
            a >>= 1;
            ++shift_a;
        }
 
        while (!(b & 1)) {
            b >>= 1;
            ++shift_b;
        }
 
        while (a && b) a >= b ? a %= b : b %= a;
    }
    return (a | b) << (shift_a <= shift_b ? shift_a : shift_b);
}

@TheCalligrapher · 30.06.2018, 02:02

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

Долго разбирался, как действует бинарный алгоритм (не привык я работать с битами).

Данная реализация сначала просто-напросто в цикле делит исходные значения на 2 пока они делятся на 2. То, что это деление выражено через битовые сдвиги или битовые проверки никакой роли не играет - это просто манерничанье. При этом запоминается, сколько раз удалось каждое число разделить на 2 (значения shift_a и shift_b)

Дальше применяется обычный Евклидов алгоритм НОД для чисел, которые остались после деления на 2.

Когда мы получили этот НОД, надо просто умножить его на 2^{min(shift_a, shift_b)} - и готов результат. Вот тут действительно полезен побитовый сдвиг.

---

Я бы предположил, что такая оптимизация не имеет большого смысла, пока мы не пользуемся встроенными процессорными средствами для выполнения исходных исчерпывающих делений на 2. Например, для GCC

C
1
2
3
4
5
6
7
8
9
10
11
12
unsigned gcd(unsigned a, unsigned b)
{   
    unsigned shift_a = 0, shift_b = 0;
    if (a && b)
    {
        a >>= (shift_a = __builtin_ctz(a));
        b >>= (shift_b = __builtin_ctz(b));
 
        while (a && b) a >= b ? a %= b : b %= a;
    }
    return (a | b) << (shift_a <= shift_b ? shift_a : shift_b);
}

@spum · 14.05.2022, 11:25

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

А такое сможете решить?

ValeryS · 14.05.2022, 20:54

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

А такое сможете решить?

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

@TheCalligrapher · 11.09.2022, 19:58

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

Когда мы получили этот НОД, надо просто умножить его на 2^{min(shift_a, shift_b)} - и готов результат. Вот тут действительно полезен побитовый сдвиг.

Эту идею на самом деле можно развить и дальше.

Как только мы знаем, какая степень двойки является общим делителем для исходных значений a и b, промежуточные значения в процессе работы Алгоритма Евклида уже можно делить на 2 (то есть выдвигать из них замыкающие вереницы нулей) ни о чем не беспокоясь - это не приведет к искажению финального значения НОД.

В терминах C++20 получаем что-то вроде

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
unsigned gcd(unsigned a, unsigned b)
{
  unsigned pow2 = std::countr_zero(a | b); // или __builtin_ctz
 
  while (a && b)
  {
    a >>= std::countr_zero(a);
    b >>= std::countr_zero(b);
    a >= b ? a -= b : b -= a;
  }
 
  return (a | b)  << pow2;
}

или

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
unsigned gcd(unsigned a, unsigned b)
{
  unsigned pow2 = std::countr_zero(a | b);
 
  a >>= std::countr_zero(a);
  do 
  {
    b >>= std::countr_zero(b);
 
    if (a > b)
      std::swap(a, b);
 
    b -= a;
 
  } while (b > 0);
 
  return a << pow2;
}

Новые блоги и статьи Все статьи Все блоги /
Часы электронные Uhbif79 12.08.2026 Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .	Часы с будильником на основе класса QLCDNumber Uhbif79 12.08.2026 Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .	Установка MinGW GCC 16.2 и CMake 8Observer8 10.08.2026 VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия	Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо anaschu 10.08.2026 Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .
Калькулятор для расчета родства russiannick 07.08.2026 1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь	Мир по моей воле kumehtar 07.08.2026 Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .	Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .

@spum 0 / 0 / 0 Регистрация: 17.03.2022 Сообщений: 8
	14.05.2022, 11:25
	Данные цели положительные числа А и В. Найти их наибольшего общего делителя (НОД), используя алгоритм Евклида: НОД(А, В) = НОД(B, A mod В), если В ≠0; НОД(A, 0) = А, где «mod» означает операцию взятия остатка от деления. А такое сможете решить? 0