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

Лекция

Привет, сегодня поговорим про бинарный алгоритм вычисления нод, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое бинарный алгоритм вычисления нод , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.

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

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

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

пока A и Bодновременно не равны нулю, выполнять

если A и B – четные числа, то пошагово (соразмерно) заменять каждое из них половиной настоящего значения (A←A/2, B←B/2) до тех пор, пока хотя бы одно из чисел A или B не станет нечетным;

Здесь придется обзавестись переменной, которая будет подсчитывать «несоразмерность», полученную в результате деления. Назовем ее k и прировняем 1; в то время как A и B сокращаются вдвое, она должна увеличиваться вдвое (k←k*2).

если A – четное, а B – нечетное, то заменять A половинной собственного значения до тех пор, пока A не станет нечетным числом;
если B – четное, а A – нечетное, то заменять B половинной собственного значения до тех пор, пока B не станет нечетным числом;
если A≥B, то заменить A разностью A и B, иначе B заменить разностью B и A;

после выхода из пункта 1, остается в качестве результата вернуть произведение B на k: НОД(A, B)=B*k.

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

Код программы на 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, когда израильский программист и физик Джозеф Стейн опубликовал алгоритм. Ввиду этого встречается альтернативное название метода – алгоритм Стейна.

На этом все! Теперь вы знаете все про бинарный алгоритм вычисления нод, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое бинарный алгоритм вычисления нод и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов

Из статьи мы узнали кратко, но содержательно про бинарный алгоритм вычисления нод

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

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

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

Комментарии

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

Алгоритмы и теория алгоритмов

Термины: Алгоритмы и теория алгоритмов