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 2
^{e}, and this tends to be how random number generators for e-bit machines are written, the low-order n bits repeat with period 2^{n}