Бинарный алгоритм Евклида — метод нахождения наибольшего общего делителя двух целых чисел. Данный алгоритм «быстрее» обычного алгоритма Евклида, так как вместо медленных операций деления и умножения используются сдвиги proceedings edited by J. Davies, A. W. Roscoe and J. Woodcock.. Но это преимущество в скорости теряется с увеличением разницы между целыми числами более чем на несколько порядков, в результате чего число итераций вычитания (см. шаги 6, 7 в разделе Алгоритм) может многократно превышать число итераций обычного алгоритма, использующего сравнение по модулю. То есть скорость бинарных сдвигов даёт эффект только для чисел, близких друг к другу.

Возможно, алгоритм был известен ещё в Китае I века, но опубликован был лишь в 1967 году израильским физиком и программистом Джозефом Стайном. Он основан на использовании следующих свойств НОД: НОД(2m, 2n) = 2 НОД(m, n), НОД(2m, 2n+1) = НОД(m, 2n+1), НОД(-m, n) = НОД(m, n)

Алгоритм НОД(0, n) = n; НОД(m, 0) = m; НОД(m, m) = m; НОД(n, n) = n; НОД(1, n) = 1; НОД(m, 1) = 1; Если m, n чётные, то НОД(m, n) = 2*НОД(m/2, n/2); Если m чётное, n нечётное, то НОД(m, n) = НОД(m/2, n); Если n чётное, m нечётное, то НОД(m, n) = НОД(m, n/2); Если m, n нечётные и n > m, то НОД(m, n) = НОД(m, (n-m)/2); Если m, n нечётные и n < m, то НОД(m, n) = НОД((m-n)/2, n);

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

Существует также бинарная версия обобщенного алгоритма Евклида, описанная в книге Д. КнутаДональд Кнут «Искусство программирования» п. 4.5.2 задача 39, а также в книге Василенко О. Н. «Теоретико-числовые методы в криптографии», с. 300.

Сложность Алгоритм требует O(n) шагов, где n — количество битов в большем из двух чисел (u и v), так как каждые два шага уменьшают хотя бы один из операндов как минимум вдвое. Каждый шаг включает только несколько арифметических операций (O(1) с небольшой константой); при работе с числами размером в машинное слово, каждая арифметическая операция переводится в одну машинную операцию, поэтому количество машинных операций имеет порядок n, то есть log₂(max(u, v)).

Для произвольных чисел асимптотическая сложность этого алгоритма составляет O(n²), так как каждая арифметическая операция (вычитание и битовый сдвиг) над произвольно большими целыми числами включает линейное число машинных операций (одну на каждое слово в двоичном представлении чисел). Это ограничение снижается до O(n² / log₂ n), предполагая, что (входные) числа могут быть представлены в памяти (абстрактной) машины, то есть слова машины могут представлять размер каждого числа.

Таким образом, вычислительная сложность совпадает с алгоритмом Евклида, хотя более точный анализ, проведенный Ахави и Валле, показал, что двоичный алгоритм нахождения НОД использует примерно на 60% меньше битовых операций.

Примечания

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

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

Ссылки

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

Категория:Теоретико-числовые алгоритмы