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

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

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

1. инициализируем переменную k значением 1. Ее задача – подсчитывать «несоразмерность», полученную в результате деления. В то время как A и Bсокращаются вдвое, она будет увеличиваться вдвое;
2. пока 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.
3. после выхода из 2-ого пункта, остается вернуть в качестве результата произведение B и k: НОД(A, B)=B*k.

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

#include "stdafx.h"
#include <iostream>
using namespace std;
//бинарный алгоритм вычисления НОД
int NOD(int A, int B)
{
int k=1;
while ((A!=0) && (B!=0))
{
while ((A%2==0) && (B%2==0))
{
A/=2;
B/=2;
k*=2;
}
while (A%2==0) A/=2;
while (B%2==0) B/=2;
if (A>=B) A-=B; else B-=A;
}
return B*k;
}
//главная функция
void main()
{
setlocale(LC_ALL,"Rus");
int A, B;
cout<<"A > "; cin>>A;
cout<<"B > "; cin>>B;
cout<<"НОД("<<A<<", "<<B<<")="<<NOD(A, B);
system("pause>>void");
}

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

program BinaryNOD;
uses crt;
var A, B: integer;
{бинарный алгоритм вычисления НОД}
function NOD(A, B: integer): integer;
var k: integer;
begin
k:=1;
while (A<>0) and (B<>0) do
begin
while (A mod 2=0) and (B mod 2=0) do
begin
A:=A div 2;
B:=B div 2;
k:=k*2;
end;
while A mod 2=0 do A:=A div 2;
while B mod 2=0 do B:=B div 2;
if A>=B then A:=A-B else B:=B-A;
end;
NOD:=B*k;
end;
{основной блок программы}
begin
write('A > '); read(A);
write('B > '); read(B);
write('НОД(', A, ', ', B, '): ', NOD(A, B));
end.

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