       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)
• 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

{{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.