Rekursion-zu lange Berechnung!

Computer: Software & Programmierung C/C++
#1

Hallo,

mein Programm funktioniert sehr gut aber nur solange ich kleine m und n angebe. Wenn ich große Zahlen für m und n wähle, rechnet es ein paar Tage. Kann mir jemand helfen, um diese Rekursion effizienter zu machen??? Ich wollte die Daten in eine Tabelle schreiben aber das hat irgendwie nicht geklappt. Danke für jeden Hinweis.

#include

float zeta_0(int m, int n)
{float epsilon=1;
float delta=6
if(m==0) return 0;
if(n==0) return 0;
else return 1+((delta*n*zeta_0(m,n-1)+epsilon*m*n*zeta_0(m-1,n+1))/(delta*n+epsilon*m*n));
}

float zeta_1(int m, int n)
{
float M=6;
float rho=6;
if(m==0) return 0;
if(n==0) return 0;
else
return ((M/rho)+M*n+m*n+M*zeta_0(m+1,n)+M*n*zeta_1(m,n-1)+m*n*zeta_1(m-1,n+1)-M*zeta_0(m,n))/(M*n+m*n);
}

main()
{int m;
int n;

m=20;n=20;

printf("%f\n",zeta_0(m,n));
printf("%f\n",zeta_1(m,n));
}

Maria

#2

Hallo Maria,

Ich habe mir deinen Code jetzt nicht genau angesehen.

mein Programm funktioniert sehr gut aber nur solange ich
kleine m und n angebe. Wenn ich große Zahlen für m und n
wähle, rechnet es ein paar Tage. Kann mir jemand helfen, um

Hm, was heißt denn „klein“? Du hast m nur als integer angegeben und das ist üblicherweise nur eine 16-bit-Zahl. Was sagt denn der Debugger?

Ist die Verarbeitungsdauer proportional zur Größe von m? Also braucht die Berechnung von m=20 doppelt so lange wie mit m=10?

diese Rekursion effizienter zu machen??? Ich wollte die Daten
in eine Tabelle schreiben aber das hat irgendwie nicht
geklappt. Danke für jeden Hinweis.

Diese Rekursion ist insgesamt der Hammer. Ich weiß ja nicht, was du berechnen willst, aber schon bei m=10 hast du eine unglaubliche Rekursionstiefe. Da wird dein Stack irgendwann überlaufen. Vermutlich passiert genau das, wenn er „tagelang“ rechnet.

Was sagt denn der Debugger? Was willst du berechnen? Meint: Gibt es da ne Formel, die man möglicherweise umstellen kann?

Günther

#3

Hallo,

mein Programm funktioniert sehr gut aber nur solange ich
kleine m und n angebe. Wenn ich große Zahlen für m und n
wähle, rechnet es ein paar Tage. Kann mir jemand helfen, um
diese Rekursion effizienter zu machen??? Ich wollte die Daten
in eine Tabelle schreiben aber das hat irgendwie nicht
geklappt. Danke für jeden Hinweis.

Hallo Maria,

ohne das genauer zu analysieren, sondern ganz allgemein: Rekursion ist theoretisch elegant, aber in der Praxis so gut wie immer unbrauchbar. Beipiel Fakultät: der Nutzanteil jeder Stufe ist eine einfache Multiplikation, dafür wird aber ein kompletter Funktionsaufruf durchgeführt mit Abspeichern aller Prozessor-Register auf dem Stack, und diese Aufrufe bleiben alle offen bis zum letzten Aufruf, um dann alle nacheinander den Stack freizugeben und zurückzukehren. Die iterative Variante erledigt das gleiche mit einem winzigen Bruchteil an Speicherbedarf und Prozessorleistung.

Gruss Reinhard

#4

Hallo,

mein Programm funktioniert sehr gut aber nur solange ich
kleine m und n angebe. Wenn ich große Zahlen für m und n
wähle, rechnet es ein paar Tage. Kann mir jemand helfen, um
diese Rekursion effizienter zu machen??? Ich wollte die Daten
in eine Tabelle schreiben aber das hat irgendwie nicht
geklappt. Danke für jeden Hinweis.

Ich habe Dein Programm erstmal so umgestellt,
dass die Werte für m und n je nur einmal
berechnet werden. Das sollte schon einiges
bringen (m=50,n=50 in weniger als 1 sec).

Ob das korrekt ist, kann ich nicht beurteilen,
da ich den verwendeten Algorithmus nicht kenne
(irgendwas wie Reihenentwicklung in einem
physikalischen Kontext).

Auf jeden Fall liefert es die selben Ergebnisse
wie Dein Code. Wenn Du höhere m,n brauchst,
musst Du

#define TBSIZE 100

entsprechend erhöhen (immer etwas höher als Deine Zahlen).

Was meinst Du denn mit „in eine Tabelle schreiben“?

Grüße

CMБ

 #include **#define TBSIZE 100**
 **#define EMPTY (4-5)**
 **float zeta\_0\_tb[TBSIZE][TBSIZE];**
 **float zeta\_1\_tb[TBSIZE][TBSIZE];**
 
 **void init\_zeta\_tb() {**
**int i, j;**
**for(i=0; ifor(j=0; jzeta\_0\_tb[i][j] = zeta\_1\_tb[i][j] = EMPTY;  
 }  
  
 float zeta\_0(int m, int n)  
{  
 float delta = 6;  
 float epsilon = 1;  
 if( m==0 || n==0 ) return 0;  
 if( zeta\_0\_tb[m][n] != EMPTY ) return zeta\_0\_tb[m][n];  
  
 return zeta\_0\_tb[m][n] =   
 1 + (  
 ( delta \* n \* zeta\_0(m, n-1)   
 + epsilon \* m \* n \* zeta\_0(m-1, n+1)   
 )   
 / (delta\*n + epsilon\*m\*n)  
 );  
}  
  
  
 float zeta\_1(int m, int n)  
{  
 float M = 6;  
 float rho = 6;  
 if( m==0 || n==0 ) return 0;  
 if( zeta\_1\_tb[m][n] != EMPTY ) return zeta\_1\_tb[m][n];  
  
 return zeta\_1\_tb[m][n] = (  
 (M/rho)  
 + M \* n   
 + m \* n  
 + M \* zeta\_0(m+1, n )  
 + M \* n \* zeta\_1(m, n-1)  
 + m \* n \* zeta\_1(m-1, n+1)  
 - M \* zeta\_0(m, n )  
 )   
 / (M\*n + m\*n);  
}  
  
 main()  
{  
 int m, n;  
   
 m = 20;  
 n = 20;  
   
 init\_zeta\_tb();  
  
 printf("%f\n", zeta\_0(m,n) );  
 printf("%f\n", zeta\_1(m,n) );  
 return 0;  
}**