Бинарный алгоритм вычисления НОД (>nugjudw glikjnmb fdcnvlyunx UK:)

Бинарный алгоритм Евклида — метод нахождения наибольшего общего делителя двух целых чисел. Данный алгоритм «быстрее» обычного алгоритма Евклида, так как вместо медленных операций деления и умножения используются сдвиги^[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; НОД(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.
↑ Knuth, Donald (1998), Seminumerical Algorithms, The Art of Computer Programming, vol. 2 (3rd ed.), Addison-Wesley, ISBN 0-201-89684-2
↑ Дональд Кнут «Искусство программирования» п. 4.5.2 задача 39
↑ GNU MP 6.1.2: Binary GCD (неопр.). Дата обращения: 15 июля 2023. Архивировано 5 ноября 2018 года.
↑ Akhavi, Ali; Vallée, Brigitte (2000), "Average Bit-Complexity of Euclidean Algorithms", Proceedings ICALP'00, Lecture Notes Computer Science 1853: 373—387, CiteSeerX 10.1.1.42.7616, Архивировано из оригинала 29 августа 2017, Дата обращения: 15 июля 2023