Re: help in speeding up code involving a recursive function
- To: mathgroup at smc.vnet.net
- Subject: [mg43926] Re: [mg43907] help in speeding up code involving a recursive function
- From: Dr Bob <drbob at bigfoot.com>
- Date: Sun, 12 Oct 2003 04:03:45 -0400 (EDT)
- Reply-to: drbob at bigfoot.com
- Sender: owner-wri-mathgroup at wolfram.com
This may help:
ClearAll[betacoeff]
betacoeff[0, _, _] := 1;
betacoeff[k_, 1, _] /; k > 0 := 1/k!;
betacoeff[1, r_, _] := r
betacoeff[k_, r_, L_] := betacoeff[k, r, L] = Sum[betacoeff[i, r - 1,
L]/(k - i)!,
{i, Max[0, k - (L - 1)], Min[k, (r - 1)*(L - 1)]}]
The key is to avoid recomputing the laborious ones by using "dynamic
programmic" (fancy term for saving computed values for later reuse).
Double-check that I've duplicated the function properly while I was
simplifying it!
If you prefer, here's another way to simplify it:
ClearAll@betacoeff
betacoeff[k_, r_, L_] := Which[
k == 0, 1,
r == 1, 1/k!,
k == 1, r,
True, betacoeff[k, r, L] = Sum[betacoeff[i, r - 1, L]/ (k - i)! , {i,
Max[
0, k - (L - 1)], Min[k, (r - 1) (L - 1)]}]
]
Each of those methods took about 11.3 seconds on my machine, and the
answer was:
{{5.000, 0.027040344}, {10.00, 0.049286903}, {15.00, 0.073548480}}
Bobby
help in speeding up code involving a recursive function
Subject: [mg43926] [mg43907] help in speeding up code involving a recursive function
From: "Salman Durrani" <s4001586 at student.uq.edu.au>
To: mathgroup at smc.vnet.net
Organization: The University of Queensland, Australia
Reply-to: "Salman Durrani" <s4001586 at student.uq.edu.au>
Hi,
In the code below, the input variables are L and a.
The code executes correctly and almost instantaneously for L=1 and a=5.
However when I run it for L=2 and a=5, the execution is very slow.
I ran it on a 2.5 GHz machine for L=2 and a=5 for over 48 hours, without
the
execution finishing.
In the end, I was forced to abort the execution.
Can someone please suggest how to speed up the execution.
The code can also be downloaded from
http://www.itee.uq.edu.au/~dsalman/_downloads/test.nb
Thanks in advance.
Salman