Simple Random Generators

We all need (pseudo)random numbers sooner or later. Are they hard to generate? Depends. If you want them to be really strong (that is, very random), yes, it’s difficult. If you merely need something random-looking, well, you still need some number theory, but it’s rather not complicated.

roulette

Let’s have a look at three simple types: additive, multiplicative, and the infamous linear congruential generator.

The additive generator, as its name implies, only use addition (and wrap-around) to generate the pseudo-random values. The sequence is given by:

x_n=x_{n+1}+b~(\mathrm{mod~}m)

where m is the modulus, say m=2^{32} on a 32 bits machine (but it could be just about anything else), and b is an integer relatively prime to m. If b is relatively prime to m, that is, if they share no factors, then the above cycles through m distinct values before repeating.

Then you would use x_n\mathrm{~mod~}k for values from 0 to k-1. This generator is particularly simple if the modulus, m, is implicitly taken care of by machine-size registers. Basically, in C you could write:

 unsigned state=seed;
 ...
 state=state+b;

and the machine would wrap around modulo the size of unsigned (whatever it may be for your target architecture).

So why does b has to be relatively prime to m for this to work? Well, we should show that to have z b \equiv 0~(\mathrm{mod~} m), z must be m, because since b and m share no divisors, the first number in the series 0, b, 2b, 3b, ... that is divisible by m is …mb, and all others have remainders (\mathrm{mod~}m).

*
* *

The next one in line is the multiplicative generator, also known as the Lehmer generator and as the Park-Miller generator, is as follows:

x_n= a x_{n-1}~(\mathrm{mod~}m)

where a is a primitive root mod m. The number a (which is not trivial to find) is such that a^1, a^2, \ldots, a^m generate a permutation of 1,\ldots,m! That’s cool but the obvious limitation is that it cannot generate zero, and the algorithms to find a a are not very computationally expensive, but they’re not trivial.

*
* *

The linear congruential generator, the infamous method behind rand() and other generators, combines some of the ideas above to yield a simple generator, one that does not require really hard algorithms to initialize, and that generates a long period.

given by

x_n = ax_{n-1}+b~(\mathrm{mod~}m)

where b is relatively prime to m, and where a must be such that it’s a\equiv{1}~(\mathrm{mod~}p) for all prime factors of m, and if m is a multiple of four, a-1 must also be a multiple of four (or, conversely, a=4k+1 for some k).

The demonstration of this is given by the proof of the Hull-Dobell theorem, and is found, in, say, here (an honors thesis written by a brilliant young woman). If these three conditions are fulfilled, then the generator will have a period of m.

*
* *

A simple C++ implementation would look something like

template <typename T>
class Random
{
 private:

    T state,multiplier,addend;

 public:

    void next() { state=(state*multiplier+addend); }
    operator T() { next(); return state; }

    T get_multiplier() const { return multiplier; }
    T set_multiplier(const T & mult) { return multiplier=mult; }
    T get_addend() const { return addend; }
    T set_addend(const T & add) { return addend=add; }
 
    void seed(const T & seed) { state=seed; }

 Random(T seed=0,
        T mult=1103515245,
        T add=12345)
  : state(seed),
    multiplier(mult),
    addend(add)
  {}
};

This would allows us, unlike C Lib’s rand() to have any number
of distinct random generator instances. Ideally, this class would be a specialization of a ancestor class that provides the interface, but I think it would quickly lead to cases where the common interface would be too simple, especially regarding how the internal state is manipulated and how to get parameters.

We will reuse this thing soon.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: