Hinweis zum euklidischen Algorithmus

[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;

[marabu]

Hallo Christian,

da hast du allerdings zwei dicke Klopse entdeckt - soviel zum Thema QM. Nur zwei Klopse deshalb, weil ggT(0, b) = |b| nicht ganz richtig ist - auch wenn du das eventuell bei Wikipedia so gelesen hast. Genauer gilt ggT(0, b) = b für jedes b ungleich 0. Es ist in der Mathematik allerdings üblich sich in diesem Zusammenhang auf positive Ergebnisse zu beschränken, da nach dem "Fundamentalsatz" der Zahlentheorie zur Teilbarkeit gilt:

(1) Für alle n ungleich 0 gilt n teilt 0 und n teilt n
(2) Ist m Teiler von n, so ist auch -m Teiler von n und m Teiler von -m

Vergleiche: Bundschuh "Einführung in die Zahlentheorie" Springer: 2002; Kapitel 1.2

Für die Freunde der funktionalen Programmierung hier noch eine rekursive Lösung des Problems:

Delphi-Quellcode:

function Gcd(n, m: Int64): Int64;
begin
  Result := Math.IfThen(m = 0, n, Gcd(m, n mod m));
end;

// oder 

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

Die Beschränkung auf positive Ergebnisse mittels Abs() findet bei Bedarf außerhalb der Funktion statt.

Freundliche Grüße

[Hawkeye219]

Hallo marabu,

die Lösung mit "IfThen" gefällt mir nicht. Da war doch mal was...

Gruß Hawkeye

[marabu]

Guten Morgen Hawkeye,

functional programming ohne lazy evaluation - gefällt mir eigentlich auch nicht. Danke für dein aufmerksames Lesen.

Freundliche Grüße

[gammatester]

Zitat:

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

[gammatester]

Zur Klarstellung:

nicht der Beitrag von Cöster ist fehlerhaft, sondern der Delphicode den Chakotay1308 in Code-Library-Eintrag zum Euklidschen Algorithmus daraus ableitet.

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;

Bei Cöster steht richtig Result := Abs(A). Allerdings sollte auch bei ihm Integer zurückgeliefert werden.

Gammatester

[Cöster]

Das stimmt, wenn man Abs weglässt, muss man auch Integer statt Cardinal zurückgeben.

Zitat:

Zitat von gammatester

da mathematisch der ggt immer nicht negativ ist.

:wiejetzt: jetzt doch? Ich blick gerade nicht mehr durch: Wikipedia sagt nicht negativ, weswegen ich auch Abs benutzt hatte. Marabu widerspricht und du stimmst mir wieder zu. Was ist denn jetzt richtig?

Zitat:

Zitat von gammatester

Allerdings sollte auch bei ihm Integer zurückgeliefert werden.

Wieso? Wenn sich das Ergebnis sowieso im Bereich zwischen 0 und 2147483647 müsste es doch eig. egal sein.

[gammatester]

Zitat:

Zitat von Cöster

:wiejetzt: jetzt doch? Ich blick gerade nicht mehr durch: Wikipedia sagt nicht negativ, weswegen ich auch Abs benutzt hatte. Marabu widerspricht und du stimmst mir wieder zu. Was ist denn jetzt richtig?

Richtig ist abs, das kann man leicht einsehen: ggt ist der größte gemeinsame Teiler. Wenn also -abs(d) und abs(d) gemeinsame Teiler sind, ist doch wohl abs(d) der größere.

Zitat:

Zitat von Cöster

Zitat:

Zitat von gammatester

Allerdings sollte auch bei ihm Integer zurückgeliefert werden.

Wieso? Wenn sich das Ergebnis sowieso im Bereich zwischen 0 und 2147483647 müsste es doch eig. egal sein.

Genau, also warum sollte der Ergebnistyp ein anderer sein als der gemeinsame Ausgangstyp? Er ist ja auch nicht int64 oder uint64.

Gammatester

[Cöster]

Zitat:

Zitat von gammatester

warum sollte der Ergebnistyp ein anderer sein als der gemeinsame Ausgangstyp?

Warum sollte der Ergebnistyp kein anderer sein als der gemeinsame Ausgangstyp? Wenn's Cardinal ist, sieht jeder sofort, dass der Rückgabewert positiv ist, auch ohne in den Code zu gucken.

Zitat:

Zitat von gammatester

Er ist ja auch nicht int64 oder uint64.

Weil das (im Gegensatz zu Integer/Cardinal) den Nachteil hätte, dass der Rückgabewert doppelt so viel Speicher einnimmt.

[alcaeus]

Dass -abs(d) < abs(d) gilt, ist auch nur eine Frage der Definition. Beachte: nicht immer arbeiten Mathematiker mit einem Zahlenstrahl, und selbst wenn, dann sieht der nicht immer so aus wie in der Grundschule ;)

Greetz
alcaeus