Как детерминистически отобразить последовательные целые числа в равномерно распределенные двойные - PullRequest
Новая
       24

Как детерминистически отобразить последовательные целые числа в равномерно распределенные двойные

0 голосов
/ 10 декабря 2018

Я получаю последовательность примерно последовательных целых чисел (поступающих из ключа базы данных), и я хочу отобразить каждое целое число в двойное число от 0 до 1 детерминистическим образом, чтобы результирующий набор всех двойных чисел был (близко к) равномерно распределены.В идеале это должно быть верно, даже после того, как было получено только небольшое количество целых чисел.

Отображение должно быть детерминированным, потому что оно может происходить несколько раз для каждого целого числа (на нескольких разных машинах), и результирующее двойное число должнобыть одинаковым каждый раз, когда происходит сопоставление.

Например, как должна выглядеть функция mapToDouble ниже? 

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

Наилучший подход, о котором я могу подумать, это что-то вроде: 

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

, который приблизительно равномерно распределен для наиболее значимых битов с относительно небольшим размером выборки, но может быть искажен для менее значимых битов.

1 Ответ

0 голосов
/ 10 декабря 2018

Конечно, вы можете использовать Линейный конгруэнтный генератор , чтобы сделать отображение.По сути, LCG с правильными параметрами, удовлетворяющими теореме Халла – Добелла, однозначно отображает любое целое число в диапазоне [0 ... 2 64 ) на другое целое число в [0 ... 2 64 ) дальность, хорошие биты чоппер так сказать.Двойные числа не будут уникальными, их недостаточно в диапазоне [0 ... 1).

Псевдокод Java (извините, Java уже давно, предполагал, что Java 8 с Long здесь) 

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;
}

Вы можете попытаться сопоставить уникальный дубль, используя Лемер RNG с простым 2 53 -111 , что довольномного гарантирует равномерное 53-битное мантисса.Однако вычисление по модулю должно быть сделано явно.

...