The period of a PRNG is how many random numbers you can generate before the sequence starts to repeat. If you don't mind using lower-quality PRNG algorithms, some classic ones (which fell out of favour for good reason) have short periods; for example an LCG can be constructed with any period you want, even for non-power-of-2.
Good quality PRNGs have a period much larger than the bit-space of their output. (Their internal state is wider than one output.) e.g. at least a couple words for a 1-word output, like for fast modern PRNGs such as the xorshift family.
The Mersenne Twister (the usual recommendation for C++: std::mt19937
) has a famously large amount of state to initialize and manage, giving it a period of 219937 − 1. A large period is not the only figure of merit for a PRNG, but a short period is a serious flaw. (https://prng.di.unimi.it/ discusses various factors of PRNG quality, and has a comparison table of periods and which statistical tests are passed/failed by various PRNGs.)
For a PRNG with n
bits of internal state, the maximum possible period is 2n, iterating through every internal state once before repeating. If the output is the entire state, achieving that maximum-period goal would mean generating each number exactly once, which is your requirement. (And some constructions do, although an LFSR can't generate 0).
But then they'd generate each number again in the same order.
More interesting would be a PRNG that could sample every integer in its output range without replacement, and then do it again in a different order, and not just from a different starting point. That's non-trivial.
There are multiple crusty old PRNG algorithms which used to be used to implement functions like C rand()
or random()
which can return their whole state, and have maximal periods for that state.
The linear congruential generator is probably the most famous, where seed = (seed * a + c) % m;
/ return seed;
Generating 0 .. m-1 in a pseudo-random order without replacement
Interestingly, an LCG can be constructed with period m
for any m
. In some cases the sequence isn't very random, e.g. having some obvious patterns in the way they traverse the numbers from 0..m-1, at least with the way I chose to select c
and a
that would ensure a period m
I used this once, when low-quality randomness was acceptable (because nearby integers often had different-enough effects). I just wanted some permutation of the numbers in a 0..n range for rearranging trees via subtree pruning-regrafting aka SPR, to search for a maximum-likelihood tree in phylogenetics. This was a half-finished library that I shared on Github (GPLv2) in case pieces of it were useful.
I don't know if there are better algorithms for doing this for a non-power-of-2 period; this is just what I came up with many years ago, in about 2006.
Another option would be to do something with a period somewhat too long, and discard out-of-range samples. (That could allow avoiding very low-randomness LCGs; see the comments in the code about some bad cases, like when m
has no repeated prime factors.)
I constructed an LCG with m
= the desired period (and output range), and chose c
and a
in a way that created a maximal-period LCG for that modulus. Knuth's The Art of Computer Programming was a useful resource for this.
// GPLv2, copyright Peter Cordes, written in 2006-2007 at Dalhousie University
// while running the computers for the phylogenetics group (math/stats/biology)
struct lcg {
unsigned int state;
unsigned int a, c, m;
unsigned int startstate;
};
int is_prime(int p); // these do what the name implies
int next_prime (int i); // see lcg.c on github for the implementation I copied
/******************** Linear Congruential Generator setup ************/
/* to generate all possible SPRs in a pseudo-random order, we generate
* all the numbers between 0 and the number of possible SPRs once each
* without repetition using an LCG of the form: x_n+1 = x_n*a + c mod m.
*/
/*
* Knuth: TAOCP 3.2.1: ex 2: if a and m are relatively prime,
* the number X_0 will always appear in the period. (will return to start?)
*
* 3.2.1.2: Theorem A: An LCG will have period m iff:
* - c is relatively prime to m
* - b = a-1 is a multiple of p, for every prime p dividing m
* - b is a multiple of 4, if m is a multiple of 4
*
* 3.2.1.3: ex 4: m = 2**e >= 8 -> maximum potency when a mod 8 = 5.
* small multipliers are to be avoided.
*
* Numerical recipies suggests c = a prime close to (1/2 - sqrt(3)/6)*m
*/
/* make up some parameters for an LCG that will have the maximum period
* equal to the range, so every value is generated once.
* When maxval doesn't have any repeated prime factors, a = m+1,
* which is the same as a=1. It's not exactly random, but it does still
* mix up which SPRs are done.
*/
void findlcg(struct lcg *lcg_params, int maxval)
{
unsigned int a, b, c, m = maxval;
int i;
primesetup (maxval+maxval/2);
if (m<=6){ // will be either 6 or 2. Just loop in order
b=0;
c=1;
}else{
int divlimit = m;
b=1; // b must be a multiple of all of m's prime factors
if (!(m%2)){
b=2;
while (divlimit%2 == 0) divlimit /= 2;
}
for (i=3 ; i <= divlimit ; i+=2){
if (is_prime(i) && m%i == 0){
b *= i;
while (divlimit%i == 0) divlimit /= i;
}
}
if (!(m%4)){ // if m is a mult of 4, b must be.
while (b%4) b *= 2;
}
/* make sure a isn't too small */
while (b<sqrtf(m)) b*=7;
if (b == m) b=0; // just give up and avoid overflow
// Numerical Recipies says there is "lore" behind this... :)
// TAOCP says it's useless unless the multiplier sucks (section 3.3.3, eq. 40)
// That would be us.
c = next_prime(max(5, (0.5 - sqrtf(3)/6.0)*m - 2));
while (m%c == 0) c = next_prime(c+1);
// Luckily we don't have to test for c>m, because it doesn't
// happen with any m<100, and there are enough primes later...
/* I've observed that when a == m, (e.g. a=13, c=13, m=72) you often get
* two consecutive numbers... Do something to avoid that if it's a problem */
}
a = b+1;
unsigned long long l = (unsigned long long)a * m;
if (l > ULONG_MAX){
fprintf(stderr, "spr: chosen Linear Congruential Generator is bogus\n"
" x_n+1 = x_n*%u+%u mod %u\n"
" a*m > ULONG_MAX, so it would overflow :(\n", a, c, m);
}
lcg_params->a = a;
lcg_params->c = c;
lcg_params->m = m;
lcg_params->startstate = UINT_MAX;
lcg_params->state = rand() % m; // Linux/glibc rand() is not terrible
}
The actual PRNG function.
I didn't bother with any tricks to speed up the %m
part; this was good enough for a first version.
// startstate = UINT_MAX means we've just started
// UINT_MAX as a return value means we've looped.
unsigned int lcg(struct lcg *lcgp) {
// use long just to avoid overflow on multiply
unsigned long a = lcgp->a, c = lcgp->c, m = lcgp->m;
unsigned long old = lcgp->state;
if (lcgp->startstate == UINT_MAX)
lcgp->startstate = old;
else if (old == lcgp->startstate)
return UINT_MAX;
// will continue to return this until startstate is reset
lcgp->state = (a*lcgp->state + c) % m;
return old;
}
With m
being a power of 2type_width, the modulo is just binary truncation an happens for free. But that results in the low bits of the value having a very short period, e.g. alternating odd/even for the low bit.
Some LCG implementations use a wider state, like 48-bit, and return the high 32 bits of that. So the lowest bit returned doesn't have that short-period problem. (But then you wouldn't have the period = 2output_width property you're looking for.)
rand()
, which is about the worst PRNG in common use, has a 15-bit output and a period of $2^{32}$. $\endgroup$