The first function is the middle square PRNG. Basically, you start with a seed with an even number of digits and then repeatedly square it and return the middle digits.
Here I have a function that will take any suitable seed and generate a sequence of psuedorandom numbers from it:
; middle square PRNG: square the seed and take the middle digits (define (make-middle-square n) (lambda () (let ([digits (inexact->exact (ceiling (log n 10)))]) (let ([res (mod (div (* n n) (expt 10 (/ digits 2))) (expt 10 digits))]) (set! n res) res))))
An example of running it (using the same seed from the Wikipedia page):
~ (define middle-square (make-middle-square 675248)) ~ (middle-square) 959861 ~ (middle-square) 333139 ~ (middle-square) 981593 ~ (middle-square) 524817 ~ (middle-square) 432883
The second example is perhaps even simpler. This time you start with any odd seed and apply the relation xn+1 = 65539 * xn mod 231:
; randu PRNG: x_n+1 = 65539 * x_n mod 2^31 (assume x_0 is odd) (define make-randu (let ([2**31 (expt 2 31)]) (lambda (x) (lambda () (let ([res (mod (* 65539 x) 2**31)]) (set! x res) res)))))
An example run:
~ (define randu (make-randu 675249)) ~ (randu) 1305471251 ~ (randu) 1384299321 ~ (randu) 851521963 ~ (randu) 1240372481 ~ (randu) 1926020867
Pretty neat. Fortunately or not, this makes me want to implement a more heavyweight PRNG now, perhaps like the Mersenne Twister. We’ll see.
If you’d like to download the full source code, you can do so here: two more random exercises source
|← Two Random Exercises||All||Minimum scalar product →|
|← Two Random Exercises||By category||Minimum scalar product →|