Search NKS | Online
141 - 150 of 210 for Listable
![](/common/images/search/spacer.gif)
(Notably, FoldList normally seems more difficult to understand than NestList .)
The Thue–Morse sequence discussed on page 890 can be obtained from it by applying
1 - Mod[Flatten[Partition[FoldList[Plus, 0, list], 1, 2]], 2]
(b) The n th element is simply Mod[n, 2] .
But rather than trying to give a huge list of specific references, I have instead included in these notes historical information tracing key contributions.
Computing powers [of numbers]
The method of repeated squaring (also known as the binary power method, Russian peasant method and Pingala's method) computes the quantity m t by performing about Log[t] multiplications and building up the sequence
FoldList[#1 2 m #2 &, 1, IntegerDigits[t, 2]]
(related to the Horner form for the base 2 representation of t ). Given two numbers x and y their product can be computed in base k by ( FromDigits does the carries)
FromDigits[ListConvolve[IntegerDigits[x, k], IntegerDigits[y, k], {1, -1}, 0], k]
For numbers with n digits direct evaluation of the convolution would take about n 2 steps.
Sorting networks
Any list can be sorted using Fold[PairSort, list, pairs] by doing a fixed sequence of comparisons of pairs
PairSort[a_, p : {_, _}] := Block[{t = a}, t 〚 p 〛 = Sort[t 〚 p 〛 ]; t]
(Different comparisons often do not interfere and so can be done in parallel.)
Every point in the pattern must correspond to some list of left and right branchings, represented by 0's and 1's respectively; in terms of this list the position of the point is given by Fold[1 + {c, Conjugate[c]} 〚 1 + #2 〛 #1&, 1, Reverse[list]] .
This means, for example, that instead of having to list explicitly all the cells in a run of, say, 53 identical cells, one instead just gives the number "53".
In 1D, a basic form a 〚 i 〛 is just a list.
(Note that even when alkanes are listed in chemical databases—as discussed above—their melting points may not be given.)
With a list s of possible symbols, c[s, n] gives all possible expressions with LeafCount[expr] n :
c[s_, 1] = s; c[s_, n_] := Flatten[ Table[Outer[#1[#2] &, c[s, n - m], c[s, m]], {m, n - 1}]]
There are a total of Binomial[2n - 2, n - 1] Length[s] n /n such expressions.
![](/common/images/search/spacer.gif)