Я посмотрел на «Fast Dice Roller» (FDR), на который указывает @ Peter.O , который действительно прост (и избегает деления). Но каждый раз, когда генерируется случайное число, оно потребляет некоторое количество битов и отбрасывает часть тех битов, которые не использует.
Методы «пакетирования» / «объединения», кажется, работают лучше, чем FDR, потому что неиспользуемые доли битов (хотя бы частично) сохраняются.
Но, что интересно, вещь, на которую вы ссылаетесь DrMath , в основном такая же, как FDR, но не начинается с нуля для каждой случайное значение, которое он возвращает.
Таким образом, FDR для возврата 0..n-1 идет:
random(n):
m = 1 ; r = 0
while 1:
# Have r random and evenly distributed in 0..m-1
# Need m >= n -- can double m and double r adding random bit until
# we get that. r remains evenly distributed in 0..m-1
while m < n: r = 2*r + next_bit() ; m = m*2
# Now have r < m and n <= m < n*2
if r < n: return r # Hurrah !
# Have overshot, so reduce m and r to m MOD n and r MOD m
m -= n ; r -= n ;
В DrMath идет речь:
# Initialisation once before first call of random(m)
ms = 1 ; rs = 0
N = ... # N >= maximum n and N*2 does not overflow
# The function -- using the "static"/"global" ms, rs and N
random(n):
m = ms ; r = rs
while 1:
# Same as FDR -- except work up to N not n
while m < N: r = 2*r + next_bit() ; m = m*2 ;
# Now have r < m and m >= N
# Set nq = largest multiple of n <= m
# In FDR, at this point q = 1 and nq = n
q = m DIV n ;
nq = n * q
if r < nq: # all set if r < nq
# in FDR ms = 1, rs = 0
ms = q # keep stuff not used this time
rs = r DIV n # ditto
return r MOD n # hurrah !
# Overshot, so reduce MOD n*q -- remembering, for FDR q == 1
m = m - nq
r = r - nq
, который, как отмечалось, в основном совпадает с FDR, но отслеживает неиспользованную случайность.
При тестировании я обнаружил:
FDR: for 100000 values range=3 used 266804 bits cost=1.6833
DrMath: for 100000 values range=3 used 158526 bits cost=1.0002
Где cost равно bits-used / (100000 * log2(3)) отмечая, что log2 (3) = (1,58496). (Таким образом, cost - это количество используемых битов, деленное на количество битов, которые можно использовать).
Также:
FDR: for 100000 values range=17: 576579 bits cost=1.4106
DrMath: for 100000 values range=17: 408774 bits cost=1.0001
И:
FDR: for 100000 values ranges=5..60: 578397 bits cost=1.2102
DrMath: for 100000 values ranges=5..60: 477953 bits cost=1.0001
, где построено 100000 значений, и для каждого из них выбран диапазон в 5..60 (включительно).
Мне кажется, что DrMath имеет его! Хотя для больших диапазонов у него меньше преимуществ.
Имейте в виду ... DrMath использует по крайней мере 2 деления на случайное возвращаемое значение, что дает мне умения во время выполнения. Но вы сказали, что вас не интересует эффективность во время выполнения.
Как это работает?
Итак, мы хотим, чтобы последовательность случайных значений r была равномерно распространяется в диапазоне 0..n-1. Неудобно, что у нас есть только источник случайности, который дает нам случайные значения, которые равномерно распределены в 0..m-1. Обычно m будет степенью 2 - и предположим, что n < m (если n == m, проблема тривиальна, если n > m, проблема невозможна). Для любого r мы можем взять r MOD n, чтобы получить случайное значение в требуемом диапазоне. Если мы используем r только тогда, когда r < n, тогда (тривиально) мы получаем равномерное распределение, которое мы хотим. Если мы используем r только тогда, когда r < (n * q) и (n * q) < m, у нас также есть равномерное распределение. Мы здесь «отвергаем» r, которые являются «слишком большими». Чем меньше r мы отвергаем, тем лучше. Поэтому мы должны выбрать q так, чтобы (n * q) <= m < (n * (q-1)) - так, чтобы n * q было наибольшим кратным n, меньшим или равным m. Это, в свою очередь, говорит нам о том, что n «намного меньше», чем m, следует отдавать предпочтение.
Когда мы «отвергаем» данный r, мы можем выбросить все это, но это поворачивает не быть полностью необходимым. Кроме того, m не обязательно должно быть степенью 2. Но мы вернемся к этому позже.
Вот некоторые рабочие Python:
M = 1
R = 0
N = (2**63) # N >= maximum range
REJECT_COUNT = 0
def random_drmath(n):
global M, R, REJECT_COUNT
# (1) load m and r "pool"
m = M
r = R
while 1:
# (2) want N <= m < N*2
# have 0 <= r < m, and that remains true.
# also r uniformly distributed in 0..m-1, and that remains true
while m < N:
r = 2*r + next_bit()
m = m*2
# (3) need r < nq where nq = largest multiple of n <= m
q = m // n
nq = n * q
if r < nq:
# (4) update the m and r "pool" and return 0..n-1
M = q
R = r // n
return r % n # hurrah !
# (5) reject: so reduce both m and r by MOD n*q
m = m - nq
r = r - nq
REJECT_COUNT += 1
Должно иметь N> = максимальная дальность, желательно намного больше. 2**31 или 2**63 являются очевидными вариантами.
При первом вызове random_drmath() step (2) будет читать случайные биты, чтобы «заполнить пул». Для N = 2**63, получится m = 2**63 и r с 63 случайными битами. Ясно, что r является случайным и равномерно распределен в 0..m-1. [Пока все хорошо.]
Теперь (и при всех последующих вызовах random_drmath()) мы надеемся равномерно извлечь случайное значение в 0..n-1 из r, как обсуждалось выше. Итак - step (3) - создает nq, который является наибольшим кратным n, которое меньше или равно m. Если r >= nq мы не можем использовать его, потому что в nq..m-1 меньше n значений - это обычный критерий «отклонения».
Итак, где r < nq может возвращать значение - - шаг (4). Хитрость в том, чтобы думать о m и r как о числах "base-n". Ls "di git" из r извлекается (r % n) и возвращается. Затем m и r сдвигаются вправо на один «ди git» (q = m // n и r // n) и сохраняются в «пуле». Я думаю, что ясно, что на данный момент r и m все еще r < m и r случайны и равномерно распределены в 0..m-1. Но m больше не является степенью 2 - но это нормально.
Но, если r >= nq должен уменьшить r и m вместе - шаг (5) - и попробуйте снова. Тривиально, можно установить m = 1 ; r = 0 и начать заново. Но то, что мы делаем, вычитаем nq из m и r, что оставляет r равномерно распределенным в 0..m-1. Этот последний шаг выглядит как волшебный c, но мы знаем, что r находится в nq..m-1, и каждое возможное значение имеет равную вероятность, поэтому r-nq находится в диапазоне 0..m-nq-1, и каждое возможное значение все еще имеет равную вероятность! [Помните, что «инвариант» в верхней части while l oop означает, что r является случайным и равномерно распределен в 0..m-1.]
Для малых n шаг отклонения будет отбросить большую часть r, но для небольших n (по сравнению с N) мы надеемся не слишком часто отказываться. И наоборот, для больших n (по сравнению с N) мы можем ожидать отклонения чаще, но при этом сохраняются, по крайней мере, некоторые из случайных битов, которые мы съели до сих пор. Я чувствую, что может быть способ сохранить больше r ... но я не думал о простом способе сделать это ... и если стоимость чтения одного случайного бита высока, возможно, стоит попробовать чтобы найти непростой способ!
FWIW: установка N = 128 Я получаю:
FDR: for 100000 values ranges=3.. 15: 389026 bits cost=1.2881
DrMath: for 100000 values ranges=3.. 15: 315815 bits cost=1.0457
FDR: for 100000 values ranges 3.. 31: 476428 bits cost=1.2371
DrMath: for 100000 values ranges 3.. 31: 410195 bits cost=1.0651
FDR: for 100000 values ranges 3.. 63: 568687 bits cost=1.2003
DrMath: for 100000 values ranges 3.. 63: 517674 bits cost=1.0927
FDR: for 100000 values ranges 3..127: 664333 bits cost=1.1727
DrMath: for 100000 values ranges 3..127: 639269 bits cost=1.1284
, так как n приближается к N стоимость за единицу увеличивается.