MathGroup Archive 2003

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: How do I get Timing results in Out[]//<Message>?
  • Next by Date: AW: What Happens to Garbage in Mathematica?
  • Previous by thread: help in speeding up code involving a recursive function
  • Next by thread: plotting streamlines from vector data