## Monday, February 16, 2015

### wolfram's random generator

The center column of the rule 30 elementary CA: a chaotic bit stream.

The expression sum (take 80 \$ rands 5000) `div` 80 produces 2525.

Since each random bit requires computing a full cell generation, this algorithm quickly slows down. I'd imagine that robust implementations (Mathematica uses this PRNG, among others) re-seed the automaton after every so many bits.

```rands n = map ((`mod` n) . dec) \$ f cells
where
cells  = map mid . tail \$ iterate next [1]
mid xs = xs !! (length xs `div` 2)
f xs   = take 32 xs : f (drop 32 xs)

next = map f . chunk . pad
where
f     = maybe 0 id . (`lookup` rule 30)
pad s = [0,0] ++ s ++ [0,0]

rule = zip ns . bin
where
ns = map (drop 5 . bin) [7, 6..0]

dec = sum . zipWith (*) ns
where
ns = map (2^) [31, 30.. 0]

bin n = map (fromEnum . (`elem` bits n)) pows
where
pows = reverse \$ map (2^) [0..7]

bits 0 = []
bits n = let x = f n in x : bits (n-x)
where
f n = last \$ takeWhile (<= n) \$ map (2^) [0..]

chunk (a:b:c:ns) = [a,b,c] : chunk (b:c:ns)
chunk _          = []
```