Для функции, которая производит случайное целое число в диапазоне от 1 до 5, напишите функцию, которая производит случайное целое число в диапазоне от 1 до 7.
Это эквивалентно решению Адама Розенфилда, но для некоторых читателей может быть немного понятнее. Он предполагает, что rand5() - это функция, которая возвращает статистически случайное целое число в диапазоне от 1 до 5 включительно.
int rand7()
{
int vals[5][5] = {
{ 1, 2, 3, 4, 5 },
{ 6, 7, 1, 2, 3 },
{ 4, 5, 6, 7, 1 },
{ 2, 3, 4, 5, 6 },
{ 7, 0, 0, 0, 0 }
};
int result = 0;
while (result == 0)
{
int i = rand5();
int j = rand5();
result = vals[i-1][j-1];
}
return result;
}
Как это работает? Подумайте об этом так: представьте, что вы печатаете этот двумерный массив на бумаге, прикладываете его к доске для дарта и произвольно бросаете в нее дартс. Если вы нажмете ненулевое значение, это статистически случайное значение между 1 и 7, так как существует равное количество ненулевых значений. Если вы нажмете ноль, просто продолжайте бросать дротик, пока не нанесете ненулевое значение. То, что делает этот код: индексы я и j случайным образом выбирают местоположение на доске дарта, и если мы не получим хороший результат, мы продолжаем бросать дротики.
Как сказал Адам, это может продолжаться вечно в худшем случае, но статистически худший случай никогда не случается.:)
Нет (точно правильное) решение, которое будет выполняться в течение постоянного времени, так как 1/7 является бесконечным десятичным числом в базе 5. Одним простым решением было бы использовать выборку отбраковки, например:
int i;
do
{
i = 5 * (rand5() - 1) + rand5(); // i is now uniformly random between 1 and 25
} while(i > 21);
// i is now uniformly random between 1 and 21
return i % 7 + 1; // result is now uniformly random between 1 and 7
Это ожидаемое время выполнения 25/21 = 1.19 итераций цикла, но существует бесконечно малая вероятность зацикливания навсегда.
Я хотел бы добавить еще один ответ, в дополнение к моему первому ответу. Этот ответ пытается минимизировать количество вызовов rand5() на вызов rand7(), чтобы максимально использовать случайность. То есть, если вы считаете случайность ценным ресурсом, мы хотим использовать как можно большую ее часть, не выбрасывая случайные биты. Этот ответ также имеет некоторые сходства с логикой, представленной в ответе Ивана.
Энтропия случайной величины является четко определенной величиной. Для случайной величины, которая принимает N состояний с равными вероятностями (равномерное распределение), энтропия равна log 2 N. Таким образом, rand5() имеет приблизительно 2.32193 бита энтропии, а 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 1a 2a 3..., где каждая цифра a i выбирается при вызове rand5(). Например, если наш RNG выбрал 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() пример из предыдущего, то если наша rand5() создает бесконечный поток из 1, то наше случайное действительное число будет 1/4. Преобразовав 1/4 в основание 7, мы получим бесконечное десятичное число 0,15151515..., поэтому мы получим в качестве выходных 1, 5, 1, 5, 1, 5 и т.д.
Итак, у нас есть основная идея, но у нас осталось две проблемы: мы не можем на самом деле вычислить или сохранить бесконечно точное действительное число, так как же нам иметь дело только с его конечной частью? Во-вторых, как мы можем преобразовать его в базу 7?
Один из способов преобразования числа от 0 до 1 в основание 7 заключается в следующем:
Чтобы справиться с проблемой бесконечной точности, мы вычисляем частичный результат и сохраняем верхнюю границу того, каким может быть результат. То есть предположим, что мы дважды вызывали rand5() и он возвращал 1 оба раза. Число, которое мы сгенерировали до сих пор, составляет 0,11 (основание 5). Что бы ни производили остальные бесконечные серии вызовов rand5() генерируемое нами случайное действительное число никогда не будет больше 0,12: всегда верно, что 0,11 ≤ 0,11xyz... <0,12.
Таким образом, отслеживая текущее число и максимальное значение, которое оно может принять, мы конвертируем оба числа в основание 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-битных целых чисел.
(Я украл ответ Адама Розенфельда и заставил его работать на 7% быстрее.)
Предположим, что rand5() возвращает один из {0,1,2,3,4} с равным распределением, а цель - return {0,1,2,3,4,5,6} с равным распределением.
int rand7() {
i = 5 * rand5() + rand5();
max = 25;
//i is uniform among {0 ... max-1}
while(i < max%7) {
//i is uniform among {0 ... (max%7 - 1)}
i *= 5;
i += rand5(); //i is uniform {0 ... (((max%7)*5) - 1)}
max %= 7;
max *= 5; //once again, i is uniform among {0 ... max-1}
}
return(i%7);
}
Мы отслеживаем наибольшее значение, которое цикл может сделать в переменной max. Если результат до сих пор находится между max% 7 и max-1, тогда результат будет равномерно распределен в этом диапазоне. Если нет, мы используем остаток, который является случайным от 0 до max% 7-1, и другой вызов rand() для создания нового номера и нового max. Затем мы начинаем снова.
Изменить: Ожидать количество раз для вызова rand5() - это x в этом уравнении:
x = 2 * 21/25
+ 3 * 4/25 * 14/20
+ 4 * 4/25 * 6/20 * 28/30
+ 5 * 4/25 * 6/20 * 2/30 * 7/10
+ 6 * 4/25 * 6/20 * 2/30 * 3/10 * 14/15
+ (6+x) * 4/25 * 6/20 * 2/30 * 3/10 * 1/15
x = about 2.21 calls to rand5()
Алгоритм:
7 может быть представлена в последовательности из 3 бит
Используйте rand (5) для случайного заполнения каждого бита 0 или 1.
Например, например: вызов rand (5) и
если результат равен 1 или 2, заполните бит 0 если результат равен 4 или 5, заполните бит 1 | если результат равен 3, то игнорировать и делать это снова (отклонение)
Таким образом, мы можем произвольно заполнить 3 бита с 0/1 и, таким образом, получить число от 1 до 7.
EDIT: Это похоже на самый простой и эффективный ответ, поэтому здесь есть код для него:
public static int random_7() {
int returnValue = 0;
while (returnValue == 0) {
for (int i = 1; i <= 3; i++) {
returnValue = (returnValue << 1) + random_5_output_2();
}
}
return returnValue;
}
private static int random_5_output_2() {
while (true) {
int flip = random_5();
if (flip < 3) {
return 0;
}
else if (flip > 3) {
return 1;
}
}
}
int randbit( void )
{
while( 1 )
{
int r = rand5();
if( r <= 4 ) return(r & 1);
}
}
int randint( int nbits )
{
int result = 0;
while( nbits-- )
{
result = (result<<1) | randbit();
}
return( result );
}
int rand7( void )
{
while( 1 )
{
int r = randint( 3 ) + 1;
if( r <= 7 ) return( r );
}
}
rand7() = (rand5()+rand5()+rand5()+rand5()+rand5()+rand5()+rand5())%7+1
Изменить: Это не совсем работает. Это примерно на 2 части в 1000 (при условии идеального rand5). Ковши получают:
value Count Error%
1 11158 -0.0035
2 11144 -0.0214
3 11144 -0.0214
4 11158 -0.0035
5 11172 +0.0144
6 11177 +0.0208
7 11172 +0.0144
Переключаясь на сумму
n Error%
10 +/- 1e-3,
12 +/- 1e-4,
14 +/- 1e-5,
16 +/- 1e-6,
...
28 +/- 3e-11
похоже, на порядок на каждые 2 добавленных
BTW: таблица ошибок выше не была сгенерирована с помощью выборки, а следующим отношением рекуррентности:
p[x,n]- число путейoutput=xможет случиться, еслиnвызываетrand5.
p[1,1] ... p[5,1] = 1
p[6,1] ... p[7,1] = 0
p[1,n] = p[7,n-1] + p[6,n-1] + p[5,n-1] + p[4,n-1] + p[3,n-1]
p[2,n] = p[1,n-1] + p[7,n-1] + p[6,n-1] + p[5,n-1] + p[4,n-1]
p[3,n] = p[2,n-1] + p[1,n-1] + p[7,n-1] + p[6,n-1] + p[5,n-1]
p[4,n] = p[3,n-1] + p[2,n-1] + p[1,n-1] + p[7,n-1] + p[6,n-1]
p[5,n] = p[4,n-1] + p[3,n-1] + p[2,n-1] + p[1,n-1] + p[7,n-1]
p[6,n] = p[5,n-1] + p[4,n-1] + p[3,n-1] + p[2,n-1] + p[1,n-1]
p[7,n] = p[6,n-1] + p[5,n-1] + p[4,n-1] + p[3,n-1] + p[2,n-1]
int ans = 0;
while (ans == 0)
{
for (int i=0; i<3; i++)
{
while ((r = rand5()) == 3){};
ans += (r < 3) >> i
}
}
Следующее дает равномерное распределение на {1, 2, 3, 4, 5, 6, 7} с использованием генератора случайных чисел, создающего равномерное распределение на {1, 2, 3, 4, 5}. Код грязный, но логика понятна.
public static int random_7(Random rg) {
int returnValue = 0;
while (returnValue == 0) {
for (int i = 1; i <= 3; i++) {
returnValue = (returnValue << 1) + SimulateFairCoin(rg);
}
}
return returnValue;
}
private static int SimulateFairCoin(Random rg) {
while (true) {
int flipOne = random_5_mod_2(rg);
int flipTwo = random_5_mod_2(rg);
if (flipOne == 0 && flipTwo == 1) {
return 0;
}
else if (flipOne == 1 && flipTwo == 0) {
return 1;
}
}
}
private static int random_5_mod_2(Random rg) {
return random_5(rg) % 2;
}
private static int random_5(Random rg) {
return rg.Next(5) + 1;
}
Если мы рассмотрим дополнительное ограничение на попытку дать наиболее эффективный ответ, т.е. тот, который дал входной поток I, равномерно распределенных целых чисел длиной m с 1-5 выводит поток O, of равномерно распределенные целые числа от 1 до 7 длинной длины относительно m, скажем L(m).
Самый простой способ проанализировать это - обработать потоки я и O как 5-арные и 7-арные числа соответственно. Это достигается основной идеей ответа на поток a1, a2, a3,... -> a1+5*a2+5^2*a3+.. и аналогичным образом для потока O.
Тогда, если взять сечение входного потока длины m choose n s.t. 5^m-7^n=c, где c>0 и как можно меньше. Тогда существует равномерное отображение из входного потока длины m в целые числа от 1 до 5^m и другое равномерное отображение из целых чисел от 1 до 7^n в выходной поток длины n, где нам может понадобиться потерять несколько случаев из входного потока, когда отображаемое целое число превышает 7^n.
Таким образом, это дает значение для L(m) около m (log5/log7), которое приблизительно равно .82m.
Трудность с приведенным выше анализом - это уравнение 5^m-7^n=c, которое нелегко точно решить, и случай, когда равномерное значение от 1 до 5^m превышает 7^n, и мы теряем эффективность.
Вопрос заключается в том, насколько можно достичь максимально возможного значения m (log5/log7). Например, когда это число приближается к целому числу, мы можем найти способ достижения этого точного целого числа выходных значений?
Если 5^m-7^n=c, то из входного потока мы фактически генерируем равномерное случайное число от 0 до (5^m)-1 и не будем использовать значения, превышающие 7^n. Однако эти значения могут быть снова спасены и использованы. Они эффективно генерируют равномерную последовательность чисел от 1 до 5^m-7^n. Поэтому мы можем попытаться использовать их и преобразовать их в 7-рядовые числа, чтобы мы могли создавать больше выходных значений.
Если мы допустим T7(X) как среднюю длину выходной последовательности целых чисел random(1-7), полученных из равномерного ввода размера X, и предположим, что 5^m=7^n0+7^n1+7^n2+...+7^nr+s, s<7.
Тогда T7(5^m)=n0x7^n0/5^m + ((5^m-7^n0)/5^m) T7(5^m-7^n0), так как мы имеем длину без последовательности с вероятностью 7 ^ n0/5 ^ m с остатком длины 5^m-7^n0 с вероятностью (5^m-7^n0)/5^m).
Если мы просто оставим подстановку, получим:
T7(5^m) = n0x7^n0/5^m + n1x7^n1/5^m + ... + nrx7^nr/5^m = (n0x7^n0 + n1x7^n1 + ... + nrx7^nr)/5^m
Следовательно
L(m)=T7(5^m)=(n0x7^n0 + n1x7^n1 + ... + nrx7^nr)/(7^n0+7^n1+7^n2+...+7^nr+s)
Другой способ сделать это:
If 5^m has 7-ary representation `a0+a1*7 + a2*7^2 + a3*7^3+...+ar*7^r
Then L(m) = (a1*7 + 2a2*7^2 + 3a3*7^3+...+rar*7^r)/(a0+a1*7 + a2*7^2 + a3*7^3+...+ar*7^r)
Самый лучший случай - это мой оригинал выше, где 5^m=7^n+s, где s<7.
Затем T7(5^m) = nx(7^n)/(7^n+s) = n+o(1) = m (Log5/Log7)+o(1), как и раньше.
В худшем случае мы можем найти только k и s.t 5 ^ m = kx7 + s.
Then T7(5^m) = 1x(k.7)/(k.7+s) = 1+o(1)
Другие случаи находятся где-то между ними. Было бы интересно посмотреть, насколько хорошо мы можем сделать для очень больших m, т.е. Насколько хорошо мы можем получить член ошибки:
T7(5^m) = m (Log5/Log7)+e(m)
Кажется невозможным достичь e(m) = o(1) в целом, но, надеюсь, мы можем доказать e(m)=o(m).
Все это основывается на распределении 7-арных цифр 5^m при различных значениях m.
Я уверен, что есть много теории, которая охватывает это, я могу взглянуть и сообщить в какой-то момент.
Возможны ли домашние задания?
Эта функция выполняет грубую математику "base 5" для генерации числа от 0 до 6.
function rnd7() {
do {
r1 = rnd5() - 1;
do {
r2=rnd5() - 1;
} while (r2 > 1);
result = r2 * 5 + r1;
} while (result > 6);
return result + 1;
}
Вот работающая реализация Python ответ Адама.
import random
def rand5():
return random.randint(1, 5)
def rand7():
while True:
r = 5 * (rand5() - 1) + rand5()
#r is now uniformly random between 1 and 25
if (r <= 21):
break
#result is now uniformly random between 1 and 7
return r % 7 + 1
Мне нравится бросать алгоритмы, которые я просматриваю на Python, поэтому я могу поиграть с ними, подумал, что отправлю его здесь в надежде, что это полезно кому-то там, а не то, что потребовалось много времени, чтобы бросить вместе.
Почему бы не сделать это просто?
int random7() {
return random5() + (random5() % 3);
}
Шансы получить 1 и 7 в этом решении ниже из-за модуляции, однако, если вам просто нужно быстрое и понятное решение, это путь.
int rand7() {
int value = rand5()
+ rand5() * 2
+ rand5() * 3
+ rand5() * 4
+ rand5() * 5
+ rand5() * 6;
return value%7;
}
В отличие от выбранного решения, алгоритм будет работать в постоянное время. Однако он делает еще 2 вызова rand5, чем среднее время выполнения выбранного решения.
Обратите внимание, что этот генератор не идеален (число 0 на 0,0064% больше шанса, чем любое другое число), но для большинства практических целей гарантия постоянного времени, вероятно, перевешивает эту неточность.
Объяснение
Это решение получается из того факта, что число 15,624 делится на 7 и, следовательно, если мы можем случайным образом и равномерно генерировать числа от 0 до 15 624, а затем взять mod 7, мы можем получить почти однородный генератор rand7. Числа от 0 до 15,624 могут быть равномерно генерированы путем прокатки rand5 6 раз и с их использованием для формирования цифр номера основания 5 следующим образом:
rand5 * 5^5 + rand5 * 5^4 + rand5 * 5^3 + rand5 * 5^2 + rand5 * 5 + rand5
Свойства mod 7, однако, позволяют немного упростить уравнение:
5^5 = 3 mod 7
5^4 = 2 mod 7
5^3 = 6 mod 7
5^2 = 4 mod 7
5^1 = 5 mod 7
Итак,
rand5 * 5^5 + rand5 * 5^4 + rand5 * 5^3 + rand5 * 5^2 + rand5 * 5 + rand5
становится
rand5 * 3 + rand5 * 2 + rand5 * 6 + rand5 * 4 + rand5 * 5 + rand5
Теория
Число 15,624 не было выбрано случайным образом, но может быть найдено с использованием теоремы Ферма, в которой говорится, что если p - простое число, то
a^(p-1) = 1 mod p
Итак, это дает нам,
(5^6)-1 = 0 mod 7
(5 ^ 6) -1 равно
4 * 5^5 + 4 * 5^4 + 4 * 5^3 + 4 * 5^2 + 4 * 5 + 4
Это число в форме основания 5 и, следовательно, мы можем видеть, что этот метод можно использовать для перехода от любого генератора случайных чисел к любому другому генератору случайных чисел. Хотя при экспоненте p-1 всегда вводится небольшое смещение в направлении 0.
Предполагая, что rand (n) означает "случайное целое в равномерном распределении от 0 до n-1", здесь код образец с использованием Pandon randint, который имеет этот эффект. Он использует только randint (5) и константы для создания эффекта randint (7). Немного глупо, на самом деле
from random import randint
sum = 7
while sum >= 7:
first = randint(0,5)
toadd = 9999
while toadd>1:
toadd = randint(0,5)
if toadd:
sum = first+5
else:
sum = first
assert 7>sum>=0
print sum
Постановка правильного ответа Адама Розенфилда такова:
Когда n равно 2, у вас есть 4 возможности отбрасывания: y = {22, 23, 24, 25}. Если вы используете n равным 6, у вас есть только 1 отбрасывание: y = {15625}.
5 ^ 6 = 15625
7 * 2232 = 15624
Вы вызываете rand5 еще раз. Однако у вас гораздо меньше шансов получить значение выброса (или бесконечный цикл). Если есть способ получить возможное значение выброса для y, я еще не нашел его.
Вот мой ответ:
static struct rand_buffer {
unsigned v, count;
} buf2, buf3;
void push (struct rand_buffer *buf, unsigned n, unsigned v)
{
buf->v = buf->v * n + v;
++buf->count;
}
#define PUSH(n, v) push (&buf##n, n, v)
int rand16 (void)
{
int v = buf2.v & 0xf;
buf2.v >>= 4;
buf2.count -= 4;
return v;
}
int rand9 (void)
{
int v = buf3.v % 9;
buf3.v /= 9;
buf3.count -= 2;
return v;
}
int rand7 (void)
{
if (buf3.count >= 2) {
int v = rand9 ();
if (v < 7)
return v % 7 + 1;
PUSH (2, v - 7);
}
for (;;) {
if (buf2.count >= 4) {
int v = rand16 ();
if (v < 14) {
PUSH (2, v / 7);
return v % 7 + 1;
}
PUSH (2, v - 14);
}
// Get a number between 0 & 25
int v = 5 * (rand5 () - 1) + rand5 () - 1;
if (v < 21) {
PUSH (3, v / 7);
return v % 7 + 1;
}
v -= 21;
PUSH (2, v & 1);
PUSH (2, v >> 1);
}
}
Это немного сложнее, чем другие, но я считаю, что это сводит к минимуму призывы к rand5. Как и в случае с другими решениями, существует небольшая вероятность того, что он может зацикливаться в течение длительного времени.
Простой и эффективный:
int rand7 ( void )
{
return 4; // this number has been calculated using
// rand5() and is in the range 1..7
}
(Вдохновленный Какой ваш любимый "программист" мультфильм?).
До тех пор, пока на выбор не останется семь возможностей, нарисуйте еще одно случайное число, которое умножит количество возможностей на пять. В Perl:
$num = 0;
$possibilities = 1;
sub rand7
{
while( $possibilities < 7 )
{
$num = $num * 5 + int(rand(5));
$possibilities *= 5;
}
my $result = $num % 7;
$num = int( $num / 7 );
$possibilities /= 7;
return $result;
}
Мне не нравятся диапазоны, начинающиеся с 1, поэтому я начну с 0: -)
unsigned rand5()
{
return rand() % 5;
}
unsigned rand7()
{
int r;
do
{
r = rand5();
r = r * 5 + rand5();
r = r * 5 + rand5();
r = r * 5 + rand5();
r = r * 5 + rand5();
r = r * 5 + rand5();
} while (r > 15623);
return r / 2232;
}
Там вы идете, равномерное распределение и нулевые вызовы rand5.
def rand7:
seed += 1
if seed >= 7:
seed = 0
yield seed
Необходимо заранее установить семя.
Я знаю, что на это был дан ответ, но похоже, что это работает нормально, но я не могу сказать, есть ли у него предвзятость. Мое "тестирование" предполагает, что это, по крайней мере, разумно.
Возможно, Адам Розенфилд был бы доволен, чтобы прокомментировать?
Моя (наивная?) идея такова:
Накопить rand5 до тех пор, пока не будет достаточно случайных бит для создания rand7. Это занимает не более 2 rand5. Чтобы получить номер rand7, я использую накопленное значение mod 7.
Чтобы избежать переполнения аккумулятора, и поскольку накопитель является модулем 7, я беру модем 7 аккумулятора:
(5a + rand5) % 7 = (k*7 + (5a%7) + rand5) % 7 = ( (5a%7) + rand5) % 7
Функция rand7() следует:
(пусть диапазон rand5 равен 0-4, а rand7 равно 0-6.)
int rand7(){
static int a=0;
static int e=0;
int r;
a = a * 5 + rand5();
e = e + 5; // added 5/7ths of a rand7 number
if ( e<7 ){
a = a * 5 + rand5();
e = e + 5; // another 5/7ths
}
r = a % 7;
e = e - 7; // removed a rand7 number
a = a % 7;
return r;
}
Изменить: Добавлены результаты для 100 миллионов проб.
"Реальные" функции rand mod 5 или 7
rand5: avg = 1.999802 0: 20003944 1:19999889 2: 20003690 3: 19996938 4: 19995539 rand7: avg = 3,000111 0: 14282851 1:14282879 2: 14284554 3: 14288546 4: 14292388 5: 14288736 6: 14280046
Мой rand7
Среднее значение выглядит нормально, а числовые распределения выглядят нормально.
randt: avg = 3.000080 0: 14288793 1:14280135 2: 14287848 3: 14285277 4: 14286341 5: 14278663 6: 14292943
Есть изящные алгоритмы, приведенные выше, но здесь один из способов приблизиться к нему, хотя он может быть окольным. Я принимаю значения, полученные из 0.
R2 = генератор случайных чисел, дающий значения менее 2 (пространство образца = {0, 1})
R8 = генератор случайных чисел, дающий значения менее 8 (пространство образца = {0, 1, 2, 3, 4, 5, 6, 7})
Чтобы генерировать R8 из R2, вы будете запускать R2 трижды и использовать комбинированный результат всех трех прогонов как двоичное число с 3 цифрами. Ниже приведен диапазон значений, когда R2 запускается три раза:
0 0 0 → 0
.
.
1 1 1 → 7
Теперь, чтобы сгенерировать R7 из R8, мы снова запускаем R7, если он возвращает 7:
int R7() {
do {
x = R8();
} while (x > 6)
return x;
}
Круговое решение должно генерировать R2 из R5 (точно так же, как мы породили R7 из R8), тогда R8 из R2, а затем R7 из R8.
Здесь решение, которое полностью помещается в целые числа и находится в пределах около 4% от оптимального (т.е. использует 1,26 случайных чисел в {0..4} для каждого из {0..6}). Код в Scala, но математика должна быть достаточно понятной на любом языке: вы воспользуетесь тем, что 7 ^ 9 + 7 ^ 8 очень близко к 5 ^ 11. Таким образом, вы выбираете 11-значное число в базе 5, а затем интерпретируете его как 9-значное число в базе 7, если оно находится в диапазоне (дает 9 базовых 7 чисел), или как 8-значное число, если оно превышает 9-значное число и т.д..
abstract class RNG {
def apply(): Int
}
class Random5 extends RNG {
val rng = new scala.util.Random
var count = 0
def apply() = { count += 1 ; rng.nextInt(5) }
}
class FiveSevener(five: RNG) {
val sevens = new Array[Int](9)
var nsevens = 0
val to9 = 40353607;
val to8 = 5764801;
val to7 = 823543;
def loadSevens(value: Int, count: Int) {
nsevens = 0;
var remaining = value;
while (nsevens < count) {
sevens(nsevens) = remaining % 7
remaining /= 7
nsevens += 1
}
}
def loadSevens {
var fivepow11 = 0;
var i=0
while (i<11) { i+=1 ; fivepow11 = five() + fivepow11*5 }
if (fivepow11 < to9) { loadSevens(fivepow11 , 9) ; return }
fivepow11 -= to9
if (fivepow11 < to8) { loadSevens(fivepow11 , 8) ; return }
fivepow11 -= to8
if (fivepow11 < 3*to7) loadSevens(fivepow11 % to7 , 7)
else loadSevens
}
def apply() = {
if (nsevens==0) loadSevens
nsevens -= 1
sevens(nsevens)
}
}
Если вы вставляете тест в интерпретатор (на самом деле REPL), вы получаете:
scala> val five = new Random5
five: Random5 = [email protected]
scala> val seven = new FiveSevener(five)
seven: FiveSevener = [email protected]
scala> val counts = new Array[Int](7)
counts: Array[Int] = Array(0, 0, 0, 0, 0, 0, 0)
scala> var i=0 ; while (i < 100000000) { counts( seven() ) += 1 ; i += 1 }
i: Int = 100000000
scala> counts
res0: Array[Int] = Array(14280662, 14293012, 14281286, 14284836, 14287188,
14289332, 14283684)
scala> five.count
res1: Int = 125902876
Распределение хорошее и плоское (в пределах примерно 10 к 1/7 от 10 ^ 8 в каждом бункере, как и ожидалось от гауссова распределения).
Используя общее число показов, вы можете
Обе эти проблемы являются проблемой с упрощенными решениями rand(5)+rand(5).... Следующий код Python показывает, как его реализовать (большинство из этого доказывает распределение).
import random
x = []
for i in range (0,7):
x.append (0)
t = 0
tt = 0
for i in range (0,700000):
########################################
##### qq.py #####
r = int (random.random () * 5)
t = (t + r) % 7
########################################
##### qq_notsogood.py #####
#r = 20
#while r > 6:
#r = int (random.random () * 5)
#r = r + int (random.random () * 5)
#t = r
########################################
x[t] = x[t] + 1
tt = tt + 1
high = x[0]
low = x[0]
for i in range (0,7):
print "%d: %7d %.5f" % (i, x[i], 100.0 * x[i] / tt)
if x[i] < low:
low = x[i]
if x[i] > high:
high = x[i]
diff = high - low
print "Variation = %d (%.5f%%)" % (diff, 100.0 * diff / tt)
И этот результат показывает результаты:
pax$ python qq.py
0: 99908 14.27257
1: 100029 14.28986
2: 100327 14.33243
3: 100395 14.34214
4: 99104 14.15771
5: 99829 14.26129
6: 100408 14.34400
Variation = 1304 (0.18629%)
pax$ python qq.py
0: 99547 14.22100
1: 100229 14.31843
2: 100078 14.29686
3: 99451 14.20729
4: 100284 14.32629
5: 100038 14.29114
6: 100373 14.33900
Variation = 922 (0.13171%)
pax$ python qq.py
0: 100481 14.35443
1: 99188 14.16971
2: 100284 14.32629
3: 100222 14.31743
4: 99960 14.28000
5: 99426 14.20371
6: 100439 14.34843
Variation = 1293 (0.18471%)
Простейший rand(5)+rand(5), игнорируя случаи, когда это возвращает более 6, имеет типичное изменение в 18%, в 100 раз больше, чем у метода, показанного выше:
pax$ python qq_notsogood.py
0: 31756 4.53657
1: 63304 9.04343
2: 95507 13.64386
3: 127825 18.26071
4: 158851 22.69300
5: 127567 18.22386
6: 95190 13.59857
Variation = 127095 (18.15643%)
pax$ python qq_notsogood.py
0: 31792 4.54171
1: 63637 9.09100
2: 95641 13.66300
3: 127627 18.23243
4: 158751 22.67871
5: 126782 18.11171
6: 95770 13.68143
Variation = 126959 (18.13700%)
pax$ python qq_notsogood.py
0: 31955 4.56500
1: 63485 9.06929
2: 94849 13.54986
3: 127737 18.24814
4: 159687 22.81243
5: 127391 18.19871
6: 94896 13.55657
Variation = 127732 (18.24743%)
И, по совету Nixuz, я очистил script, чтобы вы могли просто извлечь и использовать материал rand7...:
import random
# rand5() returns 0 through 4 inclusive.
def rand5():
return int (random.random () * 5)
# rand7() generator returns 0 through 6 inclusive (using rand5()).
def rand7():
rand7ret = 0
while True:
rand7ret = (rand7ret + rand5()) % 7
yield rand7ret
# Number of test runs.
count = 700000
# Work out distribution.
distrib = [0,0,0,0,0,0,0]
rgen =rand7()
for i in range (0,count):
r = rgen.next()
distrib[r] = distrib[r] + 1
# Print distributions and calculate variation.
high = distrib[0]
low = distrib[0]
for i in range (0,7):
print "%d: %7d %.5f" % (i, distrib[i], 100.0 * distrib[i] / count)
if distrib[i] < low:
low = distrib[i]
if distrib[i] > high:
high = distrib[i]
diff = high - low
print "Variation = %d (%.5f%%)" % (diff, 100.0 * diff / count)
Этот ответ - скорее эксперимент по получению наибольшей энтропии, возможной из функции Rand5. t поэтому несколько неясен и почти наверняка намного медленнее других реализаций.
Предполагая равномерное распределение от 0-4 и получим равномерное распределение от 0-6:
public class SevenFromFive
{
public SevenFromFive()
{
// this outputs a uniform ditribution but for some reason including it
// screws up the output distribution
// open question Why?
this.fifth = new ProbabilityCondensor(5, b => {});
this.eigth = new ProbabilityCondensor(8, AddEntropy);
}
private static Random r = new Random();
private static uint Rand5()
{
return (uint)r.Next(0,5);
}
private class ProbabilityCondensor
{
private readonly int samples;
private int counter;
private int store;
private readonly Action<bool> output;
public ProbabilityCondensor(int chanceOfTrueReciprocal,
Action<bool> output)
{
this.output = output;
this.samples = chanceOfTrueReciprocal - 1;
}
public void Add(bool bit)
{
this.counter++;
if (bit)
this.store++;
if (counter == samples)
{
bool? e;
if (store == 0)
e = false;
else if (store == 1)
e = true;
else
e = null;// discard for now
counter = 0;
store = 0;
if (e.HasValue)
output(e.Value);
}
}
}
ulong buffer = 0;
const ulong Mask = 7UL;
int bitsAvail = 0;
private readonly ProbabilityCondensor fifth;
private readonly ProbabilityCondensor eigth;
private void AddEntropy(bool bit)
{
buffer <<= 1;
if (bit)
buffer |= 1;
bitsAvail++;
}
private void AddTwoBitsEntropy(uint u)
{
buffer <<= 2;
buffer |= (u & 3UL);
bitsAvail += 2;
}
public uint Rand7()
{
uint selection;
do
{
while (bitsAvail < 3)
{
var x = Rand5();
if (x < 4)
{
// put the two low order bits straight in
AddTwoBitsEntropy(x);
fifth.Add(false);
}
else
{
fifth.Add(true);
}
}
// read 3 bits
selection = (uint)((buffer & Mask));
bitsAvail -= 3;
buffer >>= 3;
if (selection == 7)
eigth.Add(true);
else
eigth.Add(false);
}
while (selection == 7);
return selection;
}
}
Количество бит, добавленных в буфер для каждого звонка в Rand5, в настоящее время составляет 4/5 * 2, поэтому 1.6. Если включено значение вероятности 1/5, которое увеличивается на 0,05 и 1,65, но см. Комментарий в коде, где мне пришлось отключить это.
Биты, потребляемые по вызову Rand7 = 3 + 1/8 * (3 + 1/8 * (3 + 1/8 * (...) Это 3 + 3/8 + 3/64 + 3/512... примерно 3,42
Извлекая информацию из семерки, я возвращаю 1/8 * 1/7 бит за вызов, поэтому около 0,018
Это дает чистое потребление 3,4 бит на звонок, что означает, что отношение равно 2,255 звонков на Rand5 для каждого Rand7. Оптимальным должен быть 2.1.
Я бы предположил, что этот подход значительно медленнее, чем многие другие, если только стоимость вызова Rand5 не является чрезвычайно дорогостоящей (например, вызывая какой-то внешний источник энтропии).
extern int r5();
int r7() {
return ((r5() & 0x01) << 2 ) | ((r5() & 0x01) << 1 ) | (r5() & 0x01);
}
в php
function rand1to7() {
do {
$output_value = 0;
for ($i = 0; $i < 28; $i++) {
$output_value += rand1to5();
}
while ($output_value != 140);
$output_value -= 12;
return floor($output_value / 16);
}
чтобы создать случайное число между 16 и 127, делит на шестнадцать, чтобы создать поплавок между 1 и 7.9375, затем округляется вниз, чтобы получить int между 1 и 7. Если я не ошибаюсь, есть 16/112 шанс получить любой из 7 результатов.
Вам нужна функция rand1_7(), я написал rand1_5(), чтобы вы могли ее протестировать и построить.
import numpy
def rand1_5():
return numpy.random.randint(5)+1
def rand1_7():
q = 0
for i in xrange(7): q+= rand1_5()
return q%7 + 1
просто масштабируйте свой вывод с первой функции
0) you have a number in range 1-5
1) subtract 1 to make it in range 0-4
2) multiply by (7-1)/(5-1) to make it in range 0-6
3) add 1 to increment the range: Now your result is in between 1-7