## Rule 30 RNG

### April 29, 2011

We have examined several different random number generators in past exercises, including Donald Knuth’s lagged-fibonacci generator that is used in the Standard Prelude. We also looked at cellular automata in a previous exercise. In today’s exercise we combine random number generators and cellular automata by looking at a random number generator developed by Stephen Wolfram, based on the Rule 30 cellular automaton of his book A New Kind of Science. Our random number generator will be similar to that in Mathematica; it is not cryptographically secure, but is suitable for simulation, as long as you avoid the occasional bad seed, like 0.

The cellular automata we are discussing have a state consisting of a row of cells; each cell can be in either of two states, 0 or 1. Unlike the cellular automata of the previous exercise, the row contains a finite number of cells and is considered to “wrap around” at the ends. A new state is generated based on the current state by assigning to each cell in the new state a value determined by the same-indexed cell in the previous state as well as the two cells immediately adjacent to it. The chart below shows the rule that determines the cell value in the new state:

 ■ ■ ■ ■ ■ □ ■ □ ■ ■ □ □ □ ■ ■ □ ■ □ □ □ ■ □ □ □ □ □ □ ■ ■ ■ ■ □

The name Rule 30 comes from the binary-to-decimal conversion of the new values in each of the cells. Taking the same-indexed cell in each successive state gives a sequence of random bits; collect enough of them and you can convert them to a number.

In Wolfram’s book, the various cellular automata are studied based on an infinite row that starts with a single 1-cell, with all remaining cells having a value of 0; the successive states of that cellular automaton are shown in the image above-right. In a random-number generator, the initial state is seeded with 1s and 0s in some user-defined pattern.

Your task is to write a random-number generator based on the Rule 30 cellular automaton. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

### 9 Responses to “Rule 30 RNG”

1. [...] today’s Programming Praxis exercise, our goal is to write a random number generator based on the Rule 30 [...]

2. My Haskell solution (see http://bonsaicode.wordpress.com/2011/04/29/programming-praxis-rule-30-rng/ for a version with comments):

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

size :: Int
size = 7 * 43

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

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)

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

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

Don’t really know if I understand algorithm, but here is my attempt in python:

```#!/usr/bin/python3

from math import log, floor
from functools import reduce

lst_lookup = [1, 1, 1, 0, 0, 0, 0, 1]

(state, iterations) = 123456789, 5
size = floor(log(state, 2)) + 1
main_index = size // 2

def gen_states2(n):
cur_state = state
for i in range(0, n):
print([int((cur_state & (1 << i)) != 0) for i in range(size - 1, -1, -1)])
yield cur_state

cur_state = (cur_state << 1) | ((cur_state & 1) << (size + 1)) | (cur_state & (1 << (size - 1))) >> (size - 1)
cur_state = reduce(lambda x, y: x + (lst_lookup[(cur_state >> y) & 7] << y), range(0, size))

print(reduce(lambda x, y: x * 2 + y, [((i >> main_index) & 1) for i in gen_states2(iterations)], 0))
```

Not the most efficient, but I wanted to look at python’s bitwise capabilities and to play with all that funky stuff Graham uses all the time :D
Basically I use simple number as a state (each binary digit represents cell) and then use gen_state2 to generate all the preceding states.

```[1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1]
[1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0]
[0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0]
[1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0]
[0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0]
4
```
4. Mike said

Implemented a Rule30 class. An instance of the class can be called like a function to return the next random number. The class also supports the iteration protocol.

The basic strategy is to store the state of the rng in an integer. left and right are the state rotated 1 bit to the right and left, respectively, so the three bits that make up the next state “line up”. Then a boolean expression involving left, state and right is used to calculate the next state.

The LSBs of the state are accumulated to determine the random number

```from random import randint

class Rule30:
def __init__(self, seed=None, nbits=32):
self.mask  = 2**(2*nbits) - 1
self.nbits = nbits
self.shift = 2*nbits - 1

self.state  = seed or randint(1,self.mask)

def __call__(self):
val = 0

for n in range(self.nbits):
left  = (self.state >> 1 | self.state << self.shift) & self.mask
right = (self.state << 1 | self.state >> self.shift) & self.mask

self.state = ~left&self.state | ~self.state&(left^right)

val = val<<1 | self.state&1

return val

def __iter__(self):
return self

next = __call__

# examples
from itertools import islice

# using an instance as an iterable/generator
for n in islice(Rule30(),10):
print n

# calling an instance
rng = Rule30(3495872309)
rng()
```
5. David said

Forth version. We take a 30 bit number, prep it by shifting once left and wrapping the bits. Each iteration of the loop, use table to look up the value of current bit based on three bits in original word.

```\ 30 bit random

create state-trans
1 C,  1 C,  1 C,  0 C,  0 C,  0 C,  0 C,  1 C,

: prep  ( n -- n )  \ takes 30 bit number, wraps around low bit & high bit
\$3FFFFFFF and 1 lshift
dup \$00000002 and IF \$80000000 or THEN
dup \$40000000 and IF \$00000001 or THEN ;

: rng30 ( n -- n )
0 locals| result |
prep 7
30 0 DO
2dup and i rshift state-trans + c@
i lshift result or  to result
2*
LOOP
2drop result ;

create seed  counter \$3FFFFFFF and ,
: random-30
seed @  dup rng30  seed ! ;

: .30bin
base @ >r  2 base !
0 <# 30 0 do # loop #> type space
r> base ! ;
```

Session:

```include rng30  ok
random-30 .30bin 000000111001010111100101100100  ok
random-30 .30bin 111111010011010011001100001101  ok
random-30 .30bin 111110010100010100010001110000  ok
random-30 .30bin 011100110101110101110110100111  ok
random-30 .30bin 001001000100100100100000101010  ok
random-30 .30bin 111011011101101101101111101010  ok
random-30 .30bin 010000001000000000000111001010  ok
random-30 .30bin 110111111011111111111010011010  ok
random-30 .30bin 000011110001111111110010100010  ok
random-30 .30bin 111101100110111111100110101110  ok
```
6. Graham said

@arturasl, you flatter me. As for me, here’s my Python solution.
Perhaps not as elegant as others, but I wanted to play with Python’s bitarrays for speed.

7. Graham said

@arturasl: I just try to make my Python solutions get anywhere near the great functional programming
we see in the “official” solution and in the Haskell ones @Remco posts :-)

8. JP said

That was pretty neat. I’m not sure how valuable it is as a RNG, as there are easier to code RNGs that seem more random (heck, this post from here at Programming Praxis even) but as a thought experiment it’s worthwhile. And it gave me a chance to build on the cellular automaton code I’d previously built in JavaScript and transfer that to Racket.

In any case, here’s my Racket version: Rule 30 RNG

9. [...] number generator in specific: a Rule 30 psuedo-random number generator (PRNG). (Here’s the motivating post from Programming [...]