Search NKS | Online
61 - 70 of 93 for NestList
![](/common/images/search/spacer.gif)
In the first 200 billion digits, the frequencies of 0 through 9 differ from 20 billion by
{30841, -85289, 136978, 69393, -78309, -82947, -118485, -32406, 291044, -130820}
An early approximation to π was
4 Sum[(-1) k /(2k + 1), {k, 0, m}]
30 digits were obtained with
2 Apply[Times, 2/Rest[NestList[Sqrt[2 + #]&, 0, m]]]
An efficient way to compute π to n digits of precision is
(# 〚 2 〛 2 /# 〚 3 〛 )& [NestWhile[Apply[Function[{a, b, c, d}, {(a + b)/2, Sqrt[a b], c - d (a - b) 2 , 2 d}], #]&, {1, 1/Sqrt[N[2, n]], 1/4, 1/4}, # 〚 2 〛 ≠ # 〚 2 〛 &]]
This requires about Log[2, n] steps, or a total of roughly n Log[n] 2 operations (see page 1134 ).
And with this setup, t steps of evolution can be found with
SSSEvolveList[rule_, init_s, t_Integer] := NestList[(# /. rule)&, init, t]
Note that as an alternative to having s be Flat , one can explicitly set up rules based on patterns such as s[x___, 1, 0, y___] s[x, 0, 1, 0, y] .
The pattern obtained after t steps is then given by
NestList[f[RotateRight[#], #]&, init, t]
The pictures below show results with f being Times , and cells having values (a) {1, -1} , (b) the unit complex numbers {1, , -1, - } , (c) the unit quaternions.
… For n = 2 , the patterns obtained are at most nested. … With a single cell seed, no pattern more complicated than nested can be obtained in such a system.
Block cellular automata
With a rule of the form {{1, 1} {1, 1}, {1, 0} {1, 0}, {0, 1} {0, 0}, {0, 0} {0, 1}} the evolution of a block cellular automaton with blocks of size n can be implemented using
BCAEvolveList[{n_Integer, rule_}, init_, t_] := FoldList[BCAStep[{n, rule}, #1, #2]&, init, Range[t]] /; Mod[Length[init], n] 0
BCAStep[{n_, rule_}, a_, d_] := RotateRight[ Flatten[Partition[RotateLeft[a, d], n]/.rule], d]
Starting with a single black cell, none of the k = 2 , n = 2 block cellular automata generate anything beyond simple nested patterns.
Random walks
In one dimension, a random walk with t steps of length 1 starting at position 0 can be generated from
NestList[(# + (-1)^Random[Integer])&, 0, t]
or equivalently
FoldList[Plus, 0, Table[(-1)^Random[Integer], {t}]]
A generalization to d dimensions is then
FoldList[Plus, Table[0, {d}], Table[RotateLeft[PadLeft[ {(-1)^Random[Integer]}, d], Random[Integer, d - 1]], {t}]]
A fundamental property of random walks is that after t steps the root mean square displacement from the starting position is proportional to √ t . … As mentioned on page 1082 , the frequency spectrum Abs[Fourier[list]] 2 for a 1D random walk goes like 1/ ω 2 .
… To make a random walk on a lattice with k directions in two dimensions, one can set up
e = Table[{Cos[2 π s/k], Sin[2 π s/k]}, {s, 0, k - 1}]
then use
FoldList[Plus, {0, 0}, Table[e 〚 Random[Integer, {1, k}] 〛 , {t}]]
It turns out that on any regular lattice, in any number of dimensions, the average behavior of a random walk is always isotropic.
Continued fractions
The first n terms in the continued fraction representation for a number x can be found from the built-in Mathematica function ContinuedFraction , or from
Floor[NestList[1/Mod[#, 1]&, x, n - 1]]
A rational approximation to the number x can be reconstructed from the continued fraction using FromContinuedFraction or by
Fold[(1/#1 + #2 )&, Last[list], Rest[Reverse[list]]]
The pictures below show the digit sequences of successive iterates obtained from NestList[1/Mod[#, 1]&, x, n] for several numbers x .
… As discovered by Jeffrey Shallit in 1979, numbers of the form Sum[1/k 2 i , {i, 0, ∞ }] that have nonzero digits in base k only at positions 2 i turn out to have continued fractions with terms of limited size, and with a nested structure that can be found using a substitution system according to
{0, k - 1, k + 2, k, k, k - 2, k, k + 2, k - 2, k} 〚 Nest[Flatten[{{1, 2}, {3, 4}, {5, 6}, {7, 8}, {5, 6}, {3, 4}, {9, 10}, {7, 8}, {9, 10}, {3, 4}} 〚 # 〛 ]&, 1, n] 〛
The continued fractions for square roots are always periodic; for higher roots they never appear to show any significant regularities.
Implementation [of basic aggregation model]
One way to represent a cluster is by giving a list of the coordinates at which each black cell occurs. Then starting with a single black cell at the origin, represented by {{0, 0}} , the cluster can be grown for t steps as follows:
AEvolve[t_] := Nest[AStep, {{0, 0}}, t]
AStep[c_] := If[!… With a grid of cells set up in advance, each step in this type of Eden model can be achieved with
AStep[a_] := ReplacePart[a, 1, (# 〚 Random[ Integer, {1, Length[#]}] 〛 &)[Position[(1 - a)Sign[ ListConvolve[{{0, 1, 0}, {1, 0, 1}, {0, 1, 0}}, a, {2, 2}]], 1]]]
This implementation can readily be extended to generalized aggregation models (see below ).
Implementation [of geometric substitution systems]
The most convenient approach is to represent each pattern by a list of complex numbers, with the center of each square being given in terms of each complex number z by {Re[z], Im[z]} . The pattern after n steps is then given by Nest[Flatten[f[#]] &, {0}, n] , where for the rule on page 189 f[z_] = 1/2 (1 - ) {z + 1/2, z - 1/2} ( f[z_] = (1 - ){z + 1, z} gives a transformed version).
In a typical case, each cell is updated using
LFSRStep[list_] := Append[Rest[list], Mod[list 〚 1 〛 + list 〚 2 〛 , 2]]
with a step of cellular automaton evolution corresponding to the result of updating all cells in the register. … The pictures below show the evolution obtained for n = 30 with
NestList[Nest[LFSRStep, #, n]&, Append[Table[0, {n - 1}], 1], t]
Like additive cellular automata as discussed on page 951 , states in a linear feedback shift register can be represented by a polynomial FromDigits[list, x] . … Such generators are directly related to linear feedback shift registers, since with a list of length q , each step is simply
Append[Rest[list], Mod[list 〚 1 〛 + list 〚 q - p + 1 〛 , 2 k ]]
Cryptographic generators.
(Notably, FoldList normally seems more difficult to understand than NestList .)
![](/common/images/search/spacer.gif)