Binary GCD algorithm

The Einstein's algorithm or binary Euclidean algorithm is used for efficient computation of the greatest common divisor. The algorithm was introduced in 1967 by the German Josef Stein. Donald Ervin Knuth, according to R. Silver and J. Tersian developed the algorithm in 1962, but not published it.

The algorithm uses the following calculation rules:

• If a and b are even.
• If a is even and b is odd.
• If a and b odd.

He is on Binärrechnern faster than the millennia-old Euclidean algorithm, since no time-consuming divisions (or Modulooperationen ) must be performed. There are only divisions by 2 necessary for you just the bit pattern by one to the right, for low- end push. Most processors provide for an efficient shift register. Notes:

• It should be noted that the Einstein's algorithm only works properly if unsigned integers are used. The Euclidean algorithm, however, works with unsigned integer types.
• The Einstein's algorithm is on today's computers only efficient if the integer type does not fit in a register, so multiple accesses are required for each variable. This is the case for example for 64-bit integers on a computer with 32- bit registers. Conversely, the Euclidean faster if the integer type fits completely into a register, a variable, so use a single access.

Algorithm

The variant of the algorithm described here in pseudo code essentially corresponds to that which describes Donald E. Knuth in his book The Art of Computer Programming.

STONE (a, b )    when a = 0        then return b    k 0    while A and B are even numbers        a a / 2        b b / 2        k k 1    where a is an odd number        then t -b        otherwise t a    as long as t ≠ 0        as long as t is an even number            T t / 2        when t> 0            then a t            else b -t        t a - b    return a 2k swell

• Theoretical number algorithm