Entwickler-Ecke :: Thema anzeigen

Mitmischer 1703 - Mi 08.12.10 21:11
Titel: Stack-Überlauf

Hi DF!

Ich soll für die Schule einen Algorithmus programmieren, um Pi zu berechnen. Das funktioniert soweit auch wunderbar - nur gab's da ein Problemchen. Der Algorithmus ist rekursiv, also war ein Stackoverflow natürlich unumgänglich. Mit dem Stackoverflow an sich hab ich kein Problem - nur mit der Rekursionszahl bis zum Overflow.

Mein Algorithmus schafft bis zum Crash 12305 Rekursionen. Das ist meiner Meinung nach viel zu wenig, denn mein RAM lacht sich über seine Belastung kaputt. Das waren ca. 2 MB Belastung für 4 GB RAM...
Sobald ich in meiner rekursiven Funktion den Datentyp von Single auf Extended ändere, schafft der Algo nur noch 11235 Rekursionen.
Es sieht für mich so aus, als dass der Stack die RAM-Größe nicht voll ausnutzt.

Workaround

Da mir der Algo mit seinen 10000 Rekursionen viel zu schnell vorbei ist :mrgreen:, hab ich über zwei Workarounds nachgedacht, die meiner Meinung nach aber sehr unschön sind. Vielleicht habt ihr ja noch Ideen, was man zur Vermeidung von Stack-Overflows unternehmen kann ;)

Die Rekursion der Funktionen auf 500 begrenzen, mit for-Schleifen bis zur gewünschten Rekursionsteife vordringen.
Die Funktionen zu Prozeduren machen, das Ergebnis in eine Variable schreiben. Ich weiß nicht, ob das was bringt, probiere ich aber jetzt aus.

Was kann ich tun, um einen Stack-Overflow zu vermeiden oder wenigstens so lange herauszuzögern, bis ich eine Rekursionstiefe hab, die halbwegs vernünfig ist?
Was vermeidet einen Stack-Overflow eher und warum: Felder, lokale Variablen oder Funktionsvariablen?

Je weniger Variablen, desto mehr Rekursionen?

Narses - Mi 08.12.10 21:14

Moin!

Lokale Variablen landen mit auf dem Stack, so dass man hier möglichst wenige verwenden sollte. Du kannst aber auch einfach den Stack in den Programmoptionen erhöhen (das ist allerdings kein Allheilmittel für einen schlecht programmierten Algorithmus - ganz allgemein mal dazu gesagt :?). :idea:

cu
Narses

Xion - Mi 08.12.10 22:30

Statt der Rekursion kannst du deinen Algorithmus eventuell auch Iterativ machen...hmm, wie ging nochmal die Berechnung von Pi? xD

wikipedia hat folgendes geschrieben:

Der Chinese Chao Lu ist offizieller Weltrekordhalter mit bestätigten 67.890 Nachkommastellen, welche er am 20. November 2005 fehlerfrei in einer Zeit von 24 Stunden und 4 Minuten aufsagte.

:autsch:

Also ich finde jetzt auf die schnelle keinen rekursiven Quellcode...zeig mal deinen :D

Mitmischer 1703 - Mi 08.12.10 22:32

Ah. Sagt doch was :nut:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:

function TForm3.WallisProduct(AResult : Extended; ACounter, ABreakAt : Word) : Extended;
begin
  try
   if ACounter > ABreakAt then
    Exit(AResult*2);
   Result := AResult*
         ((ACounter*2/
         (ACounter*2-1))*
          (ACounter*2/
         (ACounter*2+1)));
   Inc(ACounter);
   FRecursions := ACounter;
   Result := WallisProduct(Result, ACounter, ABreakAt);
  except on EStackOverflow do
   Exit(AResult*2);
  end;
end;

Das erste Mal so aufgerufen:

Delphi-Quelltext

1:	ShowMessage(FloatToStr(WallisProduct(1, 1, Recursions)));

Recursions gibt die Grenze an, ab der der Algo abbrechen soll.

Edit: FRecursions gibt mir an, wie viele Durchläufe der Algo geschafft hat. Hat also eine rein statistische Funktion.

Xion - Mi 08.12.10 22:53

So wie ich das sehe kannst du das prima Iterativ machen:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:

function TForm3.WallisProduct(AResult : Extended; ACounter, ABreakAt : Word) : Extended;
begin
  //while Schleife außenrum
  while True do
  try
   if ACounter > ABreakAt then
    Exit(AResult*2);
   Result := AResult*
         ((ACounter*2/
         (ACounter*2-1))*
          (ACounter*2/
         (ACounter*2+1)));
   Inc(ACounter);
   FRecursions := ACounter;
   //Result := WallisProduct(Result, ACounter, ABreakAt);
   //stattdessen, Werte lokal anpassen:
   AResult:=Result;
   ACounter:=ACounter;
   ABreakAt:=ABreakAt;
  except on EStackOverflow do
   Exit(AResult*2);
  end;
  end;
end;

Ich hab den Code jetzt einfach mal durch ne while Schleife ergänzt und die Parameter gesetzt...da ist natürlich sinnloses dabei, das kannst du dann selbst rausnehmen :D Auch bräuchte die while Schleife ne Abbruchbedingung...

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!