Я хочу генерировать случайные числа вручную. Я знаю, что на каждом языке есть ранды или случайные функции, но мне любопытно знать, как это работает. У кого-нибудь есть код для этого?Как вручную генерировать случайные числа
Посмотрите на следующие:
Linear Congruential Generator - популярный подход также используется в Java
List of Random Number Generators
А вот еще link разрабатывающее на использовании LCG в Java Случайный класс
http://en.wikipedia.org/wiki/Random_number_generator
Описаны различные типы генераторов случайных чисел и как они создаются.
Я предполагаю, что вы mea n псевдослучайных чисел. Самый простой, который я знаю (от написания игр с видеоиграми на старых машинах), работал следующим образом:
seed = seed * 5 + 1;
Вы делаете это каждый раз, когда вызывается случайный вызов, а затем вы используете все, что вам нужно. * 5 + 1 имеет приятное свойство (IIRC), чтобы поразить все возможности до повторения, независимо от того, сколько бит вы смотрите.
Недостатком, конечно же, является его предсказуемость. Но это не имело значения в играх. Мы хватали случайные числа, как сумасшедшие для всех видов вещей, и вы никогда не узнаете, какое число будет дальше.
Сделайте пару таких вещей параллельно и объедините результаты. Это линейный конгруэнтный генератор.
POSIX.1-2001 дает следующий пример реализации rand() и srand(), возможно полезный, когда требуется одна и та же последовательность на двух разных машинах.
static unsigned long next = 1;
/* RAND_MAX assumed to be 32767 */
int myrand(void) {
next = next * 1103515245 + 12345;
return((unsigned)(next/65536) % 32768);
}
void mysrand(unsigned seed) {
next = seed;
}
Aloha!
Ручным способом вы имеете в виду «не используя компьютер» или «написать собственный код»?
Если вы не используете компьютер, вы можете использовать такие вещи, как кости, цифры в сумке и все те методы, которые видны по телевизору, когда они выбирают команды, выигрывают серии Bingo и т. Д. Лас-Вегас заполнен такими методами, которые используются в процессах (игры), направленные на то, чтобы дать вам плохие шансы и рентабельность инвестиций. Вы также можете получить большую RAND книгу и перейти к случайно выбранной странице:
http://www.amazon.com/Million-Random-Digits-Normal-Deviates/dp/0833030477
(Кроме того, для некоторого развлечения, читать отзывы)
Для написания собственного кода вам необходимо рассмотреть, почему не используя систему, при условии, что RNG недостаточно хорош. Если вы используете современную ОС, у нее будет RNG, доступный для пользовательских программ, которые должны быть достаточно хороши для вашего приложения.
Если вам действительно нужно реализовать свои собственные, существует огромная совокупность генераторов.Для небезопасного использования вы можете посмотреть цепи LFSR, конгруэнтные генераторы и т. Д. Независимо от того, какое распределение вам необходимо (равномерное, нормальное, экспоненциальное и т. Д.), Вы сможете найти описания алгоритмов и библиотеки с реализациями.
Для использования в целях безопасности вы должны смотреть на такие вещи, как Yarrow/Fortuna, NIST SP 800-89, указанные PRNG и RFC 4086 для получения хороших источников энтропии, необходимых для подачи PRNG. Или еще лучше, используйте тот, который находится в ОС, который должен отвечать требованиям безопасности RNG.
Реализация ГСЧ может быть интересным упражнением, но очень редко требуется. И не изобретайте свой собственный алгоритм, если он не предназначен для игрушечных приложений. НЕ повторяйте НЕ изобретать RNG для приложений безопасности (например, генерировать криптографические ключи), по крайней мере, если вы не прочитаете и не просмотрите серипус. Вы поблагодарите меня за это (надеюсь).
A nit: «Вы также можете получить отличную книгу RAND и перейти на случайно выбранную страницу». Это было бы сильно предвзято по отношению к тем, какие числа оказались в середине книги в верхней части страницы. Люди - ужасные ГСЧ. – Malvolio
Обращение к определенной странице книги истинных случайных чисел не приводит к смещению результата, если вы не используете повторно номера, потому что числа в середине книги так же случайны, как и на переднем плане. Повторное использование чисел будет искажать результат, независимо от того, на какой странице он их выбирает. –
hopefuly im не избыточно, потому что я havent прочитал все ссылки, но я считаю, что вы можете приблизиться к true случайный генератор. в наши дни системы часто настолько сложны, что даже лучшим вундеркиндам нужно много времени, чтобы понять Что происходит внутри :)
просто откройте свой разум и подумайте, можете ли вы контролировать какое-то глобальное системное свойство, использовать его для посева. выбрать сетевой пакет (не предназначен для вас?) и вычислить «что-то» из его содержимого и использовать его для посева до ... и т. д.
вы можете спроектировать лучшее для ваших нужд со всеми этими подсказками;)
static void Main()
{
DateTime currentTime = DateTime.Now;
int maxValue = 100;
int hour = currentTime.Hour;
int minute = currentTime.Minute;
int second = currentTime.Second;
int milisecond = currentTime.Millisecond;
int randNum = (((hour + 1) * (minute + 1) * (second + 1) * milisecond) % maxValue);
Console.WriteLine(randNum);
Console.ReadLine();
}
Выше показан очень простой фрагмент кода для генерации случайных чисел. Это консольная программа, написанная на C#. Если вы знаете какое-либо базовое программирование, это должно быть понятно и легко конвертировать в любой желаемый язык.
DateTime просто принимает текущую дату и время, большинство языков программирования имеют возможность сделать это.
Переменные часа, минуты, секунды и милисекунды изменяют значение даты в его составных частях. Нас интересуют только эти части, поэтому можно игнорировать день. Опять же, в большинстве языков даты и время обычно представлены в виде строк. В .Net у нас есть возможности, позволяющие легко анализировать эту информацию. Но в большинстве других языков, где времена представлены в виде строк, не слишком сложно разобрать строку для тех частей, которые вы хотите, и преобразовать их в свои числа. Эти объекты обычно предоставляются даже на самых старых языках.
Семена по существу дают нам начальный номер, который всегда меняется. Традиционно вы просто умножаете это число на десятичное значение от 0 до 1, это отсекает этот шаг.
Верхний диапазон определяет максимальное значение. Таким образом, число сгенерированных никогда не будет выше этого значения. Также он никогда не будет ниже 0. Так что никаких ньюгейтов. Но если вы хотите негативы, вы можете просто отменить это вручную. (Умножением его на -1)
Фактическая переменная randNumis то, что имеет место случайное значение, которое вы заинтересованы.
Хитрость заключается в том, чтобы получить остаток (модуль упругости) после деления семян в верхнем диапазоне. Остаток всегда будет меньше, чем делитель, который в этом случае равен 100. Простые математики говорят вам, что вы не можете иметь остаток больше дивизора. Итак, если вы разделите на 10, у вас не будет остатка больше 10. Именно этот простой закон дает нам наше случайное число от 0 до 100 в этом случае.
Пульт console.writeline просто выводит его на экран.
Консоль .readline просто приостанавливает программу, чтобы вы могли ее увидеть.
Это очень простой фрагмент кода для генерации случайных чисел. Если вы запускаете эту программу с той же самой интервал каждый день (но вам нужно будет делать это в один и тот же час, минуту, секунду и milisecond) в течение более 1 дня, вы начнете генерировать одинаковый набор чисел снова и снова дополнительный день. Это связано с тем, что оно привязано к времени. Это разрешение генератора. Поэтому, если вы знаете код этой программы и время ее запуска, вы можете предсказать число сгенерированных, но это будет нелегко. Вот почему я использовал милисекунды. Используйте секунды или минуты, чтобы увидеть, что я имею в виду. Таким образом, вы можете написать таблицу, показывающую, когда 1 входит, 0 выходит, когда 2 идет в 0 выходит и так далее. Затем вы можете прогнозировать вывод на каждую секунду и диапазон чисел. Чем больше вы увеличиваете разрешение (увеличивая число, которое изменяется), тем сложнее оно и тем больше времени требуется, чтобы получить предсказуемый шаблон. Этот метод достаточно хорош для большинства людей.
Это старый школьный способ создания случайных чисел для базовых игр. Это нужно было быстро и просто. Это. Это также подчеркивает, почему, случайные числа генаараторы на самом деле не случайны, а psudo random.
Надеюсь, это разумный ответ на ваш вопрос.
Mersenne twister имеет очень длительный период (2^19937-1).
Вот очень простая реализация в C++:
struct MT{
unsigned int *mt, k, g;
~MT(){ delete mt; }
MT(unsigned int seed) : mt(new unsigned int[624]), k(0), g(0){
for (int i=0; i<624; i++)
mt[i]=!i?seed:(1812433253U*(mt[i-1]^(mt[i-1]>>30))+i);
}
unsigned int operator()(){
unsigned int q=(mt[k]&0x80000000U)|(mt[(k+1)%624]&0x7fffffffU);
mt[k]=mt[(k+397)%624]^(q>>1)^((q&1)?0x9908b0dfU:0);
unsigned int y = mt[k];
y ^= (y >> 11);
y ^= (y << 7) & 0x9d2c5680U;
y ^= (y << 15) & 0xefc60000U;
y ^= (y >> 18);
k = (k+1)%624;
return y;
}
};
Один хороший способ получить случайные числа, чтобы контролировать уровень окружающего шума, проходящий через микрофон вашего компьютера. Если вы можете получить драйвер (или язык, поддерживающий вход микрофона) и преобразовать его в число, вы уже на пути!
Было также изучено, как получить «истинную случайность» - поскольку компьютеры - это не что иное, как двоичные машины, они не могут дать нам «истинную случайность». Через некоторое время последовательность начнет повторяться. Стремление к лучшему генерации случайных чисел все еще продолжается, но говорят, что мониторинг уровня окружающего шума в комнате - один из хороших способов предотвратить формирование шаблона в вашей случайной генерации.
Вы можете найти this wiki article для получения дополнительной информации о науке за генерацией случайных чисел.
Это document - очень хорошая запись генерации псевдослучайных чисел и включает в себя ряд подпрограмм (в C). В нем также обсуждается необходимость в соответствующем посеве генераторов случайных чисел (см. Правило 3). Особенно полезной для этого является использование/dev/randon/(если вы работаете на Linux-машине).
Примечание: подпрограммы, включенные в этот документ, являются alot проще для кода, чем для Mersenne Twister. См. Также генератор WELLRNG, который должен иметь лучшие теоретические свойства, в качестве альтернативы MT.
Прочтите книгу рандов случайных чисел (monte carlo book of random numbers), цифры в ней случайным образом сгенерированы для вас !!! Мой дед работал на ранда.
Если вы ищете теоретическое лечение случайных чисел, возможно, вы можете взглянуть на Том 2 Искусство компьютерного программирования. В нем есть глава, посвященная случайным числам. Посмотрите, поможет ли вам это.
Большинство RNG (генераторы случайных чисел) потребует небольшой инициализации. Обычно это выполняют операцию посева и сохраняют результаты посевных значений для последующего использования. Вот пример метода высева из случайных чисел я написал для игрового движка:
/// <summary>
/// Initializes the number array from a seed provided by <paramref name="seed">seed</paramref>.
/// </summary>
/// <param name="seed">Unsigned integer value used to seed the number array.</param>
private void Initialize(uint seed)
{
this.randBuf[0] = seed;
for (uint i = 1; i < 100; i++)
{
this.randBuf[i] = (uint)(this.randBuf[i - 1] >> 1) + i;
}
}
Это вызывается из конструктора класса рандомизации. Теперь реальные случайные числа могут быть свернуты/вычислены с использованием вышеупомянутых высеваемых значений. Обычно здесь применяется алгоритм рандомизации. Вот еще один пример:
/// <summary>
/// Refreshes the list of values in the random number array.
/// </summary>
private void Roll()
{
for (uint i = 0; i < 99; i++)
{
uint y = this.randBuf[i + 1] * 3794U;
this.randBuf[i] = (((y >> 10) + this.randBuf[i])^this.randBuf[(i + 399) % 100]) + i;
if ((this.randBuf[i] % 2) == 1)
{
this.randBuf[i] = (this.randBuf[i + 1] << 21)^(this.randBuf[i + 1] * (this.randBuf[i + 1] & 30));
}
}
}
Теперь свернутые значения сохраняются для последующего использования в этом примере, но эти цифры могут быть рассчитаны на лету. Потенциал роста до предварительного расчета - небольшое увеличение производительности. В зависимости от используемого алгоритма, свернутые значения могут быть напрямую возвращены или проходить через некоторые вычисления в последнюю минуту по запросу кода. Вот пример, который принимает от prerolled значений и выплевывает очень хорошо выглядящий псевдо случайное число:
/// <summary>
/// Retrieves a value from the random number array.
/// </summary>
/// <returns>A randomly generated unsigned integer</returns>
private uint Random()
{
if (this.index == 0)
{
this.Roll();
}
uint y = this.randBuf[this.index];
y = y^(y >> 11);
y = y^((y << 7) + 3794);
y = y^((y << 15) + 815);
y = y^(y >> 18);
this.index = (this.index + 1) % 100;
return y;
}
Если вы желаете, чтобы вручную, жесткий код, свой собственный генератор случайных чисел, я не могу дать вам эффективности, однако я могу дать вам надежность. Я на самом деле решил написать код, используя время, чтобы проверить скорость обработки компьютера, посчитав во времени, и это превратилось во мне, написав мой собственный генератор случайных чисел, используя алгоритм подсчета для modulo (счетчик случайный). Пожалуйста, попробуйте это для себя и проверьте распределение чисел в рамках большого теста. Кстати, это написано на питоне.
def count_in_time(n):
import time
count = 0
start_time = time.clock()
end_time = start_time + n
while start_time < end_time:
count += 1
start_time += (time.clock() - start_time)
return count
def generate_random(time_to_count, range_nums, rand_lst_size):
randoms = []
iterables = range(range_nums)
count = 0
for i in range(rand_lst_size):
count += count_in_time(time_to_count)
randoms.append(iterables[count%len(iterables)])
return randoms
Это ужасный выбор a, c и m! – derobert
Ха-ха. Да, но в первый раз, когда я видел эту рутину, на машине с частотой 1 МГц. :-) – Nosredna