Hinweis zum euklidischen Algorithmus

[gammatester]

Zitat von Cöster:

Hi!

Ich hab mir heute den Code-Library-Eintrag zum Euklidschen Algorithmus angesehen. Die dort gepostete Implementierung berücksichtigt einige Sonderfälle nicht:

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).
ggT(0,b) ist als |b| definiert, gäbe aber 0 zurück.

Folgende Implementierung berücksichtigt diese Fälle und ist außerdem schneller:

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 := Abs(A);
end;

Da ich nicht weiß, wie man einen Code-Library-Beitrag kommentiert, also hier der Hinweis, daß dieser Code eine "Verschlimmbesserung" ist: Ein Speziallfall wird repariert, aber in ca der Hälfte aller Fehler werden neue Fehler/Bugs eingebaut:

Beispiel: ggt(-3,15) liefert je nach Rangecheck-Einstellung entweder 4294967293 oder Runtime error 201 bzw Exception.

Ursache: Eingabe Integer, Ausgabe Cardinal. Wenn Integer verwendet werden, sollte auch abs benutzt werden, da mathematisch der ggt immer nicht negativ ist.

Gruß Gammatester