Как да генерирате непредубедено произволно число в произволен диапазон, като използвате най-малко битове

Общият подход за елиминиране на отклонението е да се изхвърлят числа, които са извън желания диапазон. Както беше отбелязано, това е разточително. Възможно е да се минимизира загубата, като се започне с по-голям брой битове и се генерират множество случайни числа едновременно; можете да постигнете по-добро съответствие между диапазона от входове и изходи.

Например вземете хвърляне на зар. Изходът има 6 възможности. Наивният подход би отнел 3 произволни бита за всяко произведено произволно число. Първият пример демонстрира проблема с гълъбите.

def pigeon_die(total_bit_count):
    for i in xrange(total_bit_count // 3):
        bits = random.getrandbits(3)
        yield 1 + bits * 6 // 8

1 : 832855
2 : 417835
3 : 416012
4 : 833888
5 : 416189
6 : 416554
total 3333333
max/min 2.00448063998

Вторият пример е често използваният разточителен подход. Можете да видите, че той генерира по-малко произволни числа от същия брой произволни битове, но отклонението е елиминирано.

def wasteful_die(total_bit_count):
    for i in xrange(total_bit_count // 3):
        bits = random.getrandbits(3)
        if bits < 6:
            yield 1 + bits

1 : 417043
2 : 415812
3 : 417835
4 : 416012
5 : 416645
6 : 417243
total 2500590
max/min 1.00486517946

Последният пример отнема 13 бита наведнъж и генерира 5 произволни числа от него. Това генерира дори повече числа от наивния подход!

def optimized_die(total_bit_count):
    for i in xrange(total_bit_count // 13):
        bits = random.getrandbits(13)
        if bits < 6**5:
            for j in range(5):
                yield 1 + bits % 6
                bits //= 6

1 : 608776
2 : 608849
3 : 608387
4 : 608119
5 : 607855
6 : 608559
total 3650545
max/min 1.00163525841

Изборът от 13 бита беше направен чрез вземане на логаритъм с основа 6 на степени на 2 и избор на този, който е най-близо до цяло число.

def waste_list(n):
    for bit in range(1, 31):
        potential = math.log(2**bit, n)
        count = int(potential)
        if count > 0:
            waste = potential - count
            yield waste, bit, count

for waste, bit, count in sorted(waste_list(6)):
    print bit, count, waste
    if bit == 3:
        break

13 5 0.029086494049
26 10 0.0581729880981
8 3 0.0948224578763
21 8 0.123908951925
3 1 0.160558421704

Както можете да видите, има 4 избора, по-добри от простите 3 бита.

Опасявам се, че предложеният от вас подход е пристрастен.

Да предположим, че генераторът на произволни числа е направил числа от 0 до 255, но вие искате произволно число в диапазона от 0 до 254.

Ако генераторът на случайни числа произведе 255 (1111_1111 в двоична система), вашият подход ще изхвърли един бит и ще добави още един, докато в крайна сметка ще завършите с числото 254 (1111_1110 в двоична система). (Ако съм разбрал правилно вашия подход.)

Следователно вашите генерирани числа ще имат вероятност от 1/256 за всяко число, с изключение на 254, което ще има вероятност от 1/128.