wolfram's random generator

Despite its fundamental simplicity, the rule 30 elementary CA is conjectured to generate a purely random sequence along its center column. It reputably excels at many statistical tests of randomness, and Mathematica includes it as a choice of RNG.

For my own conviction, it was enough to find that 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 assume more pragmatic implementations solve this by perhaps re-seeding the automaton after some number of iterations.

	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 _ = []

view raw rule-30-random-gen.hs hosted with ❤ by GitHub