Recursion - how long will be computing?

[Oberon]

Hi.
I wrote algorithm

double G(int m , int n){
if(m<0 || m>n){
return 0;
}
if (m==0 && n==0){
return P_G;
}
else{
return (G(m,n-1)*P_GG + B(m,n-1)*P_BG );
}
}

double B(int m, int n){
if(m<0 || m>n){
return 0;
}
if (m==0 && n==0){
return P_B;
}
else{
return ( B(m,n-1)*P_BB*NE_B + G(m,n-1)*P_GB*NE_B +
B(m-1,n-1)*P_BB*E_B +G(m-1,n-1)*P_GB*E_B );
}
}

In main i compute P(m,n) = G(m,n)+ B(m,n)

For small n (n<20) it compute in few seconds but i would like to
compare results with the results from literature (n=100)

The total number of computations is :
16n^2 multiplications
6n^2 additions

After 1 hour it didnt compute (m=10 ,n=100) (Core duo (notebook)
1.6Ghz)

How long it will compute ? or the algorithm is wrong build (any
errors ?? ))

Thanks

[=?ISO-8859-2?Q?Erik_Wikstr=F6m?=]

Re: Recursion - how long will be computing?

On 2007-06-06 17:37, Oberon wrote:

Hi.
I wrote algorithm
>
double G(int m , int n){
if(m<0 || m>n){
return 0;
}
if (m==0 && n==0){
return P_G;
}
else{
return (G(m,n-1)*P_GG + B(m,n-1)*P_BG );
}
}
>
double B(int m, int n){
if(m<0 || m>n){
return 0;
}
if (m==0 && n==0){
return P_B;
}
else{
return ( B(m,n-1)*P_BB*NE_B + G(m,n-1)*P_GB*NE_B +
B(m-1,n-1)*P_BB*E_B +G(m-1,n-1)*P_GB*E_B );
}
}
>
In main i compute P(m,n) = G(m,n)+ B(m,n)
>
For small n (n<20) it compute in few seconds but i would like to
compare results with the results from literature (n=100)
>
The total number of computations is :
16n^2 multiplications
6n^2 additions
>
After 1 hour it didnt compute (m=10 ,n=100) (Core duo (notebook)
1.6Ghz)
>
How long it will compute ? or the algorithm is wrong build (any
errors ?? ))

If the number of multiplications and additions is correct then you have
a quadratic running time, meaning that the time it takes to run the
program is proportional to the quadrate of n. Try running with smaller
numbers first (10, 20, 30, 40, ...) and see how long it takes and you
should be able to get a figure. If you have a better calculator it
should be able to figure out the function to calculate the time based on n.

Notice thought that since you have a recursive function it is possible
that you'll run out of stack-space before completing the computation. It
is sometimes (always?) possible to rewrite the code to use a normal loop
and store values of previous iterations in an array, which will be more
space efficient and often run much faster.

--
Erik Wikström