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

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

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

НОД(2A, 2B) = 2НОД(AB)
НОД(2A, 2B+1) = НОД(A, 2B+1)
НОД(-AB) = НОД(AB)

Теперь рассмотрим этапы работы алгоритма. Они основываются на приведенных свойствах наибольшего общего делителя.

  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.
  3. после выхода из 2-ого пункта, остается вернуть в качестве результата произведение B и k: НОД(AB)=B*k.

Код программы на C++:

Код программы на Pascal:

Интересен тот факт, что алгоритм был известен еще в Китае 1-го века н. э., но годом его обнародования оказался лишь 1967, когда израильский программист и физик Джозеф Стейн опубликовал алгоритм. Ввиду этого встречается альтернативное название метода – алгоритм Стейна.


Похожие записи:

Оставить комментарий

Ваш e-mail не будет опубликован. Обязательные поля отмечены *