Is there a PRNG that visits every number exactly once, in a non-trivial bitspace, without repetition, without large memory usage, before it cycles?

Question

PRNGs (pseudorandom number generators) generally have a bit length for the binary numbers they generate (e.g. 32 bits, 64 bits). This is the universe of their possible numbers.

It seems that they typically cycle when they reach their 2^bitlen number.

Is there one that, before it cycles, will generate each possible number in its universe, exactly once, without repetition, for larger bitspaces (e.g. 64, 128, 256), without large memory requirements (such as storing numbers generated so far, or a shuffled list of future numbers).

Another way to put this: Is there an algorithm than exhaustively “traverses” or “visits” each binary number in a bitspace, exactly once, in a pseudorandom order? (with large bitspace and low memory usage, as above)

EDITS:

I now have the impression that, while PRNGs do typically eventually cycle (repeat their sequence), the point at which one cycles is specific to the algorithm, and is usually NOT after 2^bitlen numbers (where bitlen is the size in bits of their binary output). Please correct this if wrong.

I expect that a PRNG is still a PRNG if it generates a duplicate number (within its period, before it cycles), or if it never generates (within its period) some numbers that are possible in the bitspace of its output. I'm not looking for these kinds.

I'm looking for an algorithm that works as if it's just reading off N-bit binary numbers from a massive randomly-shuffled list of all N-bit binary numbers, but without the massive memory requirement of such a list.

I'm interested in algorithms meeting this criteria that are pseudorandom in a cryptographically-secure way, and also those not cryptographically-secure that are quicker or simpler.

Answer 1

Sure. Pick a block cipher (i.e., pseudorandom permutation), $E_K$, and a random key for it, $K$. Let $x_i=E_K(i)$. Then this has the properties you are looking for.

Short explanation:

As the block cipher $E_K$ maps each n-bit value uniquely to another n-bit value, all the resulting values must be different for different input values. Effectively that means $E_K$ creates a permutation of n-bit values that can be varied by changing $K$.

Answer 2

A linear-feedback shift register (LFSR) is a terrible PRNG(*), but (with correct selection of feedback taps) it seems to meet all your qualifications.

A LFSR can run extremely fast -- faster than standard natural binary counters.

Is there one that, before it cycles, will generate each possible number in its universe, exactly once, without repetition, for larger bitspaces (e.g. 64, 128, 256), without large memory requirements (such as storing numbers generated so far, or a shuffled list of future numbers).

With a proper selection of feedback taps, a standard n-bit LFSR produces a "maximum length sequence", producing 2^n-1 output values (all possible output values, except for the all-zeros value, without repetition until it cycles back to the first value). There are a variety of techniques for tweaking the system to add that one final value all-zeros, so it produces all possible n-bit values. The only memory required is the n-bit current state of the LFSR. (A little more memory may be required if you want it to halt after it's cycled through all 2^n-1 values without repetition).

For example (based on http://users.ece.cmu.edu/~koopman/lfsr/ ):

#include <stdint.h>
#include <inttypes.h>
// David Cary
uint64_t next_LFSR64(){
  static uint64_t i = UINT64_C(1); // or any other non-zero value
  #define feed (UINT64_C(800000000000000D)
  // a few other special values of feed will also produce MLS, including:
  // #define feed (UINT64_C(800000000000000E)
  // #define feed (UINT64_C(800000000000007A)

  if (i & 1)  { i = (i >> 1) ^ feed; }
  else        { i = (i >> 1);       }
  return i;
};

will produce a maximum-length sequence of all possible 64-bit values (except the 0 value) without repetition until it cycles back to the initial value.

In principle (from a table from Roy Ward and Tim Molteno), a feedback term of

const uint256_t feed =
    (UINT256_C(1)<<255) + 
    (UINT256_C(1)<<253) + 
    (UINT256_C(1)<<250) + 
    (UINT256_C(1)<<245); // warning: untested.
static uint256_t i = UINT256_C(1); // or any other non-zero value

would in theory produce all possible 256-bit values except all-zeros, but of course our Sun won't last that long.

(*) From a cryptographic point of view, we want random-number generators and PRNGs to generate numbers that are very difficult for any attacker to guess ahead of time, even if that attacker has seen the previous thousand or so output values of that generator. The Berlekamp-Massey algorithm makes it easy to guess the next output of a LFSR given practically no information about the size of the LFSR and surprisingly few output values of the LFSR. Fortunately for cryptographers, cryptographically strong PRNGs exist which are immune to the Berlekamp-Massey algorithm. For example, all good stream ciphers use cryptographically strong PRNGs.

Answer 3

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 2¹⁹⁹³⁷ − 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 2ⁿ, 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 2^type_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 = 2^output_width property you're looking for.)

Answer 4

What is your intended application?

Apart from PRNGs, there are also quasirandom sequence generators. They are (almost certainly) not cryptographically secure, but have other desirable properties. From mathworld:

A sequence of n-tuples that fills n-space more uniformly than uncorrelated random points, sometimes also called a low-discrepancy sequence. [...] useful in computational problems where numbers are computed on a grid, but it is not known in advance how fine the grid must be to obtain accurate results. Using a quasirandom sequence allows stopping at any point where convergence is observed, [...]

They are useful in numerical integration, for example.