Last Updated:

Binary algorithm for calculating the NODE.

The binary algorithm for calculating the NOD, as the name implies, finds the largest common divisor, namely the NOD of two integers. In efficiency, this algorithm is superior to the Euclid method, which is associated with the use of shifts, that is, the operations of dividing by the degree of 2, in our case by 2.

 

It is easier for a computer to divide (multiply) by 2, 4, 8, etc., than by any other number. But at the same time, the binary algorithm is inferior to euclid's algorithm in simplicity of implementation. For further assimilation of the material, you should familiarize yourself with the properties possessed by the NOD of the two numbers A and B. Not all properties will be required, but only the following three identities:

 

NOD(2A, 2B) = 2NOD(AB)
NOD(2A, 2B+1) = NODE(A, 2B+1)
RHODE(-AB) = RHAD(AB)


Now let's consider the stages of the algorithm. They are based on the given properties of the largest common divisor.

 

  1. initialize the variable k with the value 1. Its task is to calculate the "disproportionality" obtained as a result of division. While A and Bare halved, it will double;
  2. as long as A and B are not simultaneously zero, we execute
    • if A and B are even numbers, then divide each of them in two: AA/2, BB/2, and double kkk*2, until at least one of the numbers A or B becomes odd;
    • if A is even and B is odd, then we divisible A as long as division without residue is possible;
    • if B is even and A is odd, then we divide B as long as division is possible without residue;
    • if AB, then replace A with the difference A and B, otherwise B will replace B with the difference Band A.
  3. after exiting the 2nd point, it remains to return as a result the product B and k: NOD(AB) = Bk.

The code of the program in C++:

The code of the program in Pascal:

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