«

»

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

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

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

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

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#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:

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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, когда израильский программист и физик Джозеф Стейн опубликовал алгоритм. Ввиду этого встречается альтернативное название метода – алгоритм Стейна.

Добавить комментарий

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

Вы можете использовать эти теги HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Проверка на человечность *