CODEWITHSUNDEEP
random
a06e
a06e

Reputation: 20794

Generate random numbers without repetition (or vanishing probability of repetition) without storing full list of past generated numbers?

I need to generate random numbers in a very large range, 128 bits integers, and I will generate a many many of them. I'll generate so many of them, that I cannot fit into memory a list of the numbers generated.

I also have the requirement that the generated numbers do not repeat, or at least that the probability of repetition is vanishingly small.

Is there an algorithm that does this?

Upvotes: 0

Views: 78

Answers (2)

sh1
sh1

Reputation: 4763

Any full-period PRNG with a 128-bit state will do what you need in principle. Unfortunately many of these generators tend to produce only 32 or 64 bits per iteration while the rest of the state goes through a predictable permutation (LFSRs being the worst case, producing only 1 bit per iteration). Each 128-bit state is unique, but many of its bits would show a trivial relation to the previous state.

This can be overcome with tempering -- taking your questionable-quality PRNG state with a known-good period, and permuting it through a 1:1 transform to hide the not-so-random factors.

For example, borrowing from the example xorshift+ shown on Wikipedia:

static uint64_t s[2] = { 1, 0 };

void random128(uint64_t result[]) {
  uint64_t x = s[0];
  uint64_t y = s[1];

  x ^= x << 23;
  x ^= y ^ (x >> 17) ^ (y >> 26);

  s[0] = y;
  s[1] = x;

At this point we know that s[0] is just the old value of s[1], which would be a terrible PRNG if all 128 bits were exposed (normally only s[1] is exposed). To overcome this we permute the result to disguise that relationship (following the same principle as a feistel network to ensure that the transform is 1:1).

  y += x * 1630144151483159999;
  x ^= y >> 3;

  result[0] = x;
  result[1] = y;
}

This seems to be sufficient to pass diehard. So long as the original generator has full(ish) period, the whole generator should be full period too.

The logical conclusion to tempering a low-quality generator is to use AES-128 in counter mode. Simply run a counter from 0 to 2**128-1 (an extremely low-quality generator), and encrypt each value using AES-128 and a consistent key (an ideal temper) for your final output.

If you do this, don't get distracted by full cryptographic RNG requirements. Those involve re-seeding and consequently can produce the same number more than once (which is more random, but it's what you want to avoid).

Upvotes: 0

pjs
pjs

Reputation: 19855

Build a 128 bit linear congruential generator or linear feedback shift register generator. With properly chosen coefficients either of those will achieve full cycle, meaning no repeats until you've exhausted all outcomes.

Upvotes: 0

Related Questions