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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Бинарный алгоритм Евклида — метод нахождения наибольшего общего делителя двух целых чисел. Данный алгоритм быстрее обычного алгоритма Евклида, т.к. вместо медленных операций деления и умножения используются сдвиги[1]. Возможно алгоритм был известен еще в Китае 1-го века[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;
  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) = НОД((n-m)/2, m);
  7. Если m, n нечётные и n < m, то НОД(m, n) = НОД((m-n)/2, n);

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

Существует также бинарная версия обобщенного алгоритма Евклида, описанная в книге Д. Кнута[3], а так же в книге Василенко О.Н. "Теоретико-числовые методы в криптографии", с. 300.

Примечания[править | править вики-текст]

  1. Brent, Richard P., "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, <http://wwwmaths.anu.edu.au/~brent/pub/pub183.html>  proceedings edited by J. Davies, A. W. Roscoe and J. Woodcock.
  2. Knuth, Donald (1998), Seminumerical Algorithms, vol. 2 (3rd ed.), The Art of Computer Programming, Addison-Wesley, ISBN 0-201-89684-2 
  3. Дональд Кнут "Искусство программирования" п. 4.5.2 задача 39

См. также[править | править вики-текст]

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]