CODEWITHSUNDEEP
javarandomhash
not_john
not_john

Reputation: 170

How to deterministically map sequential integers to uniformly distributed doubles

I am receiving a sequence of roughly sequential integers (coming from a database key), and I want to map each integer to a double between 0 and 1 in a deterministic way, so that the result set of all the doubles be (close to) uniformly distributed. This should ideally be true even after only a small number of integers have been received.

The mapping needs to be deterministic because it can happen multiple times for each integer (on multiple different machines), and the resulting double should be the same each time the mapping occurs.

e.g. What should the function mapToDouble look like below?

final int start = 100000;
final int size = 2000;
final double[] results = new double[size];

for (int i = 0; i < size; i++) {
    results[i] = mapToDouble(i + start)
}

// results is uniformly distributed

The best approach I can think of so far is something like:

double mapToDouble(final int i) {
        final String s = new StringBuilder().append(i).append(".0").reverse().toString();
        return new Double(s);
    }

which is approximately uniformly distributed for the most significant bits with a relatively small sample size, but can be skewed for the less significant bits.

Upvotes: 0

Views: 360

Answers (1)

Severin Pappadeux
Severin Pappadeux

Reputation: 20130

Sure, you could use Linear Congruential Generator to do the mapping. Basically, LCG with proper parameters satisfying Hull–Dobell Theorem, uniquely maps any integer in [0...264) range into another one in the [0...264) range, good bits chopper so to speak. Doubles won't be unique, not enough of them in the [0...1) range.

Java pseudocode (sorry, did Java long time ago, assumed Java 8 with Long here)

static final long a = Long.parseUnsignedLong("2862933555777941757"); // values taken from https://nuclear.llnl.gov/CNP/rng/rngman/node4.html
static final long c = Long.parseUnsignedLong("3037000493");

double mapToDouble(final int i) {
    long seed = (long)i;
    long mapl = a * seed + c; // should do wraparound automatically, or use Long.remainderUnsigned
    double x  = (x >>> 11) * 0x1.0p-53; // see http://xoshiro.di.unimi.it/
    return x;
}

You may try to do mapping to unique double using Lehmer RNG with prime 253-111, which pretty much guarantees uniform 53bits mantissa. Modulo computation has to be done explicitly, though.

Upvotes: 2

Related Questions