Recently in Random Category

Halton, Here's A Pseud

Last time we came across the concept of quasi random sequences whose terms progressively fill intervals as evenly as possible, as contrasted with pseudo random number generators which give equal likelihood to numbers within them being produced.
Now it will occasionally be the case that we should prefer to use quasi random sequences in place of pseudo random number generators and to do so we shall need to present an interface to the former that exactly matches that of the latter.

Full text...

submit to reddit  

Let's Twist Again

In the last few posts we have been looking at linear feedback shift registers, or LFSRs, which generate random bits from a buffer by taking the rightmost bit as the output, shifting the buffer one bit to the right and, if the output is one, applying an exclusive or operation with a set of bits known as taps. Since the leftmost bit is always one of the taps, they effectively shift the output bit back into the leftmost bit of the buffer.
We saw that despite looking completely different to the congruential generators that we covered earlier, they are surprisingly similar, not least in that we must be extremely careful when setting them up if we want to generate sequences of bits that take as long as possible to enter into a cycle.
Finally, we noted that it was possible to generalise LFSRs so that they generate numbers rather than bits, which we shall do in this post.

Full text...

submit to reddit  

Shifting Up A Gear

Last time we took a look at linear feedback shift registers, or LFSRs, which produce pseudo random bits by shifting a buffer of them to the right, with the rightmost becoming both the output and the leftmost bit which being combined with a subset of the bits, known as taps, using an exclusive or operation.
We saw that despite looking completely different to the linear congruential generators that we covered a few posts ago they are in fact rather similar to them, albeit involving multiplication and remainder operations involving polynomials rather than integers.
Unfortunately, another thing that LFSRs have in common with linear congruential generators is that it is extremely difficult to set them up so that they generate sequences of bits that are as close to random as possible. Thankfully, there are those who've gone to the trouble of finding decent choices for the taps for us and so all that we need to concern ourselves with is implementing them, which we shall do in this post.

Full text...

submit to reddit  

Get A Shift On

We have seen how we can approximate random variables with linear congruences of the form

  xi+1 = a × xi + c % m

where x % m is the remainder of the integer division of x by m. If we are careful with our choices of the seed x0, the multiplier a, the increment c and the modulus m then they can generate sequences of pseudo random numbers that, whilst wholly deterministic, pass many of the statistical tests for randomness.
These are not the only kind of recurrences that we can use to generate pseudo random numbers, however.

Full text...

submit to reddit  

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...

submit to reddit  

Talkin' 'Bout My Generators

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 x0, known as the seed, follow the rule

  xi+1 = (a × xi + 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 x0 if we wished to construct sequences that approximate randomness, not least that we should choose values for a, c and x0 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.

Full text...

submit to reddit  

Pseudo Algorithmical

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?

Full text...

submit to reddit