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

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

Он иллюстрируется следующей программой:

1.Определим матрицу 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 кольца Z_n обратим тогда и только тогда, когда НОД(a,n)=1. То есть ответ есть не всегда. Из определения обратного элемента прямо следует алгоритм.

Бинарный алгоритм вычисления НОД, как понятно из названия, находит наибольший общий делитель, а именно НОД двух целых чисел. В эффективности данный алгоритм превосходит метод Евклида, что связано с использованием сдвигов, то есть операций деления на степень 2-ки, в нашем случае на 2.

Компьютеру проще поделить (умножить) на 2, 4, 8 и т.д., чем на какое-либо другое число. Но в тоже время бинарный алгоритм уступает алгоритму Евклида в простоте реализации. Для дальнейшего усвоения материала следует ознакомиться со свойствами, которыми обладает НОД двух чисел A и B. Потребуются не все свойства, а только три следующих тождества:

1. инициализируем переменную k значением 1. Ее задача – подсчитывать «несоразмерность», полученную в результате деления. В то время как A и Bсокращаются вдвое, она будет увеличиваться вдвое;
2. пока A и B одновременно не равны нулю, выполняем
3. если A и B – четные числа, то делим надвое каждое из них: A←A/2, B←B/2, а k увеличивать вдвое: k←k*2, до тех пор, пока хотя бы одно из чисел A или B не станет нечетным;
4. если A – четное, а B – нечетное, то делим A, пока возможно деление без остатка;
5. если B – четное, а A – нечетное, то делим B, пока возможно деление без остатка;
6. если A≥B, то заменим A разностью A и B, иначе B заменим разностью Bи A.
7. после выхода из 2-ого пункта, остается вернуть в качестве результата произведение B и k: НОД(A, B)=B*k.