Stack-Überlauf

Mitmischer 1703 · Verfasst: Mi 08.12.10 21:11

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?

_________________
Die Lösung ist nicht siebzehn.

Narses · Verfasst: 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

).

cu
Narses

_________________
There are 10 types of people - those who understand binary and those who don´t.

BenBE · Verfasst: Mi 08.12.10 21:56

Bitte mit Soße ;-)

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Narses · Verfasst: Mi 08.12.10 22:22

Moin!

BenBE hat folgendes geschrieben :

Bitte mit Soße ;-)

Ähm, what? :gruebel:

cu
Narses

_________________
There are 10 types of people - those who understand binary and those who don´t.

der organist · Verfasst: Mi 08.12.10 22:28

Narses hat folgendes geschrieben :

Moin!

BenBE hat folgendes geschrieben :

Bitte mit Soße ;-)

Ähm, what? :gruebel:

cu
Narses

Quellcode?

_________________
»Gedanken sind mächtiger als Waffen. Wir erlauben es unseren Bürgern nicht, Waffen zu führen - warum sollten wir es ihnen erlauben, selbständig zu denken?« Josef Stalin

Xion · Verfasst: 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.

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

_________________
a broken heart is like a broken window - it'll never heal
In einem gut regierten Land ist Armut eine Schande, in einem schlecht regierten Reichtum. (Konfuzius)

Mitmischer 1703 · Verfasst: Mi 08.12.10 22:32

Ah. Sagt doch was :nut:

markieren

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:

markieren

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.

_________________
Die Lösung ist nicht siebzehn.

Xion · Verfasst: Mi 08.12.10 22:53

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

markieren

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

Auch bräuchte die while Schleife ne Abbruchbedingung...

_________________
a broken heart is like a broken window - it'll never heal
In einem gut regierten Land ist Armut eine Schande, in einem schlecht regierten Reichtum. (Konfuzius)

Mitmischer 1703 · Verfasst: Do 09.12.10 21:52

cool, danke!

_________________
Die Lösung ist nicht siebzehn.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme