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

[gammatester]

Zitat:

Zitat von 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.

Alles richtig, aber es besteht doch wirklich keine Notwendigkeit dazu. Du nimmts doch auch nicht den Ergebnistyp

Delphi-Quellcode:

type posint = 0..MaxInt

[gammatester]

Zitat:

Zitat von 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

Das ist erstens nicht ganz richtig, weil -abs(0) nicht kleiner ist als abs(0), und zweitens hier völlig irrerelevant, denn es wird doch offensichtlich die Standardinterpretation von ganzen Zahlen (im 32 Bitbereich betrachtet.

Allerdings würde mich ein Beispiel interessieren, wo "-"], "<"] und "abs" definiert sind aber -abs(d) <= abs(d) nicht gilt.

Gammatester

[Laufi]

Zitat:

Zitat von gammatester

Allerdings würde mich ein Beispiel interessieren, wo "-"], "<"] und "abs" definiert sind aber -abs(d) <= abs(d) nicht gilt.

d = NaN :gruebel: :dp:

gruss laufi

[gammatester]

Zitat:

Zitat von Laufi

Zitat:

Zitat von gammatester

Allerdings würde mich ein Beispiel interessieren, wo "-"], "<"] und "abs" definiert sind aber -abs(d) <= abs(d) nicht gilt.

d = NaN :gruebel: :dp:

gruss laufi

Das ist ziemlicher Blödsinn aus mindestens zwei Gründen:

1. Wie reden hier von integern, da gibts es kein NaN

2. Wenn Du schon Fließkommazahlen benutzen willst und solche Behauptungen aufstellst, solltest Du sie vielleicht vorher mal testen. Rate mal, was auf dem Button erscheint, wenn Du den das folgende Stück in ein Programm einbaust.

Delphi-Quellcode:

uses math;

procedure TForm1.Button1Click(Sender: TObject);
var
  d: double;
begin
  d := NaN;
  if -abs(d)<=abs(d) then button1.Caption := 'True'
  else button1.Caption := 'False'
end;

[Laufi]

das spielt überhaupt keine rolle :roll:

Zitat:

Zitat von Wikipedia

Vergleicht man ein NaN-wertiges Ergebnis mit sich selbst, dann besteht Ungleichheit.

gruss laufi

[gammatester]

Zitat:

Zitat von Laufi

das spielt überhaupt keine rolle :roll:

Zitat:

Zitat von Wikipedia

Vergleicht man ein NaN-wertiges Ergebnis mit sich selbst, dann besteht Ungleichheit.

gruss laufi

Diese Diskussion wird ja immer absurder. Wenn überhaupt irgendetwas halbwegs sinnvoll auf Gleichheit getestet werden kann, dann sollte doch wohl a=a für alle Elemente gelten.

Wenn (und leider ist da kein Link) Wikipedia das schreibt, dann ist es halt schlicht und einfach falsch.

Schönes Wochenende
Gammatester