Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2005
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2005

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

Search the Archive

Re: Differences between recursions and limit

  • To: mathgroup at smc.vnet.net
  • Subject: [mg60537] Re: Differences between recursions and limit
  • From: Peter Pein <petsie at dordos.net>
  • Date: Tue, 20 Sep 2005 05:18:52 -0400 (EDT)
  • References: <dgm01k$njm$1@smc.vnet.net>
  • Sender: owner-wri-mathgroup at wolfram.com

anbra1 schrieb:
> Please,
> I want to know
> why these two recursions,doing the same thing,
> are the first one much more slow than the second
> 
> -------------------------
> 
> x[0]=0;
> x[k_] := .25 *(1 + x[k-1] + (x[k-1])^2 + (x[k-1])^3);
> 
> For[k=1,k<12,Print[k," ",SetPrecision[x[k],30]];k++]
> 
> -------------------------
> 
> a=0;
> 
> For[k=1,k<12,k++,
> 
> b= .25 (1 + a + a^2 + a^3);a:=b;Print[k," ",SetPrecision[b,30]]]
> 
> -------------------------
> Another question
> How can I calculate
> the limit of this recursion for k->Infinite ?
> Thank you all
> 
> 
Hi,

your recursive version invokes more than a million function calls:

x[0] := (calls++; 0);
x[k_Integer /; k > 0] :=
  (calls++; 0.25*(1 + x[k - 1] + x[k - 1]^2 + x[k - 1]^3));

calls = 0;
{ti, tb} = Timing[Table[x[i], {i, 12}]]
calls
calls*("Calls"/ti)

-->
{4.641*Second, {0.25, 0.33203125, 0.3697201758623123,
0.3892378368553577, ... , 0.41388606703854386}}

1195734
257645.76599870718 Calls/Second

There are at least two possibilities to speed things up:

1.) use only one recursive call:

y[0] := (calls++; 0);
y[k_Integer /; k > 0] :=
   (calls++;
   (0.25*((#1^4 - 1)/(#1 - 1)) & )[y[k - 1]]);
calls = 0;
{ti, tb} = Timing[Table[y[i], {i, 12}]]
calls

-->
{0.*Second, {0.25, ... , 0.4138860670385438}}

90

2.) remember already calculated values:

z[0]:=(calls++;0);
z[k_Integer/;k>0]:=z[k]=(calls++;(.25(#^4-1)/(#-1))&[z[k-1]]);

calls=0;
Timing[Table[z[i],{i,12}];]//First
calls

-->

0.*Second
13

________________________

It makes no sense to set the precision of a number which has been
calculated with machine-precision to a higher value in the output.
________________________

To get the limit up to 30 decimal places, use

FixedPoint[N[(#^4 - 1)/(# - 1)/4, 30] &, 0] // Timing

-->
{0. Second, 0.414213562373095048801688724209}

well, one could guess...


N[Sqrt[2]-1,30]==Last[%]

  True

to verify this:

a = Sqrt[2] - 1;
Simplify[1 + a + a^2 + a^3]/4

  -1 + Sqrt[2]

Ciao,
Peter


-- 
Peter Pein, Berlin
GnuPG Key ID: 0xA34C5A82
http://people.freenet.de/Peter_Berlin/


  • Prev by Date: "layering" 2d plots
  • Next by Date: Re: 'Changing' parameters in an expression
  • Previous by thread: Re: Differences between recursions and limit
  • Next by thread: Re: Differences between recursions and limit