Бинарный алгоритм Евклида — метод нахождения наибольшего общего делителя двух целых чисел. Данный алгоритм быстрее обычного алгоритма Евклида, т.к. вместо медленных операций деления и умножения используются сдвиги [1] . Возможно, алгоритм был известен еще в Китае 1-го века [2] , но опубликован был лишь в 1967 году израильским физиком и программистом Джозефом Стайном. Он основан на использовании следующих свойств НОД:
- НОД(2m, 2n) = 2 НОД(m, n),
- НОД(2m, 2n+1) = НОД(m, 2n+1),
- НОД(-m, n) = НОД(m, n)
Этот алгоритм использует соотношения для НОД:
НОД(2*a, 2*b) = 2*НОД(a,b)
НОД(2*a, b) = НОД(a,b) при нечетном b,
Он иллюстрируется следующей программой:
Алгоритм решения уравнения ax+by = 1.
1.Определим матрицу E:
E = |
2. Вычислим r — остаток от деления числа a на b, a=bq+r, 0 E *
5. Заменим пару чисел (a,b) на (b,r) и перейдем к шагу 2.
Расширенный алгоритм Евклида.
Алгоритм Евклида можно расширить так, что он не только даст НОД(a,b)=d, но и найдет целые числа x и y, такие что ax + by = d.
Псевдокод.
Исходник на Си.
Алгоритм работает за O(log 2 n) операций.
Нахождение обратного элемента по модулю
Для начала заметим, что элемент a кольца Zn обратим тогда и только тогда, когда НОД(a,n)=1. То есть ответ есть не всегда. Из определения обратного элемента прямо следует алгоритм.
Бинарный алгоритм вычисления НОД, как понятно из названия, находит наибольший общий делитель, а именно НОД двух целых чисел. В эффективности данный алгоритм превосходит метод Евклида, что связано с использованием сдвигов, то есть операций деления на степень 2-ки, в нашем случае на 2.
Компьютеру проще поделить (умножить) на 2, 4, 8 и т.д., чем на какое-либо другое число. Но в тоже время бинарный алгоритм уступает алгоритму Евклида в простоте реализации. Для дальнейшего усвоения материала следует ознакомиться со свойствами, которыми обладает НОД двух чисел A и B. Потребуются не все свойства, а только три следующих тождества:
- инициализируем переменную k значением 1. Ее задача – подсчитывать «несоразмерность», полученную в результате деления. В то время как A и Bсокращаются вдвое, она будет увеличиваться вдвое;
- пока A и B одновременно не равны нулю, выполняем
- если A и B – четные числа, то делим надвое каждое из них: A←A/2, B←B/2, а k увеличивать вдвое: k←k*2, до тех пор, пока хотя бы одно из чисел A или B не станет нечетным;
- если A – четное, а B – нечетное, то делим A, пока возможно деление без остатка;
- если B – четное, а A – нечетное, то делим B, пока возможно деление без остатка;
- если A≥B, то заменим A разностью A и B, иначе B заменим разностью Bи A.
- после выхода из 2-ого пункта, остается вернуть в качестве результата произведение B и k: НОД(A, B)=B*k.