MathGroup Archive 2007

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

Search the Archive

Re: Better recursive method?

  • To: mathgroup at smc.vnet.net
  • Subject: [mg72826] Re: [mg72802] Better recursive method?
  • From: danl at wolfram.com
  • Date: Sun, 21 Jan 2007 05:53:45 -0500 (EST)
  • References: <200701200824.DAA10469@smc.vnet.net>

> Hallo:
>
> I have following recursive functions:
> pi(i, theta) := (2n-1)/(n-1) cos(theta) pi(i-1, theta) - n/(n-1)
> pi(i-2,theta)
> tau(i,theta) := n pi(i, theta) - (n+1) pi(i-1,theta)
>
> with intial values:
> pi(0,theta) := 0
> pi(1,theta) := 1
>
> These should calculate the following function:
> S1(theta) := sum(i=1-nstop) (2i+1)/(i(i+1)) (a(i) pi(i,theta) - b(i)
> tau(i,theta)) (where nstop=40)
>
> This should be pretty easy to calculate for Mathematica. I have written
> it the following way:
> pi[0,theta] := 0;
> pi[1,theta] := 1;
> pi[i_, theta_] := pi[i, theta] =(2n-1)/(n-1) Cos[theta] pi[i-1, theta]
> - n/(n-1) pi[i-2,theta]
> tau[i_,theta_] := n pi[i, theta] - (n+1) pi[i-1,theta]
> S1Temp[i_,theta_] := (2i+1)/(i(i+1)) (a[i] pi[i,theta] - b[i]
> tau[i,theta])
> S1(theta) := Sum[ S1Temp[i,theta], {i, 1, nstop}]
>
> Well, it works fine, but it takes enormous time. I have introduced
> recursive function to save time for calculation of Legendre Polynomials
> of which the function 'pi' and 'tau' consist of. But the same function
> if I write with 2 loops each for 'theta' and 'i' in IDL, it calculates
> in fraction of a second. Even the simple calculation of 'pi[40,pi/4]'
> took more than 350 seconds.
>
> What could be the problem in my logic. Is there any other better way to
> write recursive functions in Mathematica?
>
> Any help will be appreciated!
>
> Regards,
> nandan
>



It looks generally reasonable to me. What hits hard is the complexity
growth in i. For the example at hand it can be reduced considerably with
Together.

pi[i_, t_] :=
 pi[i, t] =
  Together[(2*n - 1)/(n - 1)*Cos[t]*pi[i - 1, t] - n/(n + 1)*pi[i - 2, t]]

This cuts the computation time considerably.

In[44]:= Timing[ss=S1[Pi/4];]
Out[44]= {0.344 Second,Null}

Another possibility is to find a closed form for pi[] using RSolve.

In[49]:=InputForm[
  RSolve[{p2[i]==(2*n-1)/(n-1)*Cos[t]*p2[i-1]-n/(n+1)*p2[i-2],
   p2[0]\[Equal]0,p2[1]\[Equal]1},p2[i],i]]
Out[49]//InputForm= {{p2[i] ->
   -(((-1 + n^2)*(((-Cos[t] + n*Cos[t] + 2*n^2*Cos[t] -
          Sqrt[-4*(-1 + n^2)*(-n + n^2) + (Cos[t] - n*Cos[t] -
              2*n^2*Cos[t])^2])/(-1 + n^2))^i -
       ((-Cos[t] + n*Cos[t] + 2*n^2*Cos[t] +
          Sqrt[-4*(-1 + n^2)*(-n + n^2) + (Cos[t] - n*Cos[t] -
              2*n^2*Cos[t])^2])/(-1 + n^2))^i))/
     (2^i*Sqrt[-4*(-1 + n^2)*(-n + n^2) +
        (Cos[t] - n*Cos[t] - 2*n^2*Cos[t])^2]))}}

This can now be used to construct your sum.

Daniel Lichtblau
Wolfram Research



  • Prev by Date: Re: how to quickly read a >10MB big file
  • Next by Date: Re: Better recursive method?
  • Previous by thread: Better recursive method?
  • Next by thread: Re: Better recursive method?