WikiSort.ru - Не сортированное

Бинарный алгоритм Евклида — метод нахождения наибольшего общего делителя двух целых чисел. Данный алгоритм быстрее обычного алгоритма Евклида, т.к. вместо медленных операций деления и умножения используются сдвиги^[1]. Возможно, алгоритм был известен еще в Китае 1-го века^[2], но опубликован был лишь в 1967 году израильским физиком и программистом Джозефом Стайном. Он основан на использовании следующих свойств НОД:

• НОД(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 нечётные и n > m, то НОД(m, n) = НОД((n-m)/2, m);
7. Если m, n нечётные и n < m, то НОД(m, n) = НОД((m-n)/2, n);

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

Существует также бинарная версия обобщенного алгоритма Евклида, описанная в книге Д. Кнута^[3], а также в книге Василенко О.Н. "Теоретико-числовые методы в криптографии", с. 300.

Примечания

См. также

• Алгоритм Евклида
• Наибольший общий делитель

Литература

• Виноградов И. М. Основы теории чисел. М.-Л.: Гос. изд. технико-теоретической литературы, 1952, 180 с.

Ссылки

Имеется викиучебник по теме
«Бинарный алгоритм вычисления НОД»

• Бинарный алгоритм Евклида