Бинарный алгоритм вычисления НОД

Бинарный алгоритм Евклида — метод нахождения наибольшего общего делителя двух целых чисел. Данный алгоритм «быстрее» обычного алгоритма Евклида, так как вместо медленных операций деления и умножения используются сдвиги[1]. Но это преимущество в скорости теряется с увеличением разницы между целыми числами более чем на несколько порядков, в результате чего число итераций вычитания (см. шаги 6, 7 в разделе Алгоритм) может многократно превышать число итераций обычного алгоритма, использующего сравнение по модулю. То есть скорость бинарных сдвигов даёт эффект только для чисел, близких друг к другу.

Возможно, алгоритм был известен ещё в Китае I века[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; НОД(n, n) = n;
  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) = НОД(m, (n-m)/2);
  7. Если 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]

Примечания

  1. ↑ 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.
  2. ↑ Knuth, Donald (1998), Seminumerical Algorithms, The Art of Computer Programming, vol. 2 (3rd ed.), Addison-Wesley, ISBN 0-201-89684-2
  3. ↑ Дональд Кнут «Искусство программирования» п. 4.5.2 задача 39
  4. ↑ GNU MP 6.1.2: Binary GCD. Дата обращения: 15 июля 2023. Архивировано 5 ноября 2018 года.
  5. ↑ 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

См. также

Литература

Ссылки