February 2016 Archives

Last time we took a look at pseudo random number generators, being entirely deterministic sequences of numbers that pass many of the tests that we might use to try to identify truly random sequences.
Specifically, we considered congruential generators which, starting from an initial value of x₀, known as the seed, follow the rule

  x_i+1 = (a × x_i + c) % m

where x % m is the remainder of integer division of x by m, a is known as the multiplier, c as the increment and m as the modulus.
We saw that we needed to be careful with our choices of the values of a, c, m and x₀ if we wished to construct sequences that approximate randomness, not least that we should choose values for a, c and x₀ that are strictly less than m, and the easiest way to do so is to simply copy those that have stood the test of time.

It is often the case that numerical algorithms require a source of random numbers; we have used them for an, admittedly rather crude, optimisation algorithm and for the selection of initial cluster representatives in the k means clustering algorithm.
The notion of generating random numbers with computers, which are meticulously designed to operate in an entirely predictable manner, is admittedly a rather odd one. One approach is to deliberately design elements of the computer to be extremely sensitive to physical conditions like temperature. Another is to detune a radio and use the noise as a source of randomness. Finally, we might exploit the fundamentally probabilistic nature of the universe as described by quantum mechanics.
Unfortunately, such sources of randomness are typically too slow for general use and we must instead settle for sequences of numbers that are almost random.

Wait, what's that?