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

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

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

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

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

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

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

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

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

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

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

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

@Ferrari F1 · 22.04.2016, 12:50

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

C++

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

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

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

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

@Qwertiy 833 / 641 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	05.03.2015, 10:39	22
	Сообщение от evgr Однако имейте ввиду, что рекурсивные алгоритмы, как правило, не отличаются высокой скоростью работы. Если компилятор не решит развернуть рекурсию?) 0

@evgr 117 / 33 / 14 Регистрация: 13.02.2015 Сообщений: 793
	05.03.2015, 10:47	23
	Сообщение от Qwertiy решит развернуть рекурсию Ну тогда алгоритм несомненно перестанет быть рекурсивным. А вообще зачем писать код с рекурсией и надеяться на компилятор, если можно сразу создать алгоритм без использования рекурсии? 0

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

@castorsky 1978 / 1082 / 87 Регистрация: 29.11.2013 Сообщений: 3,353
	05.03.2015, 18:14	25
	Сообщение от evgr Ну тогда алгоритм несомненно перестанет быть рекурсивным алгоритм не может быть сначала рекурсивным, а после компиляции исходников стать не рекурсивным. Сообщение от evgr А вообще зачем писать код с рекурсией и надеяться на компилятор, если можно сразу создать алгоритм без использования рекурсии? Надо понимать что говорите. А говорите Вы откровенную, простите, чушь. Итерация - частный случай рекурсии, если что. Оптимизация рекурсии явление не новое и если компилятор этого не умеет, то стоит задуматься о целесообразности его использования. 0

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

@castorsky 1978 / 1082 / 87 Регистрация: 29.11.2013 Сообщений: 3,353
	06.03.2015, 10:36	27
	Сообщение от 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 Не проще сразу писать нормальный код Боюсь что Вы только на пороге к понимаю этих слов. 0

@evgr 117 / 33 / 14 Регистрация: 13.02.2015 Сообщений: 793
	06.03.2015, 11:09	28
	Сообщение от castorsky Вот Вам рекурсивный алгоритм Да вы пытаетесь меня втянуть в какую-то специальную олимпиаду! Смотрите, как бы вас кто-нибудь также не развёл на слабо и не заставил сделать за него что-нибудь Давайте-ка свернём эту дискуссию, если вы не против? 0

@castorsky 1978 / 1082 / 87 Регистрация: 29.11.2013 Сообщений: 3,353
	06.03.2015, 11:25	29
	Не по теме: Простейшие основы матана для Вас оленьпиада? Тут надо курить матчасть. Я указал Вам на ошибку, как человек рациональный Вы долны поразмыслить на сказанным. Сообщение от evgr Давайте-ка свернём эту дискуссию, если вы не против? ЧТД. Добавлено через 1 минуту evgr, под "реализуйте на своё усмотрение" я понимаю не "реализуйте" а "можете реализовать как Вам вздумается", т.е. это не попытка взять на слабо, а просто пример. 0

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

@easybudda Модератор 12459 / 7483 / 1754 Регистрация: 25.07.2009 Сообщений: 13,762
	22.04.2016, 15:17	36
	Сообщение от Ferrari F1 но зато алгоритм другой Да и ветка - не С++, будьте внимательнее. 0

@TheCalligrapher Вездепух 11696 / 6375 / 1724 Регистрация: 18.10.2014 Сообщений: 16,076
	22.04.2016, 20:42	37
	Сообщение от Ferrari F1 Программка медленнее, но зато алгоритм другой. Все зависит от кол-ва простых чисел в векторе. О, да, разумеется, зависит! Программа просто тупо вылетает за размер вектора и падает, если ни одно из чисел в векторе не делит входное число. Как это должно вообще работать в финальном варианте? Вы предлагаете заранее заполнить вектор простыми числами вплоть до корня из `UINT_MAX`? 0

ValeryS Модератор 8909 / 6678 / 918 Регистрация: 14.02.2011 Сообщений: 23,523
	22.04.2016, 22:01	39
	Сообщение от Ferrari F1 а простые числа можно, например, запихнуть в файл. и что это быстро? Сообщение от Ferrari F1 главное - продемонстрировать другой подход к решению задачи! я тут вижу тупой перебор Сообщение от TheCalligrapher заполнить вектор простыми числами вплоть до корня из UINT_MAX? а если числа будут хотя бы 64 бита, я уж не говорю о большем размере, какой будет размер файла? 0