Improve speed in this tree - memoization won't suffice
I found that it is considerably faster, if you process the fractional part of j
as a seperate integer variable:
Clear[function1, function2]
function1[i_, j_, jc_] := function1[i, j, jc] =
Which[i >= 40, 1.0, j >= 40, 0.0, jc >= 40, 0.0, True,
0.18*0.45*(1 - function2[j, i + 1, jc]) +
0.66*0.45*(1 - function2[j, i + 2, jc]) +
0.16*0.45*(1 - function2[j, i + 3, jc]) + (1 - 0.18*0.45 -
0.66*0.45 - 0.16*0.45)*(1 - function2[j, i, jc])];
function2[j_, i_, jc_] := function2[j, i, jc] =
Which[j >= 40, 1.0, i >= 40, 0.0, True,
0.18*0.55*(1 - function1[i, j + 1, jc]) +
0.66*0.55*(1 - function1[i, j + 2, jc]) +
0.16*0.55*(1 - function1[i, j + 3, jc]) + (1 - 0.18*0.55 -
0.66*0.55 - 0.16*0.55)*(1 - function1[i, j, jc + 1])];
The primary inefficiency of your code comes from quite a lot of unnecessary evaluations and memoizations because of pattern matching on machine numbers. If we eliminate these the function is several times faster. Simply changing function1[i, j+0.01]
in your last line of code to function1[i, j + 1/100]
is sufficient.
With your original:
function1[0, 0] // AbsoluteTiming
function1 // DownValues // Length
function2 // DownValues // Length
{6.90192, 0.218588} 342540 323897
With that sole change:
function1[0, 0] // AbsoluteTiming
function1 // DownValues // Length
function2 // DownValues // Length
{1.48465, 0.218587} 69036 67436
Berg's code fundamentally works in the same way.