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