Бинарный алгоритм евклида пример

Бинарный алгоритм Евклида — метод нахождения наибольшего общего делителя двух целых чисел. Данный алгоритм быстрее обычного алгоритма Евклида, т.к. вместо медленных операций деления и умножения используются сдвиги [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. Потребуются не все свойства, а только три следующих тождества:

  1. инициализируем переменную k значением 1. Ее задача — подсчитывать «несоразмерность», полученную в результате деления. В то время как A и Bсокращаются вдвое, она будет увеличиваться вдвое;
  2. пока A и B одновременно не равны нулю, выполняем
    • если A и B — четные числа, то делим надвое каждое из них: AA/2, BB/2, а k увеличивать вдвое: kk*2, до тех пор, пока хотя бы одно из чисел A или B не станет нечетным;
    • если A — четное, а B — нечетное, то делим A, пока возможно деление без остатка;
    • если B — четное, а A — нечетное, то делим B, пока возможно деление без остатка;
    • если AB, то заменим A разностью A и B, иначе B заменим разностью Bи A.
    • после выхода из 2-ого пункта, остается вернуть в качестве результата произведение B и k: НОД(A, B)=B*k.
    Читайте также:  Как в экселе изменить нумерацию строк