March 2016 Archives

The Weak, The Inappropriate And The B-D Shuffle

We have been looking at how we might approximate random variables with pseudo random number generators, such as the sequences generated with linear congruences of the form

  xi+1 = (a × xi) % m

where x % m represents the remainder of the integer division of x by m, a is known as the multiplier, c as the increment, m as the modulus and x0 as the seed.
Whilst these are supremely easy to implement and extremely efficient in terms of both speed of execution and use of memory, choosing appropriate values for a, c, m and x0 is a rather difficult proposition; get it wrong and they will produce weak pseudo random numbers and, unfortunately, the ways in which we can do so are extremely subtle.

Full text...