You get a bonus - 1 coin for daily activity. Now you have 1 coin

Binary algorithm for calculating gcd

Lecture



The binary algorithm for computing GCD, as the name implies, finds the greatest common divisor, namely GCD of two integers. In efficiency, this algorithm is superior to the Euclidean method, which is associated with the use of shifts, that is, division by a power of 2, in our case by 2. It is easier to divide (multiply) by 2, 4, 8, etc., than any other number. But at the same time, the binary algorithm is inferior to the Euclidean algorithm in the simplicity of implementation. For further assimilation of the material, one should become familiar with the properties that the GCD has of two numbers A and B. One does not need all the properties, but only the following three identities:

  1. NOD (2A, 2B) = 2NOD (A, B)
  2. GCD (2A, 2B + 1) = GCD (A, 2B + 1)
  3. GCD (-A, B) = GCD (A, B)

Now consider the stages of the algorithm. They are based on the properties of the greatest common divisor.

  1. until A and Simultaneously equal to zero, perform
    • if A and B are even numbers, then step by step (commensurately) replace each of them with half of the real value (A ← A / 2, B ← B / 2) until at least one of the numbers A or B becomes odd;

Here you will have to acquire a variable that will calculate the "disproportion" resulting from the division. Call it k and equalize 1; while A and B are halved, it should be doubled (k ← k * 2).

    • if A is even and B is odd, then replace A with a half eigenvalue until A becomes an odd number;
    • if B is even and A is odd, then replace B with half eigenvalue until B becomes an odd number;
    • if A≥B, then replace A with difference A and B, otherwise B replace with difference B and A;
  1. after leaving point 1, it remains as a result to return the product B by k: NOD (A, B) = B * k.

In the program listing, the actions described above will be carried out using the following instructions. The first numbered item corresponds to a common outer cycle, which is executed under the condition that the numbers A and B are not equal to zero at the same time. It contains three independent cycles (1, 2 and 3 marked points), as well as a conditional operator in full form (clause 4). Numbered item 2 corresponds to the usual return of the resulting value, i.e. the desired GCD.

C ++ program code:

one
2
3
four
five
6
7
eight
9
ten
eleven
12
13
14
15
sixteen
17
18
nineteen
20
21
22
23
24
25
26
27
28
29
thirty
31
#include "stdafx.h"
#include <iostream>
using namespace std;
// binary algorithm for calculating gcd
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;
}
// main function
void main ()
{
setlocale (LC_ALL, "Rus");
int A, B;
cout << "A>"; cin >> A;
cout << "B>"; cin >> B;
cout << "NOD (" << A << "," << B << ") =" << NOD (A, B);
system ("pause >> void");
}

Pascal program code:

one
2
3
four
five
6
7
eight
9
ten
eleven
12
13
14
15
sixteen
17
18
nineteen
20
21
22
23
24
25
26
27
28
program BinaryNOD;
uses crt;
var A, B: integer;
{binary algorithm for calculating gcd}
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: = AB else B: = BA;
end;
NOD: = B * k;
end;
{main program block}
begin
write ('A>'); read (A);
write ('b>'); read (B);
write ('GCD (', A, ',', B, '):', NOD (A, B));
end.

An interesting fact is that the algorithm was already known in China of the 1st century AD. e., but the year of its publication was only 1967, when an Israeli programmer and physicist Joseph Stein published an algorithm. In view of this, there is an alternative name for the method, the Stein algorithm.

created: 2014-11-30
updated: 2021-03-13
132643



Rating 9 of 10. count vote: 2
Are you satisfied?:



Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Algorithms

Terms: Algorithms