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

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

@evgr · 05.03.2015, 06:20

GREGOR_812, для этого в библиотеке time.h есть функции

C
1
2
time_t time(time_t *time);
clock_t clock(void);

Однако имейте ввиду, что рекурсивные алгоритмы, как правило, не отличаются высокой скоростью работы.

@Qwertiy · 05.03.2015, 10:39

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

Однако имейте ввиду, что рекурсивные алгоритмы, как правило, не отличаются высокой скоростью работы.

Если компилятор не решит развернуть рекурсию?)

@evgr · 05.03.2015, 10:47

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

решит развернуть рекурсию

Ну тогда алгоритм несомненно перестанет быть рекурсивным. А вообще зачем писать код с рекурсией и надеяться на компилятор, если можно сразу создать алгоритм без использования рекурсии?

GREGOR_812 · 05.03.2015, 16:20

evgr,

Не по теме:

ко мне можно на ты

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

@castorsky · 05.03.2015, 18:14

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

Ну тогда алгоритм несомненно перестанет быть рекурсивным

алгоритм не может быть сначала рекурсивным, а после компиляции исходников стать не рекурсивным.

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

А вообще зачем писать код с рекурсией и надеяться на компилятор, если можно сразу создать алгоритм без использования рекурсии?

Надо понимать что говорите. А говорите Вы откровенную, простите, чушь. Итерация - частный случай рекурсии, если что. Оптимизация рекурсии явление не новое и если компилятор этого не умеет, то стоит задуматься о целесообразности его использования.

@evgr · 06.03.2015, 08:45

castorsky, а ещё было бы неплохо понимать, что вы пишите. А пишите вы, судя по всему, как Бог на душу положит. "Ааа, зачем мне вообще нужна оптимизация? Компилятор же всё сам за меня сделает!" - думаете вы. А потом, что дизассемблируете ваш экзешник и смотрите, действительно ли компилятор всё оптимизировал? Даже если так, оно вам надо? Не проще сразу писать нормальный код, чем приобретать себе лишнюю головную боль?

@castorsky · 06.03.2015, 10:36

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

а ещё было бы неплохо понимать, что вы пишите

я все прекрасно понимаю, и Вам пытаюсь донести. Вот Вам рекурсивный алгоритм
$https://www.cyberforum.ru/cgi-bin/latex.cgi?f \left( x \right) = \left\{\begin{matrix}0, x = 0\\ g \left(f, x \right), x < 0 \\ h \left(f, x \right), x > 0\end{matrix}\right.$
реализуйте на своё усмотрение, или как рекурсию, или как частный случай рекурсии - итерацию. Как Вам будет угодно.

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

А пишите вы, судя по всему, как Бог на душу положит. "Ааа, зачем мне вообще нужна оптимизация? Компилятор же всё сам за меня сделает!" - думаете вы.

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

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

Не проще сразу писать нормальный код

Боюсь что Вы только на пороге к понимаю этих слов.

@evgr · 06.03.2015, 11:09

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

Вот Вам рекурсивный алгоритм

Да вы пытаетесь меня втянуть в какую-то специальную олимпиаду! Смотрите, как бы вас кто-нибудь также не развёл на слабо и не заставил сделать за него что-нибудь

Давайте-ка свернём эту дискуссию, если вы не против?

@castorsky · 06.03.2015, 11:25

Не по теме:

Простейшие основы матана для Вас оленьпиада? Тут надо курить матчасть. Я указал Вам на ошибку, как человек рациональный Вы долны поразмыслить на сказанным.

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

Давайте-ка свернём эту дискуссию, если вы не против?

ЧТД.

Добавлено через 1 минуту
evgr, под "реализуйте на своё усмотрение" я понимаю не "реализуйте" а "можете реализовать как Вам вздумается", т.е. это не попытка взять на слабо, а просто пример.

@easybudda · 06.03.2015, 11:44

evgr, очень хорошее предложение!
И вообще, друзья, старайтесь поменьше эмоций проявлять, и с оценками собеседников поаккуратнее...

GREGOR_812 · 06.03.2015, 12:44

Не по теме:

А по поводу оптимизации рекурсии почитать можно что-нибудь? Авторы, названия книг интересуют

@castorsky · 06.03.2015, 13:01

начните с вики

@Ferrari F1 · 21.04.2016, 23:50

C++
1
2
3
4
unsigned long long a(34), b(27); // а должно быть больше b
while (a % b)
  swap(a %= b, b);
cout << b << endl;

@TheCalligrapher · 22.04.2016, 03:28

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

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

C
1
2
3
4
5
int gcd( int a, int b )
{
  while( b^=a^=b^=a%=b );
  return a;
}

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

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

Во-вторых, такой вариант построен на предположении, что цепочка xor является наиболее эффективным способом обмена двух целочисленных переменных, что также не верно.

@Ferrari F1 · 22.04.2016, 12:50

Программка медленнее, но зато алгоритм другой. Все зависит от кол-ва простых чисел в векторе.

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <vector>
#include <cmath>
#include <windows.h>
 
using namespace std;
 
vector<unsigned> getDividers(unsigned value)
{
    static vector<unsigned> numbers =
    {
        2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
        43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
    };
    vector<unsigned> temp(numbers[numbers.size() - 1]);
    int i(0);
    for (; value / numbers[i];)
        if (!(value % numbers[i]))
            value /= numbers[i], ++temp[numbers[i]];
        else
            ++i;
    temp.erase(temp.begin() + numbers[i] + 1, temp.end());
    return temp;
}
 
unsigned findGCD(const vector<unsigned>& value1,
    const vector<unsigned>& value2)
{
    unsigned gcd(1), count(min(value1.size(), value2.size()));
    for (unsigned i(2); i < count; i++)
        if (value1[i] && value2[i])
            gcd *= static_cast<unsigned>(pow(i, min(value1[i], value2[i])));
    return gcd;
}
 
int main(void)
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    unsigned a(1260), b(245);
    vector<vector<unsigned>> dividers =
    {
        getDividers(a), getDividers(b)
    };
    cout << findGCD(dividers[0], dividers[1]) << endl;
    system("pause");
    return 0;
}

@easybudda · 22.04.2016, 15:17

Сообщение от Ferrari F1

но зато алгоритм другой

Да и ветка - не С++, будьте внимательнее.

@TheCalligrapher · 22.04.2016, 20:42

Сообщение от Ferrari F1

Программка медленнее, но зато алгоритм другой. Все зависит от кол-ва простых чисел в векторе.

О, да, разумеется, зависит! Программа просто тупо вылетает за размер вектора и падает, если ни одно из чисел в векторе не делит входное число. Как это должно вообще работать в финальном варианте? Вы предлагаете заранее заполнить вектор простыми числами вплоть до корня из UINT_MAX?

@Ferrari F1 · 22.04.2016, 21:00

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

ValeryS · 22.04.2016, 22:01

Сообщение от Ferrari F1

а простые числа можно, например, запихнуть в файл.

и что это быстро?

Сообщение от Ferrari F1

главное - продемонстрировать другой подход к решению задачи!

я тут вижу тупой перебор

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

заполнить вектор простыми числами вплоть до корня из UINT_MAX?

а если числа будут хотя бы 64 бита, я уж не говорю о большем размере, какой будет размер файла?

@DumkinVD · 08.12.2016, 19:18

C++
1
2
3
int euclidean(int a, int b) {
    return b == 0 ? a : euclidean(b, a % b);
}

Новые блоги и статьи Все статьи Все блоги /
Жизня: рисунок укладки багажа, сделанный клодом anaschu 21.08.2026 Сделал 15 снимков, он по снимкам сделал схему.	Был там один разговор по поводу свободы в материальном мире. kumehtar 19.08.2026 Суть: рассматривается живое существо, оказавшееся внутри довольно странной системы (этого мира) и пытающееся обустроить в ней свой кусок пространства. Жизнь действительно предъявляет каждому. . .	Когда логика программы не спасает от человеческих ошибок Maks 18.08.2026 В последнее время всё чаще и чаще сталкиваюсь с таким явлением, как абсолютная невнимательность (или глупость) пользователей. Проявляется это чаще всего на работе в коллективе. Допустим, человек с. . .	Лето уходит kumehtar 17.08.2026
Мысли в слух kumehtar 17.08.2026 Забавно, насколько сейчас стала доступна информация. Например о магии, духовном развитии, медитациях, и других подобных направлениях, ранее зачастую тайных, передаваемых от учителя к ученику. Хотя. . .	Перемещение строк из ТЧ в другой документ с учетом текущего пробега Maks 17.08.2026 Реализация из решения ниже выполнена на примере нетипового документа "Автозапчасти", с ТЧ "Шины". За основу взят алгоритм отсюда: https:/ / www. cyberforum. ru/ blogs/ 359708/ 10838. html Задача: . . .	Саморегулирующийся социальный контракт для сервера cross-section. Hrethgir 14.08.2026 С кодом конечно таких глубоких размышлений пока не было, впрочем я уже привык к алгоритмизации. Суть предмета записи: снова в диалоге с нейросетью (я взял пока себе ник для учётки админа - Rector). . . .	Часы электронные Uhbif79 12.08.2026 Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .

GREGOR_812 28 / 28 / 5 Регистрация: 23.04.2014 Сообщений: 130
	05.03.2015, 16:20
	evgr, Не по теме: ко мне можно на ты Спасибо, попробую сегодня вечерком протестить на разных числах 0

@evgr 117 / 33 / 14 Регистрация: 13.02.2015 Сообщений: 795
	06.03.2015, 08:45
	castorsky, а ещё было бы неплохо понимать, что вы пишите. А пишите вы, судя по всему, как Бог на душу положит. "Ааа, зачем мне вообще нужна оптимизация? Компилятор же всё сам за меня сделает!" - думаете вы. А потом, что дизассемблируете ваш экзешник и смотрите, действительно ли компилятор всё оптимизировал? Даже если так, оно вам надо? Не проще сразу писать нормальный код, чем приобретать себе лишнюю головную боль? 0

@easybudda Модератор 12843 / 7592 / 1766 Регистрация: 25.07.2009 Сообщений: 13,981
	06.03.2015, 11:44
	evgr, очень хорошее предложение! И вообще, друзья, старайтесь поменьше эмоций проявлять, и с оценками собеседников поаккуратнее... 1

GREGOR_812
	06.03.2015, 12:44
	Не по теме: А по поводу оптимизации рекурсии почитать можно что-нибудь? Авторы, названия книг интересуют 0

@castorsky 1978 / 1082 / 87 Регистрация: 29.11.2013 Сообщений: 3,353
	06.03.2015, 13:01
	начните с вики 0

@Ferrari F1 807 / 534 / 158 Регистрация: 27.01.2015 Сообщений: 3,017 Записей в блоге: 1
	22.04.2016, 21:00
	TheCalligrapher, главное - продемонстрировать другой подход к решению задачи! код писался ради идеи, а не для рабочего пользования. а простые числа можно, например, запихнуть в файл. Своеобразная бд простых чисел получится. 0