Steiner's algorithm

The Steinsche algorithm or binary Euclidean algorithm provides for the efficient calculation of the greatest common divisor . The algorithm was presented in 1967 by the German Josef Stein. According to Donald E. Knuth , R. Silver and J. Tersian developed the algorithm as early as 1962, but did not publish it.

The algorithm uses the following calculation rules:

• ${\displaystyle \operatorname {ggT} (a,b)=2\operatorname {ggT} (a/2,b/2)}$if a and b are even.
• ${\displaystyle \operatorname {ggT} (a,b)=\operatorname {ggT} (a/2,b)}$if a is even and b is odd.
• ${\displaystyle \operatorname {ggT} (a,b)=\operatorname {ggT} ((a-b)/2,b)}$if a and b are odd.

It is faster on binary computers than the millennia-old Euclidean algorithm because no time-consuming divisions (or modulo operations ) have to be carried out. Only divisions by 2 are required, for which one only has to shift the bit pattern by one to the right, to the low-order end. Most processors have an efficient shift register for this .

It should be noted that Stein's algorithm only works correctly if unsigned integers are used. Negative numbers must first be converted into positive ones. The Euclidean algorithm, on the other hand, also works with signed integer types.

principle

The greatest common divisor of the two positive numbers a and b is to be determined. First a variable k is defined and the value 0 is assigned to it. Then both a and b are divided by 2 until a or b is no longer divisible by 2. With every halving, k is increased by 1.

The second part requires the additional variable t, to which the difference between a and b is assigned. All common divisor of a and b also divides t have to be, so that: . The variable c is then divided by 2 as long as it is an even number. Then a is replaced by c and t is formed anew. The algorithm is finished as soon as applies. The result is the following: . ${\displaystyle \operatorname {ggT} (a,b)=\operatorname {ggT} (a,c)=\operatorname {ggT} (b,c)}$ ${\displaystyle t=0}$ ${\displaystyle \operatorname {ggT} (a,b)=a*2^{k}}$

algorithm

The variant of the algorithm described here in pseudocode corresponds essentially to the one described by Donald E. Knuth in his work The Art of Computer Programming .

STEIN(a,b)
  wenn a = 0
      dann return b
  k  ${\displaystyle \leftarrow }$ 0
  solange a und b gerade Zahlen sind
      a  ${\displaystyle \leftarrow }$ a/2
      b  ${\displaystyle \leftarrow }$ b/2
      k  ${\displaystyle \leftarrow }$ k + 1
  wenn a eine ungerade Zahl ist
      dann t  ${\displaystyle \leftarrow }$ -b
      sonst t  ${\displaystyle \leftarrow }$ a
  solange t ≠ 0
      solange t eine gerade Zahl ist
          t  ${\displaystyle \leftarrow }$ t/2
      wenn t > 0
          dann a  ${\displaystyle \leftarrow }$ t
          sonst b  ${\displaystyle \leftarrow }$ -t
      t  ${\displaystyle \leftarrow }$ a - b
  return a  ${\displaystyle \cdot }$ 2k

Many processors nowadays have instruction sets that can determine very quickly (often in one cycle) how often an integer is divisible by two. For example, the x86 architecture has provided the instruction for this purpose since the 80386bsf . Using such an instruction it is possible to save two of the three loops of the algorithm and thus to significantly improve its runtime. The following implementation in the C programming language uses the POSIX standard function ffs(find first set) for this purpose :

#include <stdlib.h>  /* für abs() */
#include <strings.h> /* für ffs() */

int ggt(int a, int b)
{
    register int c;

    if ((a == 0) || (b == 0)) // falls eines oder beide Argumente 0 sind,
        return a | b; // ist das andere Argument oder 0 das Ergebnis

    // dies kann weggelassen werden, wenn a und b nicht negativ sein können
    a = abs(a);
    b = abs(b);

    c = ffs(a | b) - 1;
    a >>= ffs(a) - 1;

    do {
        b >>= ffs(b) - 1;
        if (a > b) {
            // vertausche Variablen, damit bei Subtraktion kein Überlauf stattfinden kann
            int temp = b;
            b = a;
            a = temp;
        }

        b -= a;
    } while (b != 0);

    return a << c;
}

An implementation for unsigned integers in x86 assembler that bsfuses:

ggt:
        mov     ecx, 4[esp]     ; Lade a
        mov     eax, 8[esp]     ; Lade b
        test    ecx, ecx        ; Vergleiche a mit 0:
        jz      done            ;  falls a gleich 0 ist das Ergebnis b

        cmp     eax, ecx        ; Vergleiche a mit b:
        je      done            ;  falls a gleich b ist das Ergebnis b

        mov     edx, eax        ; Lade b
        mov     eax, ecx        ; Lade a
        test    edx, edx        ; Vergleiche b mit 0:
        jz      done            ;  falls b gleich 0 ist das Ergebnis a

        push    ebx
        bsf     ecx, edx        ; Bestimme grösste Zweierpotenz von b
        bsf     ebx, eax        ; Bestimme grösste Zweierpotenz von a
        cmp     ebx, ecx        ; Vergleiche beide
        cmova   ebx, ecx        ;  und merke deren Minimum
        shr     edx, cl         ; Dividiere b durch grösste Zweierpotenz

next:
        bsf     ecx, eax        ; Bestimme grösste Zweierpotenz von a
        shr     eax, cl         ; Dividiere a durch grösste Zweierpotenz
        mov     ecx, edx
        cmp     edx, eax        ; Vergleiche b mit a
        cmovb   edx, eax        ;  und vertausche beide, falls b kleiner a
        cmovb   eax, ecx
        sub     edx, eax        ; Subtrahiere a von b
        jnz     next            ;  und wiederhole, bis b gleich 0

        mov     ecx, ebx
        shl     eax, cl         ; Multipliziere a mit 2**Minimum
        pop     ebx
done:
        ret

swell

1. ↑ J. Stein: Computational problems associated with Racah algebra . In: Journal of Computational Physics . tape 1 , no. 3 , 1967, ISSN  0021-9991 , pp. 397-405 , doi : 10.1016 / 0021-9991 (67) 90047-2 .
2. ^ Donald E. Knuth : The Art of Computer Programming . Volume 2: Seminumerical Algorithms. 3. Edition. Addison-Wesley Professional, 1997, ISBN 0-201-89684-2 , pp. 338-341.
3. ↑ Alexander Weers: Greatest common factor. Formelsammlung24.de, accessed on March 27, 2018 .