4
$\begingroup$

I have the following code

epsilon[t_, alpha_] := If[t > 3, 1, 2]
L[t_, alpha_] := 
 Min[epsilon[t, 
    alpha] - (x[t - 1, alpha] - 
     Min[epsilon[t, alpha - 1], x[t - 1, alpha]]), x[t - 1, alpha - 1]]
d[t_] := 10
f = 5
x[0, alpha_] := 0
x[t_, f] := x[t - 1, f] + L[t, f] - Min[d[t - 1], x[t - 1, f]]
x[t_, 0] := 10

x[t_, alpha_] := x[t - 1, alpha] + L[t, alpha] - L[t, alpha + 1]
s = TimeUsed[];
Table[x[t, a], {t, 0, 8}, {a, 0, 10}] // MatrixForm
Timeused : TimeUsed[] - s

The timeused output increases dramatically and nonlinearly as I increase the range of t, in Table[...]:

1. 0.0 
2: 0.016 
3: 0.016 
4: 0.063 
5: 0.422 
6: 2.90 
7: 19.344 
8: 131

Why does this happen? It seems to me that my equations should be computable in linear of $t$ time: For every $t$, x[t, alpha] can be calculated solely on the basis of x[t-1, alpha]. Therefore each computation should be roughly equally intensive. So it should be able to just sequentially compute all the $x$'s for $t = 0$, $t = 1$, $t = 2$, ...

What am I doing wrong?

$\endgroup$
  • $\begingroup$ Try to avoid the SetDelay, i.e, := instead use =. $\endgroup$ – zhk Apr 15 '17 at 9:02
  • $\begingroup$ If I turn them all to =, it gives me this: "$RecursionLimit::reclim2: "Recursion depth of 1024 exceeded during evaluation of -Min[10,x[-1+(-1022+t),5]]."" $\endgroup$ – user56834 Apr 15 '17 at 9:06
6
$\begingroup$

I think your code is a good candidate for using memoization.

    Clear[epsilon, L, x, d, f]

    epsilon[t_, alpha_] := If[t > 3, 1, 2]

    L[t_, alpha_] := Min[
      epsilon[t,alpha] - (x[t - 1, alpha] - Min[epsilon[t, alpha - 1], x[t - 1, alpha]]),
      x[t - 1, alpha - 1]
      ]

    d[t_] := 10
    f = 5;
    x[0, alpha_] := 0
    x[t_, 0] := 10

    (* changes in definition of x *)
    x[t_, f] := x[t, f] = x[t - 1, f] + L[t, f] - Min[d[t - 1], x[t - 1, f]]
    x[t_, alpha_] := x[t, alpha] = x[t - 1, alpha] + L[t, alpha] - L[t, alpha + 1]

Then calculation takes a fraction of a second.

Table[x[t, a], {t, 0, 8}, {a, 0, 10}] // AbsoluteTiming // First
(*0.00019*)
| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.