In today’s Programming Praxis exercise, our goal is to write a random number generator based on the Rule 30 cellular automaton. Let’s get started, shall we?

Some imports:

import Control.Monad.State import Data.Bits import Data.Word

First we define the amount of bits in our RNG state.

size :: Int size = 7 * 43

We’re going to be needing a function to convert a list of bits to a number.

fromBits :: (Bits a, Integral a) => [Bool] -> a fromBits = foldl (\a x -> shift a 1 .|. fromIntegral (fromEnum x)) 0

The step function replaces the state with the next generation of cells for a given rule and returns the middle bit.

step :: Monad m => Int -> StateT Integer m Bool step r = modify (\s -> let b i = testBit s (mod i size) in fromBits [ testBit r $ fromBits [b (n+1), b n, b (n - 1)] | n <- [size - 1, size - 2..0]]) >> gets (`testBit` div size 2)

To produce a random number, we take the middle bit of the desired number of generations and convert that to an unsigned integer.

randomBits :: Monad m => Int -> Int -> StateT Integer m Word randomBits n r = return . fromBits =<< replicateM n (step r)

To test the algorithm, we see if we get the correct result when we only set the bit in the middle. Afterwards, we produce a bunch of 8-bit numbers.

main :: IO () main = evalStateT (do r <- randomBits 32 30 liftIO $ print (r == 3112904540) liftIO . print =<< replicateM 100 (randomBits 8 30) ) $ bit (div size 2)

Looks like everything is working properly.