Я хотел бы добавить еще один ответ, в дополнение к моему первому ответу . Этот ответ пытается минимизировать количество вызовов до rand5() за вызов до rand7(), чтобы максимально использовать случайность. То есть, если вы считаете случайность ценным ресурсом, мы хотим использовать как можно большую ее часть, не выбрасывая случайные биты. Этот ответ также имеет некоторые сходства с логикой, представленной в ответ Ивана .
Энтропия случайной величины является четко определенной величиной. Для случайной величины, которая принимает N состояний с равными вероятностями (равномерное распределение), энтропия равна log 2 N. Таким образом, rand5() имеет приблизительно 2,332193 бита энтропии, а rand7() имеет около 2,80735 биты энтропии. Если мы надеемся максимизировать наше использование случайности, нам нужно использовать все 2.32193 бита энтропии от каждого вызова к rand5() и применять их для генерации 2.80735 битов энтропии, необходимых для каждого вызова к rand7(). Таким образом, фундаментальный предел заключается в том, что мы можем делать не лучше, чем log (7) / log (5) = 1.20906 вызовов на rand5() за вызов rand7().
Примечания: все логарифмы в этом ответе будут основанием 2, если не указано иное. Предполагается, что rand5() вернет числа в диапазоне [0, 4], а rand7() вернет числа в диапазоне [0, 6]. Настройка диапазонов на [1, 5] и [1, 7] соответственно тривиальна.
Так как нам это сделать? Мы генерируем бесконечно точное случайное действительное число в диапазоне от 0 до 1 (представьте, что мы действительно можем вычислить и сохранить такое бесконечно точное число - мы исправим это позже). Мы можем сгенерировать такое число, генерируя его цифры в базе 5: мы выбираем случайное число 0. a 1 a 2 a 3 ..., где каждая цифра i выбирается путем вызова rand5(). Например, если наш ГСЧ выбрал i = 1 для всех i, игнорируя тот факт, что это не очень случайно, это будет соответствовать действительному числу 1/5 + 1 / 5 2 + 1/5 3 + ... = 1/4 (сумма геометрического ряда).
Хорошо, мы выбрали случайное действительное число от 0 до 1. Теперь я утверждаю, что такое случайное число распределено равномерно. Интуитивно понятно, что это легко понять, поскольку каждая цифра выбрана одинаково, а число является бесконечно точным. Однако формальное доказательство этого несколько сложнее, поскольку теперь мы имеем дело с непрерывным распределением, а не с дискретным, поэтому нам нужно доказать, что вероятность того, что наше число лежит в интервале [a, b] равна длине этого интервала, b - a. Доказательство оставлено в качестве упражнения для читателя =).
Теперь, когда у нас есть случайное действительное число, равномерно выбранное из диапазона [0, 1], нам нужно преобразовать его в серию равномерно случайных чисел в диапазоне [0, 6], чтобы сгенерировать вывод rand7() , как нам это сделать? Как раз то, что мы только что сделали - мы конвертируем его в бесконечно точное десятичное число в базе 7, и тогда каждая цифра в базовой 7 будет соответствовать одному выводу rand7().
Если взять пример из предыдущего, то, если наш rand5() создает бесконечный поток из 1, то наше случайное действительное число будет 1/4. Преобразовав 1/4 в основание 7, мы получим бесконечное десятичное значение 0,15151515 ..., поэтому мы будем производить в качестве выходных 1, 5, 1, 5, 1, 5 и т. Д.
Хорошо, у нас есть основная идея, но у нас осталось две проблемы: мы не можем фактически вычислить или сохранить бесконечно точное действительное число, так как же нам иметь дело только с его конечной частью? Во-вторых, как мы на самом деле конвертируем его в базу 7?
Один из способов преобразования числа от 0 до 1 в основание 7:
- Умножить на 7
- Неотъемлемой частью результата является следующая базовая 7 цифра
- Вычесть неотъемлемую часть, оставив только дробную часть
- Перейти к шагу 1
Чтобы решить проблему бесконечной точности, мы вычисляем частичный результат, а также сохраняем верхнюю границу того, каким может быть результат. То есть предположим, что мы дважды вызывали rand5(), и он возвращал 1 оба раза. Число, которое мы сгенерировали до сих пор, составляет 0,11 (основание 5). Что бы ни производили остальные бесконечные серии вызовов rand5(), случайное действительное число, которое мы генерируем, никогда не будет больше 0,12: всегда верно, что 0,11 ≤ 0,11xyz ... <0,12. </p>
Итак, отслеживая текущее число и максимальное значение, которое оно может принять, мы конвертируем оба числа в основание 7. Если они согласуются с первыми k цифрами, то мы может безопасно выводить следующие k цифр - независимо от того, что представляет собой бесконечный поток из базовых 5 цифр, они никогда не будут влиять на следующие k цифры в базовом 7 представлении!
И вот алгоритм - чтобы сгенерировать следующий вывод rand7(), мы генерируем столько цифр, сколько rand5(), сколько нам нужно, чтобы убедиться, что мы точно знаем значение следующей цифры при преобразовании случайное действительное число в базу 7. Вот реализация Python с тестовым набором:
import random
rand5_calls = 0
def rand5():
global rand5_calls
rand5_calls += 1
return random.randint(0, 4)
def rand7_gen():
state = 0
pow5 = 1
pow7 = 7
while True:
if state / pow5 == (state + pow7) / pow5:
result = state / pow5
state = (state - result * pow5) * 7
pow7 *= 7
yield result
else:
state = 5 * state + pow7 * rand5()
pow5 *= 5
if __name__ == '__main__':
r7 = rand7_gen()
N = 10000
x = list(next(r7) for i in range(N))
distr = [x.count(i) for i in range(7)]
expmean = N / 7.0
expstddev = math.sqrt(N * (1.0/7.0) * (6.0/7.0))
print '%d TRIALS' % N
print 'Expected mean: %.1f' % expmean
print 'Expected standard deviation: %.1f' % expstddev
print
print 'DISTRIBUTION:'
for i in range(7):
print '%d: %d (%+.3f stddevs)' % (i, distr[i], (distr[i] - expmean) / expstddev)
print
print 'Calls to rand5: %d (average of %f per call to rand7)' % (rand5_calls, float(rand5_calls) / N)
Обратите внимание, что rand7_gen() возвращает генератор, так как он имеет внутреннее состояние, включающее преобразование числа в основание 7. Испытательный комплект вызывает next(r7) 10000 раз, чтобы получить 10000 случайных чисел, а затем измеряет их распределение. Используется только целочисленная математика, поэтому результаты в точности верны.
Также обратите внимание, что числа здесь становятся очень большими, очень быстрыми. Полномочия 5 и 7 растут быстро. Следовательно, производительность начнет заметно ухудшаться после генерации большого количества случайных чисел из-за арифметики Бигнума. Но помните здесь, моя цель состояла в том, чтобы максимально использовать случайные биты, а не максимизировать производительность (хотя это вторичная цель).
В одном прогоне я сделал 12091 звонок на rand5() для 10000 звонков на rand7(), достигнув минимума вызовов log (7) / log (5) в среднем до 4 значащих цифр и получив результат был равномерным.
Чтобы перенести этот код на язык, который не имеет встроенных произвольно больших целых чисел, вам нужно ограничить значения pow5 и pow7 максимальным значением вашего собственного целочисленного типа - - если они становятся слишком большими, то перезагрузите все и начните все сначала. Это немного увеличит среднее количество вызовов до rand5() за вызов до rand7(), но, надеюсь, оно не должно увеличиться слишком сильно даже для 32- или 64-битных целых чисел.