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

Reference

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License