Today we get away from the word games for a little while and get back to talking about random number generators (previous posts here and here). Or rather one random number generator in specific: a Rule 30 psuedo-random number generator (PRNG). (Here’s the motivating post from Programming Praxis.)
Remember the previous post I made about cellular automaton? The basic idea is to turn those into a random number generator. If you go back to the linked post in particular and give it Rule 30 with a random initial state, you can see how chaotic the rows seem to be. Perfect for a PRNG.
So how do we go about it?
First, since everything we’re about to do deals with bits at some level or another, we want a pair of functions that can convert from binary to decimal and vice versa. Easy enough:
; convert a decimal number to a binary list
; 10 => '(1 0 1 0)
(define (dec->bin d)
(reverse
(let loop ([d d])
(if (= d 0)
'()
(cons (remainder d 2) (loop (quotient d 2)))))))
; convert a binary list to a decimal number
; '(1 0 1 0) => 10
(define (bin->dec b)
(let loop ([b (reverse b)] [p 1])
(if (null? b)
0
(+ (* (car b) p) (loop (cdr b) (* p 2))))))
But that doesn’t help if we have a number like 10 and we really need an 8-bit binary state. So one more function that will pad the width out to the correct length.
; pad a list out to a given length with a given value
(define (pad-to n ls with)
(append (make-list (- n (length ls)) with) ls))
Yes, it’s inefficient with calls to append and length, but with how little it’s going to be used, it’s all good.
With that, we’re just about there. The goal will be to set up the state in an initial function and then return a thunk that will return each random number in turn. To do that, we’ll loop across the internal state, updating each value according to the rule. Unfortunately, the edge cases are going to be a little problematic, so we’re just going to wrap the references around so that a negative indexes start off the right end and too large indexes come back around to the left.
; wrap the edges of a vector around rather than returning an error
(define (wrapped-vector-ref v i)
(vector-ref v (remainder (+ i (vector-length v)) (vector-length v))))
Okay, we’re golden. Let’s see if we can turn that into a function:
; create a new random number generator
; rule is the rule to use to generate the next state
; width is the number of bits in the generator
; seed is the initial value for the generator
(define (make-rng [rule 30] [width 32] [seed #f])
; start by converting the initial state into an internal vector
; and the rule into a function that will convert states
(let ([state
(list->vector
(pad-to width
(if seed
(dec->bin seed)
(for/list ([i width]) (random 2)))
0))]
[rule
(let ([rule (list->vector (reverse (pad-to 8 (dec->bin rule) 0)))])
(lambda (a b c)
(vector-ref rule (+ (* 4 a) (* 2 b) c))))])
; return a thunk that will generate each number
; calculate the next state, store it, and return a decimal version
(lambda ()
(define next
(for/vector ([i width])
(rule (wrapped-vector-ref state (- i 1))
(wrapped-vector-ref state i)
(wrapped-vector-ref state (+ i 1)))))
(set! state next)
(bin->dec (vector->list next)))))
A few interesting parts.
First, we have default parameters. I really like this about Racket and miss it when I move back to other Schemes. In this case, you can call make-rng with 0, 1, 2, or 3 parameters. As noted in the comments, the first parameter controls the rule that we’ll use to update the state (the eponymous Rule 30 by default), the second sets the width of the internal state in bits (set to a 32-bit integer by default), and the third sets the initial value (if it’s not specified, generate random bits using a more traditional method).
The next interesting part is the mess I made of the rule variable. It starts as a decimal version of the rule, but is quickly changed first into a binary vector:
(let ([rule (list->vector (reverse (pad-to 8 (dec->bin rule) 0)))])
...)
After that, we turn it into a three-argument function, taking the left, center, and right bits above it and returning the bit that we want. Perhaps it’s not optimal, what with all three variables having the same name, but since they all represent the same thing and we won’t be using the original version, it seems reasonable.
The final part is calculating the next state each time. As I’ve said before, Racket’s for family of macros is all sorts of fun.
(for/vector ([i width])
(rule (safe-vector-ref state (- i 1) 0)
(safe-vector-ref state i 0)
(safe-vector-ref state (+ i 1) 0)))
And that’s it, we’re good to go. Let’s go ahead and give it a try, making a 32-bit Rule-30 generator:
> (define rule-30-rng (make-rng 30 32))
> (for/list ([i 20]) (rule-30-rng))
'(2081921567 3258217264 2808532712 3160193164 2731779546
3063823635 2767282622 3213579041 2690277107 2966671502
2845710809 2943432471 2823546036 2902073254 2877501501
2856773729 2884406483 2852903838 2870612593 2863873995)
Some rules are a bit less interesting:
> (define rule-220-rng (make-rng 220 32))
> (for/list ([i 20]) (rule-220-rng))
'(3181303643 3185497947 3185497947 3185497947 3185497947
3185497947 3185497947 3185497947 3185497947 3185497947
3185497947 3185497947 3185497947 3185497947 3185497947
3185497947 3185497947 3185497947 3185497947 3185497947)
Still, it’s not bad from at least a theoretical point of view.
You can also make smaller generators:
> (define rule-30-small-rng (make-rng 30 8))
> (for/list ([i 20]) (rule-30-small-rng))
'(237 137 223 144 248 132 206 185 167 188
162 183 164 190 161 179 174 169 175 168)
Or significantly larger ones:
> (define rule-30-large-rng (make-rng 30 32))
> (for/list ([i 4]) (rule-30-large-rng))
'(89023152286745644506872318191753884006989667221527067666095402290895880008920
79429241104291927956174027620442798020819263458393486404866413705199432492948
76190546924302348594483004811252023470674220283715618311175239657740025994358
78165092849222814468761907530085892160685112152512879137896641918045191418565
77670707617636225778606052617006557506563209338194205599967259022343124184749)
It’s all good.
I wouldn’t at all recommend using this for anything that needs even semi-secure random numbers, but at the very least it’s interesting as a thought experiment.
If you’d like the entire source code, you can access it here: