ggT: Funktional vs. Imperativ

In diesem Kapitel werden wir den funktionalen Algorithmus des größten gemeinsamen Teilers mit dem imperativen Algorithmus vergleichen.

Version 1

GGT1 var X,Y: int;
                  input X,Y;
                  while  X ≠ Y {
                         while  X > Y   { X :=  X-Y; }
                         while  X < Y   { Y :=  Y-X; }
                   }
                  output X;

Die Auswertung für X=19 und Y=5 lautet:

X	Y
19	5
14	5
9	5
4	5
4	1
3	1
2	1
1	1

Die Berechnung erfolgt durch die Subtraktion der jeweils kleineren Zahl. Es ist zu Beobachten, dass der ggT mittels Subtraktion nicht effizient berechnet werden kann.

Version 2

GGT2 var X,Y,R: int;
                  input X,Y;
                  R := 1
                  while  R ≠ 0 {
                      R := X % Y;  X := Y;  Y := R;
                  }
                  output X;

Die Auswertung für X=19 und Y=5 lautet:

X	Y	R
19	5	1
5	4	4
4	1	1
1	0	0

Die Auswertung für X=2 und Y=1000 lautet:

X	Y	R
2	1000	2
2	0	0

Die Berechnung erfolgt hier durch die Modulo Funktion. Falls X<Y sein sollte, werden X und Y erst vertauscht, wie in der zweiten Auswertung.

Dieser Algorithmus ist folgendermaßen definiert:

$[\![GGT2]\!](x,y)=\left\{{\begin{array}{ll}ggT(x,y)&falls~x,y>0\\y&falls~x=y~\neq 0~oder~x=0,y\neq 0\\\bot &falls~y=0\\ggT(|x|,|y|)&falls~x<0~und~y>0\\-ggT(|x|,|y|)&falls~y<0\end{array}}\right.$

Vergleich

Intuitiv ist GGT2 schneller als GGT1, was man durch die Komplexität von Algorithmen zeigen kann.

Literatur

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 3.3.3 zu finden.