Euklidischer Algorithmus

• Ziel: Berechnung des größten gemeinsamen Teilers $(\text{ggT})$ zweier natürlicher Zahlen, z. B. $gcd(a,b)$ .
• Grundidee:
  • Nutzt die Eigenschaft: $gcd(a,b)=gcd(b,a\mathrm{mod}b)$.
  • Reduziert schrittweise das Zahlenpaar, bis ein Rest $0$ erreicht ist. Der letzte Nicht-Null-Rest ist der ggT.
• Mathematisches Vorgehen:
  1. Anfang: Gegeben $a,b$  mit $a>b$ .
  2. Schrittweise Division mit Rest:$$\begin{array}{}=q_{1}b+r_1\\ b=q_2{r}_1+r_2\\ r_1=q_3{r}_2+r_3\\ \dots \\ \text{bis }{r}_k=0\end{array}$$
  3. Der letzte Nicht-Null-Rest $r_{k-1}$ ist $gcd(a,b)$

_EUCLID_OLD_(a,b)
1  wenn a = 0 dann
2    Ergebnis = b
3  sonst
4    solange b ≠ 0
5      wenn a > b dann
6        a ← a – b
7      sonst
8        b ← b – a
9      //
10   //
11   Ergebnis = a
12 //

_EUCLID_OLD_RECURSIVE_(a,b)
1  wenn b = 0 dann
2    Ergebnis = a
3  sonst
4    wenn a = 0 dann
5      Ergebnis = b
6    sonst
7      wenn a > b dann
8        Ergebnis = _EUCLID_OLD_RECURSIVE_(a – b, b)
9      sonst
10       Ergebnis = _EUCLID_OLD_RECURSIVE_(a, b – a)
11     //
12   //
13 //

_EUCLID_RECURSIVE_(a,b)
1  wenn b = 0 dann
2    Ergebnis = a
3  sonst
4    Ergebnis = _EUCLID_(b, Divisionsrest(a durch b))
5  //

_EUCLID_ITERATIVE_(a,b)
1  solange b ≠ 0
2      h ← Divisionsrest(a durch b)
3      a ← b
4      b ← h
5  //
6  Ergebnis = a