The expressiveness of Haskell – Random Numbers.

Back in the 1940s the mathematician John von Neumann invented the ‘middle square’ method of generating pseudo random numbers. The algorithm starts with a 4 digit number which is then squared. If the resulting number has fewer than 8 digits then it is padded with leading zeros. From this 8 digit number the middle 4 digits are extracted and returned as the result and also as input to repeating the algorithm.

This implementation, in Haskell, will manipulate the digits of the number as a list and so in outline we need to take the seed number and

square it‘ then ‘convert number to digits‘ then ‘pad to 8‘ then ‘get middle 4‘ then ‘convert digits to number

i.e. we can write a von Neumann Random number generator vnRan as

Starting from the right… sq can be defined as (^2)

numToDigs combines div and mod to extract all the digits of the number.

the pad function is a simple recursive function that prepends ‘0’ until the length is as needed.

The mid4 function uses the substr function written in a previous post. i.e.

and finally digsToNum builds up the number, from a list, using powers of 10.

So there it is, fairly trivial, but does highlight the notion of producing more complex functions by the composition of smaller, simpler functions.
To see it in action we need to use the iterate function to repeatedly apply vnRan like this:

Here is the entire code in one block and I’ve added a main function that uses the system time to seed the vnRan with a ‘random’ 4 digit number.

Anyone playing with this will soon see the sequence quite quickly either repeats or converges to zero and then repeats. This paper modifies the algorithm slightly and overcomes the quick convergence of the sequence and I’ll hopefully post about it soon!

Thanks for reading!

Leave a Reply

Your email address will not be published. Required fields are marked *

ˆ Back To Top