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/