Русская Википедия:Бинарный алгоритм вычисления НОД
Бинарный алгоритм Евклида — метод нахождения наибольшего общего делителя двух целых чисел. Данный алгоритм «быстрее» обычного алгоритма Евклида, так как вместо медленных операций деления и умножения используются сдвиги[1]. Но это преимущество в скорости теряется с увеличением разницы между целыми числами более чем на несколько порядков, в результате чего число итераций вычитания (см. шаги 6, 7 в разделе Алгоритм) может многократно превышать число итераций обычного алгоритма, использующего сравнение по модулю. То есть скорость бинарных сдвигов дает эффект только для чисел близких друг другу.
Возможно, алгоритм был известен еще в Китае 1-го века[2], но опубликован был лишь в 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;
- НОД(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);
Так как алгоритм является хвостовой рекурсией, то рекурсию можно заменить итерацией.
Существует также бинарная версия обобщенного алгоритма Евклида, описанная в книге Д. Кнута[3], а также в книге Василенко О. Н. «Теоретико-числовые методы в криптографии», с. 300.
Сложность
Алгоритм требует O(n) шагов, где n — количество битов в большем из двух чисел (u и v), так как каждые два шага уменьшают хотя бы один из операндов как минимум вдвое. Каждый шаг включает только несколько арифметических операций (O(1) с небольшой константой); при работе с числами размером в машинное слово, каждая арифметическая операция переводится в одну машинную операцию, поэтому количество машинных операций имеет порядок n, то есть log₂(max(u, v)).
Для произвольных чисел асимптотическая сложность этого алгоритма составляет O(n²)[4], так как каждая арифметическая операция (вычитание и битовый сдвиг) над произвольно большими целыми числами включает линейное число машинных операций (одну на каждое слово в двоичном представлении чисел). Это ограничение снижается до O(n² / log₂ n), предполагая, что (входные) числа могут быть представлены в памяти (абстрактной) машины, то есть слова машины могут представлять размер каждого числа.
Таким образом, вычислительная сложность совпадает с алгоритмом Евклида, хотя более точный анализ, проведенный Ахави и Валле, показал, что двоичный алгоритм нахождения НОД использует примерно на 60% меньше битовых операций.[5]
Примечания
См. также
Литература
- Виноградов И. М. Основы теории чисел. М.-Л.: Гос. изд. технико-теоретической литературы, 1952, 180 с.
Ссылки
- ↑ Шаблон:Citation Шаблон:Cite web proceedings edited by J. Davies, A. W. Roscoe and J. Woodcock.
- ↑ Шаблон:Citation
- ↑ Дональд Кнут «Искусство программирования» п. 4.5.2 задача 39
- ↑ Шаблон:Cite web
- ↑ Шаблон:Citation
