Как сгенерировать случайное целое число в диапазоне [0, n] из потока случайных бит без потери битов?

Question

У меня есть поток (равномерных) случайных битов, из которых я хотел бы генерировать случайные целые числа равномерно в диапазоне [0, n] без потери битов.(Я рассматриваю потерянные биты, которые превышают пол (log_2 (n)) + 1, при условии, что всегда можно использовать не более того.) Например, если n = 5, то алгоритмдля поиска следует использовать не более трех бит.Как это можно сделать?

Answer 1

Это эквивалентно поиску двусторонней функции между двумя наборами различной (конечной) мощности.Это невозможно.

Answer 2

Хотя в описании вашего вопроса указано фиксированное количество бит на случайное число, сгенерированное в вашем заголовке, нет.Итак, я собираюсь добавить здесь, что в среднем вы можете сгенерировать случайное число с количеством битов, которые вы указали, плюс полубита.Приведенный ниже алгоритм принимает переменное число битов для значений n, не делимых на 2, но среднее количество битов, которое он будет использовать, составляет floor (log_2 (n)) + 1,5 .

Standardреализации функции для генерации целого числа в диапазоне используют% (по модулю) для большого случайного числа.Это приводит к потере битов и не приведет к математически точному случайному распределению, если только оно не будет перезапущено для некоторых значений большого случайного числа.Следующий алгоритм производит истинное случайное распределение и не будет тратить биты.(Вернее, я не вижу очевидного способа уменьшить количество потребляемых битов. Может быть, некоторая энтропия могла бы быть восстановлена ​​из «слишком большого числа»).

# Generate a number from 0 to n inclusive without wasting bits.
function RandomInteger(n)
    if n <= 0
        error
    else
        i = Floor(Log2(n))
        x = i
        r = 0
        while x >= 0
            r = r + (2 ^ x) * NextRandomBit()
            if r > n 
                # Selected number too large so begin again.
                x = i 
                r = 0
            else
                # Still in range. Calculate the next bit.
                x = x - 1
        return r

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

Answer 3

Сначала выясните количество возможных значений, которые вы хотите сгенерировать. В случае целых чисел в диапазоне 0..5 это 6 значений. Они могут быть представлены в битах ceil (log (6) / log (2)).

// in C++
std::bitset< 3 > bits;
// fill the bitset

// interpret as a number
long value = bits.to_ulong();

Затем найдите преобразование из n-битов в окончательный формат представления: его необходимо масштабировать от диапазона [0..2 ^N ] до диапазона [от, до]:

double out_from=-1, out_to=5;
double in_from=0, in_to = std::bitset<3>().flip().to_ulong();

double factor   = (out_to-out_from)/(in_to-in_from)
double constant = out_from - in_from;

double rescaled = in_value * scale + constant;
long out = floor( rescaled );

Answer 4

Похоже, вы могли бы просто брать x = ceil (log_2 (n)) бит за раз и просто использовать их в качестве случайных чисел. Проблема, с которой вы столкнетесь, заключается в том, что если число, которое вы получаете, превышает ваш лимит (например, 5), то вы захотите выполнить магию, чтобы получить его меньше 5, но равномерно. В этом случае, что кажется логичным, это то, что вы бы просто взяли еще x битов, но, поскольку вы указали, что мы не можем тратить биты, нам нужно быть более креативными. Я бы порекомендовал повернуть вправо или влево, но это не всегда поможет вам выйти из ситуации. (Рассмотрим строку из 111, когда вы хотели n = 5). Мы могли бы сделать до x поворотов, чтобы посмотреть, приведет ли один из поворотов к правильному диапазону, или мы могли бы просто перевернуть все биты и добавить 1 (дополнение к двум). Я верю, что это сделает его единообразным.

Так, например, если у вас была следующая строка (самый правый бит - первый, который вы получили):

101001111010010101

И вы используете n = 5, затем ceil (log2 (n)) = 3, так что вы будете использовать три бита за раз, и ваши результаты (на каждом временном шаге) будут следующими:

t=0 : 101 = 5
t=1: 010 = 2
t=2: 010 = 2
t=3: 111 = 7 -> too large, rotates won't work, so we use 2's complement: 001 = 1
t=4: 001 = 1
t=5: 101 = 5