Binary algorithm for calculating gcd

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;

2. 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:

Pascal program code:

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.