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:
- if a and b are even.
- if a is even and b is odd.
- 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: .
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 0 solange a und b gerade Zahlen sind a a/2 b b/2 k k + 1 wenn a eine ungerade Zahl ist dann t -b sonst t a solange t ≠ 0 solange t eine gerade Zahl ist t t/2 wenn t > 0 dann a t sonst b -t t a - b return a 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 bsf
uses:
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
- ↑ 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 .
- ^ 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.
- ↑ Alexander Weers: Greatest common factor. Formelsammlung24.de, accessed on March 27, 2018 .