## Programming Praxis – Rule 30 RNG

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.