Random Number Generator

## A simple full-cycle generator

A full cycle is a mathematical term that represents a traversal over a set of non-random numbers. A full cycle implies that every number in the set was chosen exactly once before repeating.

(ax+b) mod m

is a cyclic code <=>

• b and m are coprime
• a ≡ 1 (mod 4)
• a ≡ 1 (mod p) — for each p is a prime factor of m

## Get random integers in a certain range

The poor way returning numbers from 0 to N-1

```rand() % N        /* POOR */
```

A better method is something like

```(int)((double)rand() / ((double)RAND_MAX + 1) * N)
```

Use only integer operations

```rand() / (RAND_MAX / N + 1)
```

To do something with probability 1/N

```if(rand() < (RAND_MAX+1u) / N)
```

Numbers in the range [M, N] could be generated with something like

```M + rand() / (RAND_MAX / (N - M + 1) + 1)
```

### Note

• Poor pseudo random number generators are not very random in the low-order bits.
• For a pure linear congruential random number generator with period 2e, and this tends to be how random number generators for e-bit machines are written, the low-order n bits repeat with period 2n