Бинарный алгоритм нахождения НОД

Бинарный алгоритм нахождения НОД

Бинарный алгоритм нахождения НОД

Бинарный алгоритм Евклида — метод нахождения наибольшего общего делителя двух целых чисел, основанный на использовании следующих свойств НОД:

  • НОД(2m, 2n) = 2 НОД(m, n),
  • НОД(2m, 2n+1) = НОД(m, 2n+1),
  • НОД(-m, n) = НОД(m, n)

Содержание

Алгоритм

  1. НОД(0, n) = n; НОД(m, 0) = m; НОД(m, m) = m;
  2. НОД(1, n) = 1; НОД(m, 1) = 1;
  3. Если m, n чётные, то НОД(m, n) = 2*НОД(m/2, n/2);
  4. Если m чётное, n нечётное, то НОД(m, n) = НОД(m/2, n);
  5. Если n чётное, m нечётное, то НОД(m, n) = НОД(m, n/2);
  6. Если m, n нечётные, то НОД(m, n) = НОД(n, |m - n|).

Так как алгоритм является Хвостовой рекурсией, то рекурсию можно заменить итерацией.

См. также

Литература

Ссылки

Логотип Викиучебника
Имеется викиучебник по теме
«Примеры реализации алгоритма Евклида»

Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Полезное


Смотреть что такое "Бинарный алгоритм нахождения НОД" в других словарях:

  • Бинарный алгоритм вычисления НОД — Бинарный алгоритм Евклида  метод нахождения наибольшего общего делителя двух целых чисел. Данный алгоритм быстрее обычного алгоритма Евклида, т.к. вместо медленных операций деления и умножения используются сдвиги. Алгоритм был известен еще в …   Википедия

  • Алгоритм Евклида — Имеется викиучебник по теме « …   Википедия

  • Алгоритм Шенкса — (англ. Baby step giant step; также называемый алгоритм больших и малых шагов)  в теории групп, детерминированный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Для модулей специального вида данный… …   Википедия

  • Программируемые алгоритмы —       Служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавл …   Википедия

  • Наибольший общий делитель — Наибольшим общим делителем (НОД) для двух целых чисел m и n называется наибольший из их общих делителей.[1] Пример: для чисел 70 и 105 наибольший общий делитель равен 35. Наибольший общий делитель существует и однозначно определён, если хотя бы… …   Википедия

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»