Skip to content

Instantly share code, notes, and snippets.

@steveash
Last active February 17, 2023 23:05
Show Gist options
  • Star 8 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save steveash/fe241f54aa6d7fb73da9 to your computer and use it in GitHub Desktop.
Save steveash/fe241f54aa6d7fb73da9 to your computer and use it in GitHub Desktop.
Pseudo-random generator that doesn't repeat integers
import java.util.Random;
/**
* Generates a sequence of pseudo-random numbers such that they never repeat. Can handle sequence sizes up to
* length Int.MAX_VALUE. Will throw exceptions if you ask for more than that; maps the entire [0, Integer.MAX_VALUE]
* range onto itself but in a random order
* <link>http://preshing.com/20121224/how-to-generate-a-sequence-of-unique-random-integers/</link>
*/
public class PreshingRandomSequence {
public static final int MAX_INT_PRIME = 2147483587;
private final Random rand;
private final long seed1; // these are longs so that it will implicitly widen and not overflow
private final long seed2;
private long index;
public PreshingRandomSequence() {
this(new Random());
}
public PreshingRandomSequence(long seed) {
this(new Random(seed));
}
private PreshingRandomSequence(Random random) {
this.rand = random;
this.index = 0;
this.seed1 = modPrime(Math.abs(rand.nextInt()));
this.seed2 = modPrime(Math.abs(rand.nextInt()));
}
/**
* The next value in the sequence.
* @return the next value in the sequence as a BigInteger
*/
public int next() {
int result = valueForIndex((int) index);
index += 1;
if (index > Integer.MAX_VALUE) {
throw new IllegalStateException("Cannot generate more than " + Integer.MAX_VALUE + " random sequence nos");
}
return result;
}
/**
* Calculates the value for the sequence for the given index
* @param index
* @return
*/
public int valueForIndex(int index) {
if (index < 0) {
throw new IllegalArgumentException("cannot pass negative index");
}
if (index >= MAX_INT_PRIME) {
return index; // map the values above the prime to themselves
}
int first = calculateResidue(modPrime(index + seed1));
int result = calculateResidue(modPrime(first + seed2));
return result;
}
private int calculateResidue(int value) {
assert (value >= 0 && value < MAX_INT_PRIME) : value;
int residue = modPrime((long) value * (long) value);
int result = value <= (MAX_INT_PRIME / 2) ? residue : MAX_INT_PRIME - residue;
assert (result >= 0 && result < MAX_INT_PRIME) : value;
return result;
}
private int modPrime(long value) {
int i = (int) (value % MAX_INT_PRIME);
assert i >= 0 : i + " from " + value;
return i;
}
}
@talon55
Copy link

talon55 commented Apr 25, 2018

Any chance you'd be willing to put this in a repo with a license? I'd really like to use your implementation. Thanks!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment