Introduction

Although the algorithms for some random number generators are very simple, they can still be tricky to implement correctly, especially in a way which portable across different compilers and architectures. In addition, any bugs which are introduced may not be immediately obvious and can be quite difficult to track down. Therefore, the first and foremost point to note is that you should not attempt to write you own generator from scratch unless you have some extremely specialised requirements.

Instead, it is best to rely on one of the high-quality, publicly available codes that are now available with very permissive licenses and which you can use in your application.

The second point to note early on is that the standard system C library random number generators are not typically suitable for numerical applications and should not be used. Their main problems are that:

• The design as well as the implementation are system dependant and non-standard
• The precision of output and the size of internal states may be as short as 16 bits
• The standard library generators normally can not properly handle multi-threaded programs

Main concepts

A basic algorithm for generating (pseduo-)random numbers consists of three parts:

1. The initial state of the algorithm
2. The procedure to advance from current state to the next one in the sequence
3. The procedure to derive one or more useful random numbers from the current state

In some algorithms the random number derived from the state is the state itself, but this is not necessarily the case. One of the reasons for this distinction is that information capacity of the state determines the maximum possible length before the numbers produced by the generator start to repeat (i.e., the cycle length). For example with a 32-bit state, the random numbers must start to repeat after a maximum of calls to the generator (if you think this is long enough, see Short cycle length).

In order to extend the maximum cycle, the states used in modern algorithms are often much longer than 32 bits (e.g., 256 or 624 bits) and a several random numbers are derived from each state of the generator before it is advanced to the next one in the sequence.

The initial state of the algorithm is specified by a process called seeding. This process is normally as simple as supplying a 32-bit or 64-bit number which is then either further processed by utility functions to create the initial state or is the initial state by itself. The sequence of numbers generated by the algorithm after seeding with the same data is of course always identical.