Меню
Главная
Случайная статья
Настройки
|
Бинарный алгоритм Евклида — метод нахождения наибольшего общего делителя двух целых чисел. Данный алгоритм «быстрее» обычного алгоритма Евклида, так как вместо медленных операций деления и умножения используются сдвиги[1]. Но это преимущество в скорости теряется с увеличением разницы между целыми числами более чем на несколько порядков, в результате чего число итераций вычитания (см. шаги 6, 7 в разделе Алгоритм) может многократно превышать число итераций обычного алгоритма, использующего сравнение по модулю. То есть скорость бинарных сдвигов даёт эффект только для чисел, близких друг к другу.
Возможно, алгоритм был известен ещё в Китае I века[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; НОД(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);
Так как алгоритм является хвостовой рекурсией, то рекурсию можно заменить итерацией.
Существует также бинарная версия обобщенного алгоритма Евклида, описанная в книге Д. Кнута[3], а также в книге Василенко О. Н. «Теоретико-числовые методы в криптографии», с. 300.
Сложность
Алгоритм требует O(n) шагов, где n — количество битов в большем из двух чисел (u и v), так как каждые два шага уменьшают хотя бы один из операндов как минимум вдвое. Каждый шаг включает только несколько арифметических операций (O(1) с небольшой константой); при работе с числами размером в машинное слово, каждая арифметическая операция переводится в одну машинную операцию, поэтому количество машинных операций имеет порядок n, то есть log(max(u, v)).
Для произвольных чисел асимптотическая сложность этого алгоритма составляет O(n)[4], так как каждая арифметическая операция (вычитание и битовый сдвиг) над произвольно большими целыми числами включает линейное число машинных операций (одну на каждое слово в двоичном представлении чисел). Это ограничение снижается до O(n / log n), предполагая, что (входные) числа могут быть представлены в памяти (абстрактной) машины, то есть слова машины могут представлять размер каждого числа.
Таким образом, вычислительная сложность совпадает с алгоритмом Евклида, хотя более точный анализ, проведенный Ахави и Валле, показал, что двоичный алгоритм нахождения НОД использует примерно на 60% меньше битовых операций.[5]
Примечания
- Brent, Richard P. (2000), Twenty years' analysis of the Binary Euclidean Algorithm, Millenial Perspectives in Computer Science: Proceedings of the 1999 Oxford-Microsoft Symposium in honour of Professor Sir Antony Hoare, Palgrave, NY: 41–53, Архивировано 15 апреля 2012, Дата обращения: 11 апреля 2017 Источник . Дата обращения: 11 апреля 2017. Архивировано 15 апреля 2012 года. proceedings edited by J. Davies, A. W. Roscoe and J. Woodcock.
-
- Дональд Кнут «Искусство программирования» п. 4.5.2 задача 39
- GNU MP 6.1.2: Binary GCD . Дата обращения: 15 июля 2023. Архивировано 5 ноября 2018 года.
-
См. также
Литература- Виноградов И. М. Основы теории чисел. М.-Л.: Гос. изд. технико-теоретической литературы, 1952, 180 с.
Ссылки
|
|