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

No comments:

Post a Comment