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:
> 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

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