Самый быстрый алгоритм Евклида вычисления НОД - C (СИ)
Формулировка задачи:
Заинтересовал вопрос о различных реализациях алгоритма Евклида для неотрицательных целых чисел. Ниже привожу алгоритмы, собственноручно написанные, исходя из теоретического материала. Каждый алгоритм можно модифицировать в ту или иную сторону.
Считается, что бинарный алгоритм работает быстрее, но мои тесты показывают, что два первых алгоритма работают быстрее бинарного. Может ли кто перепроверить на скорость на своих компиляторах, а то очень интересно и не видится никаких преимуществ бинарного алгоритма.
Еще один бинарный алгоритм, но он самый медленный из всех предыдущих.
//обычный алгоритм Евклида через остатки long Nod(long a, long b) { while (a && b) if (a >= b) a %= b; else b %= a; return a | b; }
// Алгоритм Евклида через разности long Nod(long a, long b) { while (a && b) if (a >= b) a -= b; else b -= a; return a | b; }
// Бинарный алгоритм Евклида 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); }
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); }
Решение задачи: «Самый быстрый алгоритм Евклида вычисления НОД»
textual
Листинг программы
#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; }
Объяснение кода листинга программы
В данном коде представлен самый быстрый алгоритм Евклида вычисления НОД (наибольшего общего делителя) двух целых чисел. Алгоритм основан на рекурсивном применении евклидова алгоритма к остатку от деления.
- В первой строке объявляется шаблон структуры
gcd
, который принимает два целых числаx
иy
в качестве параметров. - В блоке
private
структурыgcd
объявляются две константы_value1
и_value2
, которые инициализируются значениямиy
иx % y
соответственно.%
- это оператор взятия остатка от деления. - Далее, используя оператор
static_cast
, мы приводим значения_value1
и_value2
к типуint
для обеспечения корректной работы алгоритма. - Затем мы определяем новый шаблон
next_step_type
, который будет использоваться в рекурсивном вызове функцииgcd
. - В блоке
public
структурыgcd
объявляется константаvalue
, которая инициализируется значениемnext_step_type::value
, т.е. результатом рекурсивного вызова функцииgcd
с новыми значениями_value1
и_value2
. - В конце кода в функции
main
выводится значениеgcd<2344, 5432>::value
на экран. - В структуре
gcd
также присутствует специальный случай для вычисления НОД двух чисел, когда одно из них равно нулю. В этом случае возвращается второе число. Это сделано для корректной работы алгоритма. Список вызовов функций и значения переменных в данном коде: gcd<2344, 5432>::value
- вызов функцииgcd
с аргументами2344
и5432
, результат выводится на экран.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д