ggT-Berechnung / Euklidischer Algorithmus

[thepaul]

Der Euklidsche Algorithmus zur Berechnung des ggT (größter gemeinsamer Teiler)

Delphi-Quellcode:

function ggT(a, b:Integer):Integer;
var
  rest:Integer;
begin
  rest:=a mod b;
  while rest<>0 do 
  begin
    rest:=a mod b;
    a:=b;
    b:=rest;
  end;

  Result:=a;
end;

(Ursprünglich von thepaul, erweitert und "verkleinert" von fkerber)

[edit=Chakotay1308]Ergänzung. Mfg, Chakotay1308[/edit]
[edit=Matze]Code formatiert. Mfg, Matze[/edit]
[edit=Dax]Das Highlighting... Mfg, Dax[/edit]
[edit=Chakotay1308] Mfg, Chakotay1308[/edit]

[CalganX]

Von [user]Cöster[/user] kommt der Hinweis, dass obige Funktion Probleme mit zwei Sonderfällen hat:

Zitat:

Zitat von Cöster

b=0 würde wegen Division durch 0 zu einem Fehler führen.
Für b=1 würde die Funktion a als Ergebnis liefern (statt 1).

Als korrigierte Version, schlägt er folgende vor:

Delphi-Quellcode:

function ggT(A, B: Integer): Cardinal; 
var 
   Rest: Integer; 
begin 
   while B <> 0 do 
   begin 
      Rest := A mod B; 
      A := B; 
      B := Rest; 
   end; 
   Result := A; 
end;

Darüberhinaus schlägt marabu noch eine weitere, rekursive Variante vor:

Delphi-Quellcode:

function Gcd(n, m: Int64): Int64; 
begin 
  if m = 0 then Result := n 
  else Result := Gcd(m, n mod m); 
end;