CHAPTER 20. LINEAR CONGRUENTIAL GENERATOR CHAPTER 20. LINEAR CONGRUENTIAL GENERATOR

Chapter 20

Linear congruential generator as pseudorandom

number generator

The linear congruential generator is probably the simplest possible way to generate random numbers. It’s not in favour in
modern times^1 , but it’s so simple (just one multiplication, one addition and one AND operation), we can use it as an example.

#include <stdint.h>

// constants from the Numerical Recipes book
#define RNG_a 1664525
#define RNG_c 1013904223

static uint32_t rand_state;

void my_srand (uint32_t init)
{
rand_state=init;
}

int my_rand ()
{
rand_state=rand_state*RNG_a;
rand_state=rand_state+RNG_c;
return rand_state & 0x7fff;
}

There are two functions: the first one is used to initialize the internal state, and the second one is called to generate
pseudorandom numbers.

We see that two constants are used in the algorithm. They are taken from [Pre+07]. Let’s define them using a#define
C/C++ statement. It’s a macro. The difference between a C/C++ macro and a constant is that all macros are replaced with
their value by C/C++ preprocessor, and they don’t take any memory, unlike variables. In contrast, a constant is a read-only
variable. It’s possible to take a pointer (or address) of a constant variable, but impossible to do so with a macro.

The last AND operation is needed because by C-standardmy_rand()has to return a value in the 0..32767 range. If you
want to get 32-bit pseudorandom values, just omit the last AND operation.

20.1 x86

Listing 20.1: Optimizing MSVC 2013

_BSS SEGMENT
_rand_state DD 01H DUP (?)
_BSS ENDS

_init$ = 8
_srand PROC
mov eax, DWORD PTR _init$[esp-4]
mov DWORD PTR _rand_state, eax

(^1) Mersenne twister is better