Побитовая эффективная равномерная генерация случайных чисел

Я помню, как читал о методе эффективного использования случайных битов в статье на веб-сайте, ориентированном на математику, но я больше не могу найти правильные ключевые слова в Google, чтобы найти его, и его нет в истории моего браузера.

Суть поставленной задачи заключалась в том, чтобы взять последовательность случайных чисел в области [domainStart, domainEnd) и эффективно использовать биты последовательности случайных чисел для равномерного проецирования в диапазон [rangeStart, rangeEnd). И домен, и диапазон — целые числа (вернее, longs, а не Z). Какой для этого алгоритм?

Что касается реализации, у меня есть функция с такой сигнатурой:

long doRead(InputStream in, long rangeStart, long rangeEnd);

in основан на CSPRNG (с питанием от аппаратного ГСЧ, обусловленным SecureRandom), который я должен использовать; возвращаемое значение должно быть между rangeStart и rangeEnd, но очевидная реализация этого расточительна:

long doRead(InputStream in, long rangeStart, long rangeEnd) {
    long retVal = 0;
    long range = rangeEnd - rangeStart;

    // Fill until we get to range
    for (int i = 0; (1 << (8 * i)) < range; i++) {
        int in = 0;
        do {
            in = in.read();
        // but be sure we don't exceed range
        } while(retVal + (in << (8 * i)) >= range);
        retVal += in << (8 * i);
     }

    return retVal + rangeStart;
}

Я считаю, что это фактически та же идея, что и (rand() * (max - min)) + min, только мы отбрасываем биты, которые подталкивают нас к max. Вместо использования оператора по модулю, который может привести к неправильному смещению результатов в сторону меньших значений, мы отбрасываем эти биты и пытаемся снова. Поскольку попадание в CSPRNG может привести к повторному заполнению (что может заблокировать InputStream), я хотел бы избежать потери случайных битов. Генри указывает, что этот код смещается от 0 и 257; Бантар демонстрирует это на примере.

Первое редактирование: Генри напомнил мне, что суммирование вызывает центральную предельную теорему. Я исправил приведенный выше код, чтобы обойти эту проблему.

Второе редактирование: механическая улитка предложила мне посмотреть источник Random.nextInt(). Почитав его какое-то время, я понял, что эта проблема похожа на проблему преобразования базы. Смотрите ответ ниже.


java random entropy
person user314104    schedule 22.09.2013    source источник
comment
Ваша очевидная реализация не только расточительна, но и концептуально неверна (за исключением нескольких ошибок реализации). Добавляя случайные числа, вы меняете распределение. Если добавлено достаточное количество чисел, оно станет гауссовым. Например, при бросании двух игральных костей чаще выпадает 7, чем 2.   -  person Henry    schedule 22.09.2013
comment
Спасибо. Я знал, что сделал что-то ужасно неправильное с алгоритмической точки зрения. :S Мне, наверное, нужно немного поспать.   -  person user314104    schedule 22.09.2013
comment
Посмотрите на реализацию java.util.Random.nextInt.   -  person Mechanical snail    schedule 22.09.2013
comment
@ Генри, user314104 на самом деле не добавляет случайные числа. Он просто объединяет байты, чтобы сформировать большее число. Это не должно приводить к предвзятости.   -  person Piotr Praszmo    schedule 22.09.2013
comment
@Banthar Тем временем вопрос был отредактирован ;-) Теперь все в порядке.   -  person Henry    schedule 22.09.2013
comment
Все еще есть небольшое смещение из-за того, как выбран последний байт.   -  person Henry    schedule 22.09.2013

Ответы (2)


arrow_upward
2
arrow_downward

Ваш алгоритм дает необъективные результаты. Предположим, rangeStart=0 и rangeEnd=257. Если первый байт больше 0, это будет результат. Если это 0, результатом будет либо 0, либо 256 с вероятностью 50/50. Таким образом, вероятность выбора 0 и 256 вдвое меньше, чем любого другого числа.

Я провел простой тест, чтобы подтвердить это:

p(0)=0.001945
p(1)=0.003827
p(2)=0.003818
...
p(254)=0.003941
p(255)=0.003817
p(256)=0.001955

Я думаю, вам нужно сделать то же самое, что и java.util.Random.nextInt, и отбросить все число, а не только последний байт.

person Piotr Praszmo    schedule 22.09.2013
comment
Правильно, чтобы уменьшить количество случаев, когда мы выходим за пределы диапазона, можно было бы взять только необходимые биты вместо полного байта. Например, чтобы получить число в диапазоне [0..700), просто возьмите 10 бит вместо двух байтов и отбросьте, если ›= 700. - person Henry; 22.09.2013

arrow_upward
0
arrow_downward

Прочитав исходный код Random.nextInt(), я понял, что эта проблема похожа на проблему преобразования базы.

Вместо того, чтобы преобразовывать один символ за раз, было бы более эффективно преобразовывать блоки входных символов за раз через «буфер» накопителя, который достаточно велик, чтобы представлять по крайней мере один символ в домене и в диапазоне. Новый код выглядит так:

public int[] fromStream(InputStream input, int length, int rangeLow, int rangeHigh) throws IOException {
    int[] outputBuffer = new int[length];
    // buffer is initially 0, so there is only 1 possible state it can be in
    int numStates = 1;
    long buffer = 0;
    int alphaLength = rangeLow - rangeHigh;
    // Fill outputBuffer from 0 to length
    for (int i = 0; i < length; i++) {
        // Until buffer has sufficient data filled in from input to emit one symbol in the output alphabet, fill buffer.
        fill:
        while(numStates < alphaLength) {
            // Shift buffer by 8 (*256) to mix in new data (of 8 bits)
            buffer = buffer << 8 | input.read();
            // Multiply by 256, as that's the number of states that we have possibly introduced
            numStates = numStates << 8;
        }
        // spits out least significant symbol in alphaLength
        outputBuffer[i] = (int) (rangeLow + (buffer % alphaLength));
        // We have consumed the least significant portion of the input.
        buffer = buffer / alphaLength;
        // Track the number of states we've introduced into buffer
        numStates = numStates / alphaLength;
    }
    return outputBuffer;
}

Однако между преобразованием чисел между основаниями и этой проблемой есть фундаментальное различие; для преобразования между основаниями, я думаю, нужно иметь достаточно информации о числе для выполнения вычисления - последовательные деления на целевое основание приводят к остаткам, которые используются для построения цифр в целевом алфавите. В этой задаче мне не нужно знать всю эту информацию, пока я не искажаю данные, что означает, что я могу делать то же, что и в цикле, помеченном как «заполнение».

person user314104    schedule 29.09.2013
comment
Я начинаю понимать, что есть некоторые условия, которые делают эту проблему неразрешимой. Я отредактирую этот ответ позже, чтобы отметить это. - person user314104; 03.10.2013