How to deterministically map sequential integers to uniformly distributed doubles

Question

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.

The current approach ain't that helpful. "0.2" hmm, see https://stackoverflow.com/questions/588004/is-floating-point-math-broken for that — GhostCat, Dec 10 '18 at 14:54
If you know the range of the integers, e.g. `[0,x]` where `x` is the maximum value you expect, why not just `i/(double)x` (the cast would only be needed if `x` isn't a double already)? — Thomas, Dec 10 '18 at 14:54
Does every `int` value (from `Integer.MIN_VALUE` to `Integer.MAX_VALUE`) have to produce a *unique* `double` value? — DodgyCodeException, Dec 10 '18 at 15:13
@Thomas The issue is I don't have all the values in that range, just a sequence starting from some value in that range. — not_john, Dec 10 '18 at 15:53
Well, what exactly is the range of the integers in question? — President James K. Polk, Dec 10 '18 at 21:29

score 2 · Accepted Answer · answered Dec 10 '18 at 19:05

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...2⁶⁴) range into another one in the [0...2⁶⁴) 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 2⁵³-111, which pretty much guarantees uniform 53bits mantissa. Modulo computation has to be done explicitly, though.

How to deterministically map sequential integers to uniformly distributed doubles

1 Answers1