How do I use recursion and get Maple fast?

Posted on 2009-05-11 12:32 By pichulonco90 (6)

Categories:

How do I ...? with Maple

I have the next problem, i need to use recursion to make the equation E(x+1)=E(x)+(E(x)*(P-E(x)))/P*10 with P 15000 and E(1)=1, i put for example E(20), but maple only use ram, but doesn't do anything.

Thanks

option remember

Comment on 2009-05-11 13:38 from pagan ( Maple Rating 4

412)

Note that you can simplify the rhs

> simplify( E(x+1)=E(x)+(E(x)*(P-E(x)))/P*10 );
                                   E(x) (-11 P + 10 E(x))
                      E(x + 1) = - ----------------------
                                             P

Suppose that you construct a procedure that computes E(x), and which does so by calling E(x-1).

> simplify( E(x)=E(x-1)+(E(x-1)*(P-E(x-1)))/P*10 );
                             E(x - 1) (-11 P + 10 E(x - 1))
                    E(x) = - ------------------------------
                                           P

You should probably first see whether the rsolve command can do anything nice with it.

If not, then construct procedure E by with `option remember` so that each separate inner invocation of E(x-1) does not needlessly duplicate each others' subcomputations. (You want to avoid unnecessary growth of the computation tree.)

> restart:
> P:=15000:
> E:=proc(x) option remember;
>    -E(x-1)*(-11*P+10*E(x-1))/P;
> end proc:
> E(1):=1:

Now observe how the length of the exact results grows, and how the computation time grows.

> for i from 10 to 18 do
> st:=time():
> print([length(E(i)), time()-st]);
> end do:
                                  [3270, 0.]

                                  [6541, 0.]

                                [13080, 0.004]

                                [26159, 0.008]

                                [52316, 0.020]

                                [104630, 0.080]

                                [209260, 0.292]

                                [418520, 1.128]

                                [837038, 4.345]

Deduce how long the result for E(20) would be, and how much time it would take to compute it.

Try it all again, but with evalf(...) around the inside of the E procedure. Try it also without the option remember, and find the timings and lengths for i=1..6, and make inferences.

Avoid recursion...

Comment on 2009-05-11 13:37 from Thomas Unger ( Maple Rating 2

185)

...like the plague.

Just do a simple loop:

restart:
P:=15000:E[1]:=1:
for n from 1 to 20 do E[n+1]:=E[n]+E[n]*(P-E[n])/P*10.0 od;

note

Comment on 2009-05-11 13:41 from pagan ( Maple Rating 4

412)

It may be worth noting, for the benefit of the understand of the OP, that the use of 10.0 will bring about floating-point arithmetic (similar to using evalf). Also, the use of [] table references will have pretty much the same effect as using procedure calls with option remember.

recursion

Comment on 2009-05-11 14:42 from pichulonco90 (6)

I used your post to try to solve my equation, but Maple evaluate a lot of time (I take 2 hours, and no result are shown), so what can I do?

hm

Comment on 2009-05-11 15:12 from pagan ( Maple Rating 4

412)

> restart:
> P:=15000:
> E:=proc(x) option remember;
>   -E(x-1)*(-11*P+10*E(x-1))/P;
> end proc:
> E(1):=1:
> kernelopts(printbytes=false):
> st:=time(): length(E(20)); time()-st;
                                    3348149

                                    92.177

> restart:
> P:=15000:
> E:=proc(x) option remember;
>   evalf( -E(x-1)*(-11*P+10*E(x-1))/P );
> end proc:
> E(1):=1:
> st:=time(): E(20); time()-st;
                                             17778
                             -0.5132751215 10

                                      0.

hm ... hmmm

Comment on 2009-05-11 15:49 from Axel Vogt ( Maple Rating 4

1431)

If only 1 - 2 steps more are needed (and not having a good idea for the task [modified logistic map ?]
in that homework (?) here is a lame modification:

  P:=15000:
  R:=proc(n) option remember;
  local r;
  if n < 19 then 
    -R(n-1)*(-11*P+10*R(n-1))/P;
  else
    r:= evalf(R(n-1));
    -r*(-11*P+10*r)/P;
  end if;
  end proc:
  R(1):=1:

  st:=time():
  R(20): evalf(%);
  time() - st;

                                        17778
                        -0.5132740841 10

                                3.562

??

Comment on 2009-05-11 16:45 from pichulonco90 (6)

copying and pasting... I get another result from you... dunno why :S

dunno 2

Comment on 2009-05-11 16:48 from Axel Vogt ( Maple Rating 4

1431)

otherwise provide complete replies (and Maple versions etc, best is a worksheet, classical *.mws format).

gn8

hm^2

Comment on 2009-05-11 16:45 from Axel Vogt ( Maple Rating 4

1431)

without thinking about error propagation:

write as ln(E(x+1)) = ln(-E(x))+ln((-11*P+10*E(x))/P) for E negative (x large)

then ignore the 11 (from known values) and get E(x+1) = -10/P*E(x)^2

use rsolve (for which starting value n?) ... just a thought ...

??

Comment on 2009-05-11 17:06 from pichulonco90 (6)

still don't understand.. sorry...

but my Maple when start evaluating for example E(20) it takes a lot of time.... and it doesn't do anything!..., with your answers it takes me to a strange number.

sketchy way

Comment on 2009-05-12 16:17 from Axel Vogt ( Maple Rating 4

1431)

P:=15000:
> S:=proc(n) option remember;
> local r;
> if n < 11 then 
>   -S(n-1)*(-11*P+10*S(n-1))/P;
> elif n < 20 then # ignore small constant 
>   -S(n-1)*S(n-1)/1500;
> else
>   r:= evalf(S(n-1));
>   -1/1500*r*r;
> end if;
> end proc:
> S(1):=1:

That is exact for small n and gives a small error beyond, since
10*Q(10)/P ~ -.2280046013e18 has much more decimal places

nTst:=16;
> S(nTst): evalf(%);
> Q(nTst): evalf(%);
> Q(nTst) - S(nTst): evalf[1000](%): evalf(%);

Now solve recurrence for ignoring '11'

> f(n)=-f(n-1)*f(n-1)/q;
> rsolve({%}, f(k));
> simplify(%) assuming (k::posint, 0 < q, f10 < 0);
> #simplify(%, symbolic);
> #eval(%, k=0);
> #eval(%%, k=1);
> #eval(%%%, k=2);

                                k      k
                              (2 )  (-2  + 1)
                         -f(0)     q

Then the following equals S and is fast, error see above,
f(0) stands for S(10)

> T:=proc(n) option remember;
> local r, f0,q;
> q:=10/P;
> if n < 11 then 
>   -T(n-1)*(-11+T(n-1)/1500);
> else
>   f0:= T(10);
>   r:= f0*q;
>   -r^(2^(n - 10))/q;
> end if;
> end proc:
> T(1):=1:

A test:

> nTst:=19;
> Sn:=S(nTst): evalf(%);
> -(S(nTst-2)/1500)^(2^(2)) * 1500: evalf(%);
> Sn+(S(10)/1500)^(2^(nTst-10)) * 1500;: evalf(%);
> Tn:=T(nTst): 
> Sn - Tn; #evalf(%);

                                  0

Hope I have not an index-shifting error in it (test it, all n).

Modify using evalf for lager n.

In case of trouble upload your sheet, after copying above to it.

How do I use recursion and get Maple fast?

Comment viewing options