fakultät ausrechnen - Exception wenn Wert zu groß wird

[Luckie]

Ich spieöle gerade etwas mit einer Funktion zur Berechnung der Fakultät rum:

Delphi-Quellcode:

function fakultaet(UpperLimit: Int64): Int64;
begin
  if UpperLimit < 0 then
    raise ERangeError.Create('Wert ausserhalb des Wertebereichs');

  if (UpperLimit = 0) or (UpperLimit = 1) then
    result := 1
  else
    result := fakultaet(UpperLimit - 1) * UpperLimit;

  if result = High(Int64) then
    raise ERangeError.Create('Wert ausserhalb des Wertebereichs');
end;

Wenn der Wert zur groß wird, wird leider ein Stacküberlauf ausgelöst. Für den Benutzer ist das aber eine eher unverständliche Fehlermeldung, deswegen wollte ich, wenn der Wertebereich überschritten wird eine ERangeError Exception auslösen. Nur leider scheint da snicht zu funktionieren, weil ich die Exception erst werfen, wenn das Kind schon in den Brunnen gefallen ist. Wie kann ich das lösen?

[Fridolin Walther]

Hmmm ... vielleicht steh ich ja aufm Schlauch, aber was hat die RangeException mit dem Stacküberlauf zu tun, der wahrscheinlich dadurch verursacht wird, daß für weitere Funktionsstacks kein Platz mehr ist auf Grund der hohen Rekursionstiefe.

[Luckie]

Ja das stimmt. Es kann natürlich zu einem Stacküberlauf kommen bevor der Wertebereich überwschritten wird. :gruebel:

[Desmulator]

Zitat:

Zitat von Luckie

Delphi-Quellcode:

  if UpperLimit < 0 then
    raise ERangeError.Create('Wert ausserhalb des Wertebereichs');

Wäre es nicht besser hier eine EInvalidParam zu werfen? Es ist ja eigendlich kein RangeError sondern eher ein ungültige Operation. Die Mathunit macht das doch auch irgenwie :roll:

Naja nun zum Problem, du wirst mit der Fakultät ja nie genau High(Int64) erreichen, dahher musst du vorher berechnen, was die größt mögliche Fakultät ist und dann vorher prüfen ob UpperLimit genau diesen Wert hat. Fakultät von 4 ist ja 1 * 2 * 3 * 4, also benutz einfach den Debugger und finde herraus, welchen Wert UpperLimit hat, bevor es zu dem Fehler kommt. Könntest z.B. auch ne Konsole allocen und dann mit WriteLn jedes mal UpperLimit ausgeben, das was am Ende da steht ist der gesuchte Wert. ( AllocConsole (?) oder einfach als Consolenprogramm kompelieren. ( {$APPTYPE CONSOLE} ) )

[jfheins]

Wie wärs damit:

Delphi-Quellcode:

function fakultaet(n: Int64): Int64; 
begin 
  if n < 0 or n > 20 then 
    raise ERangeError.Create('Wert ausserhalb des Wertebereichs'); 

  if (n = 0) or (n = 1) then 
    result := 1 
  else 
    result := fakultaet(n - 1) * n; 
end;

20! passt noch in den Int64, 21! nicht mehr => Fehler wird abgefangen bevor losrekursiert wird :stupid:

[Fridolin Walther]

Delphi-Quellcode:

function fakultaet_nonrecursive(UpperLimit: Int64) : Int64;
var
  i : Int64;
begin
  Result := 1;
  i := 2;
  while i <= UpperLimit do
    begin
      if Result * i < Result then
        raise Exception.Create('Integerüberlauf!');
      Result := Result * i;
      inc(i);
    end;
end;

Wäre mein Vorschlag. Ohne Fehlerhandling. Keine Rekursion. Wirft ne Exception sobald es überläuft. Übrigens wie mein Vorredner bereits gesagt hat bei 21.

[mirage228]

Zitat:

Zitat von Fridolin Walther

Delphi-Quellcode:

function fakultaet_nonrecursive(UpperLimit: Int64) : Int64;
var
  i : Int64;
begin
  Result := 1;
  i := 2;
  while i <= UpperLimit do
    begin
      if Result * i < Result then
        raise Exception.Create('Integerüberlauf!');
      Result := Result * i;
      inc(i);
    end;
end;

Wäre mein Vorschlag. Ohne Fehlerhandling. Keine Rekursion. Wirft ne Exception sobald es überläuft. Übrigens wie mein Vorredner bereits gesagt hat bei 21.

Oder einfach in den Projektoptionen die Überlaufprüfung einschalten ;)

[Chemiker]

Hallo Luckie,

Zitat:

Zitat von Luckie

Es kann natürlich zu einem Stacküberlauf kommen bevor der Wertebereich überwschritten wird

.

das hat aber weniger mit dem Stack zu tun, als vielmehr mit der Registergröße.

Außerdem scheint mir Cardinal besser geeignet zu sein als int64, weil ohne Vorzeichen.

Bis bald Chemiker

[mirage228]

Zitat:

Zitat von Chemiker

Außerdem scheint mir Cardinal besser geeignet zu sein als int64, weil ohne Vorzeichen.

Gibt es nicht auch UInt64?

Viele Grüße

[Chemiker]

Hallo mirage228,

dann ist die Berechnung, aber nicht mehr nur mit Registern durchzuführen bei 64Bit.

Delphi-Quellcode:

function ASMFacIterativ(n: word): Cardinal;
asm
  PUSH ECX
  CMP EAX, 20
  JG @@ZuViel
  CMP EAX, 1
  JLE @@NullOderEins
  MOV ECX, EAX
  DEC ECX
@@Weiter:
  MUL ECX
  LOOP @@Weiter
  JMP @@Schluss
@@ZuViel:
   XOR EAX, EAX
   JMP @@Schluss
@@NullOderEins:  // Hier ladet er bei -Zahlen, bei 0 und bei 1
  CMP EAX, 0
  JE @@MacheEins
  CMP EAX, 1
  JE @@MacheEins
  MOV EAX, 0
  JMP @@Schluss
@@MacheEins:
  OR EAX,1
@@Schluss:
  POP ECX
end;

Bis bald Chemiker

[BUG]

Solange wir kein 64bit-Delphi haben hat selbst Int64 doch einen viel größeren positiven Wertebereich als Cardinal, oder :gruebel:

Code:

Int64       Cardinal
--------    --------
2^(64-1) >> 2^(32)

MfG,
Bug

[Chemiker]

Hallo BUG,

das schon, aber es bringt in dem Fall nichts, weil alle Zahlen größer 20 nicht mehr in einem 32-Bit-Register dargestellt werden können. Und dem Fall ist meiner Meinung Cardinal der bessere Typ.

Bis bald Chemiker

[mirage228]

Also das verstehe ich noch nicht so ganz. 20! kann mit Cardinal nicht dargestellt werden (Integer Overflow), mit Int64 jedoch schon. Falls Du die übrigen Variablen meinst.... als UpperLimit und die lokale Variable i. Ja, die als Int64 zu machen wäre sinnlos. Da ist ein vorzeichenloser Integer (Cardinal z.B.) besser geeignet.

[Chemiker]

Hallo mirage228,

vergesst am besten was ich geschrieben habe, ich fürchte das lag etwas an dem erhöhten Bierkonsum gestern.

Bis bald Chemiker

[Stevie]

Zitat:

Zitat von Luckie

Ja das stimmt. Es kann natürlich zu einem Stacküberlauf kommen bevor der Wertebereich überwschritten wird. :gruebel:

Imo stimmt da was anderes nicht - wegen einer Rekursionstiefe von etwas über 20 bei einer solch trivialen Funktion fliegt noch lange nicht der Stack auseinander.
Warum löst du eigentlich etwas rekursiv, was auch ganz einfach iterativ möglich ist?

[sirius]

Zitat:

Zitat von Stevie

Imo stimmt da was anderes nicht - wegen einer Rekursionstiefe von etwas über 20 bei einer solch trivialen Funktion fliegt noch lange nicht der Stack auseinander.

Das liegt wohl daran, dass Luckie die Bereichsüberprüfung ausgeschaltelt hat. Dann gibt er eine schöne große Zahl ein. Hat x Rekursionsaufrufe, Result stimmt schon lange nicht mehr (wegen Überlauf) und dann kommt sein Fehler.

[Luckie]

Jupp, die Bereichsprüfung ist abgeschaltet. Ich denke da nie dran, weil die standardmäßig nicht aktiviert ist.