Как я могу легко генерировать случайные числа в соответствии с нормальным распределением в C или C ++?
Я не хочу использовать Boost.
Я знаю, что Кнут подробно рассказывает об этом, но сейчас у меня под рукой нет его книг.
Как я могу легко генерировать случайные числа в соответствии с нормальным распределением в C или C ++?
Я не хочу использовать Boost.
Я знаю, что Кнут подробно рассказывает об этом, но сейчас у меня под рукой нет его книг.
Ответы:
Существует множество методов генерации чисел с распределением по Гауссу из обычного ГСЧ .
Преобразование Бокса-Мюллера обычно используется. Он правильно производит значения с нормальным распределением. Математика проста. Вы генерируете два (однородных) случайных числа, и применяя к ним формулу, вы получаете два нормально распределенных случайных числа. Верните один, а другой сохраните для следующего запроса случайного числа.
источник
std::normal_distribution
что делает именно то, что вы просите, не вдаваясь в математические детали.C ++ 11
С ++ 11 предлагает
std::normal_distribution
, и я бы пошел именно по этому пути.C или более ранний C ++
Вот несколько решений в порядке возрастания сложности:
Добавьте 12 одинаковых случайных чисел от 0 до 1 и вычтите 6. Это будет соответствовать среднему значению и стандартному отклонению нормальной переменной. Очевидным недостатком является то, что диапазон ограничен до ± 6 - в отличие от истинного нормального распределения.
Преобразование Бокса-Мюллера. Это перечислено выше и относительно просто реализовать. Однако, если вам нужны очень точные образцы, имейте в виду, что преобразование Бокса-Мюллера в сочетании с некоторыми однородными генераторами страдает аномалией, называемой эффектом Neave 1 .
Для большей точности я предлагаю нарисовать униформу и применить обратное кумулятивное нормальное распределение, чтобы получить нормально распределенные переменные. Вот очень хороший алгоритм для обратных кумулятивных нормальных распределений.
1. HR Neave, "Об использовании преобразования Бокса-Мюллера с мультипликативными конгруэнтными генераторами псевдослучайных чисел", Applied Statistics, 22, 92-97, 1973
источник
Быстрый и простой способ - просто просуммировать несколько равномерно распределенных случайных чисел и взять их среднее значение. См. Центральную предельную теорему для полного объяснения того, почему это работает.
источник
Я создал проект с открытым исходным кодом C ++ для теста генерации нормально распределенных случайных чисел .
Он сравнивает несколько алгоритмов, в том числе
cpp11random
использует C ++ 11std::normal_distribution
withstd::minstd_rand
(на самом деле это преобразование Бокса-Мюллера в clang).Результаты
float
версии single-precision ( ) на iMac Corei5-3330S@2.70GHz, clang 6.1, 64-bit:Для правильности программа проверяет среднее значение, стандартное отклонение, асимметрию и эксцесс образцов. Было обнаружено, что метод CLT путем суммирования 4, 8 или 16 однородных чисел не имеет хорошего эксцесса, как другие методы.
Алгоритм зиккурата имеет лучшую производительность, чем другие. Однако он не подходит для параллелизма SIMD, так как требует поиска в таблице и переходов. Box-Muller с набором инструкций SSE2 / AVX намного быстрее (x1,79, x2,99), чем не-SIMD версия алгоритма зиккурата.
Поэтому я предлагаю использовать Box-Muller для архитектуры с наборами инструкций SIMD, в противном случае это может быть зиккуратным.
PS тест использует простейший LCG PRNG для генерации равномерно распределенных случайных чисел. Поэтому для некоторых приложений этого может быть недостаточно. Но сравнение производительности должно быть справедливым, потому что все реализации используют один и тот же PRNG, поэтому тест в основном проверяет производительность преобразования.
источник
Вот пример C ++, основанный на некоторых ссылках. Это быстро и грязно, лучше не изобретать заново и не использовать библиотеку ускорения.
Вы можете использовать график QQ, чтобы изучить результаты и посмотреть, насколько хорошо оно приближается к реальному нормальному распределению (ранжируйте ваши образцы 1..x, превратите ранги в пропорции от общего количества x, т.е. сколько образцов, получите z-значения и начертите их. Желаемый результат - прямая линия вверх).
источник
Используйте
std::tr1::normal_distribution
.Пространство имен std :: tr1 не является частью boost. Это пространство имен, которое содержит дополнения к библиотеке из Технического отчета C ++ 1 и доступно в современных компиляторах Microsoft и gcc, независимо от boost.
источник
Вот как вы создаете образцы на современном компиляторе C ++.
источник
generator
действительно должны быть посеяны.Вы можете использовать GSL . Даны несколько полных примеров, чтобы продемонстрировать, как его использовать.
источник
Взгляните на: http://www.cplusplus.com/reference/random/normal_distribution/ . Это самый простой способ получить нормальные распределения.
источник
Если вы используете C ++ 11, вы можете использовать
std::normal_distribution
:Есть много других распределений, которые можно использовать для преобразования вывода механизма случайных чисел.
источник
Я следил за определением PDF-файла, приведенным в http://www.mathworks.com/help/stats/normal-distribution.html, и пришел к следующему:
Возможно, это не лучший подход, но он довольно простой.
источник
rand()
изRANDU
возвращает ноль, так как Ln (0) не определено.cos(2*pi*rand/RAND_MAX)
, а вы умножаете на(rand()%2 ? -1.0 : 1.0)
.Список часто задаваемых вопросов на comp.lang.c содержит три различных способа простого генерирования случайных чисел с распределением Гаусса.
Вы можете взглянуть на это: http://c-faq.com/lib/gaussian.html
источник
Реализация Бокса-Мюллера:
источник
Существуют различные алгоритмы обратного кумулятивного нормального распределения. Самые популярные в количественном финансировании тестируются на http://chasethedevil.github.io/post/monte-carlo--inverse-cumulative-normal-distribution/
На мой взгляд, существует не так много стимулов для использования что - то другое , чем алгоритм AS241 от Wichura : это машина точность, надежность и быстро. Узкие места редко возникают при генерации гауссовских случайных чисел.
Кроме того, он показывает недостатки зиккуратоподобных подходов.
Главный ответ здесь выступает за Box-Müller, вы должны знать, что у него есть известные недостатки. Цитирую https://www.sciencedirect.com/science/article/pii/S0895717710005935 :
источник
1) Графически интуитивно понятный способ генерации гауссовских случайных чисел - это использование чего-то похожего на метод Монте-Карло. Вы должны сгенерировать случайную точку в рамке вокруг кривой Гаусса, используя генератор псевдослучайных чисел в C. Вы можете вычислить, находится ли эта точка внутри или под распределением Гаусса, используя уравнение распределения. Если эта точка находится внутри распределения Гаусса, то у вас есть гауссовское случайное число в качестве значения x точки.
Этот метод не идеален, потому что технически кривая Гаусса стремится к бесконечности, и вы не можете создать коробку, которая приближается к бесконечности в измерении x. Но кривая Гуасса довольно быстро приближается к 0 в измерении y, так что я не буду об этом беспокоиться. Ограничение размера ваших переменных в C может быть более ограничивающим фактором для вашей точности.
2) Другой способ - использовать Центральную предельную теорему, которая утверждает, что при добавлении независимых случайных величин они образуют нормальное распределение. Помня об этой теореме, вы можете аппроксимировать гауссовское случайное число, добавив большое количество независимых случайных величин.
Эти методы не самые практичные, но этого следует ожидать, если вы не хотите использовать уже существующую библиотеку. Имейте в виду, что этот ответ исходит от человека, практически не имеющего опыта в расчетах или статистике.
источник
Метод Монте-Карло . Наиболее интуитивно понятный способ сделать это - использовать метод Монте-Карло. Возьмите подходящий диапазон -X, + X. Большие значения X приведут к более точному нормальному распределению, но для схождения потребуется больше времени. а. Выберите случайное число z от -X до X. b. Сохраняйте с вероятностью,
N(z, mean, variance)
где N - гауссово распределение. В противном случае отбросьте и вернитесь к шагу (а).источник
Посмотри, что я нашел.
Эта библиотека использует алгоритм Зиккурата.
источник
Компьютер - детерминированное устройство. В расчетах нет случайности. Более того, арифметическое устройство в CPU может вычислять сумму по некоторому конечному набору целых чисел (выполняя вычисление в конечном поле) и конечному набору действительных рациональных чисел. А также выполнял побитовые операции. Математика имеет дело с более хорошими наборами, такими как [0.0, 1.0] с бесконечным количеством баллов.
Вы можете прослушивать какой-то провод внутри компьютера с каким-то контроллером, но будет ли он иметь равномерное распределение? Я не знаю. Но если предположить, что этот сигнал является результатом накопления значений огромного количества независимых случайных величин, то вы получите примерно нормально распределенную случайную величину (это было доказано в теории вероятностей).
Существуют алгоритмы, которые называются - генератор псевдослучайных чисел. Как я понял, цель псевдослучайного генератора - имитировать случайность. И критерий добродетели: - эмпирическое распределение сходится (в некотором смысле - поточечное, равномерное, L2) к теоретическому - значения, которые вы получаете от случайного генератора, кажутся независимыми. Конечно, это неправда с «реальной точки зрения», но мы предполагаем, что это правда.
Один из популярных методов - вы можете суммировать 12 irv с равномерными распределениями .... Но, честно говоря, при выводе центральной предельной теоремы с помощью преобразования Фурье, рядов Тейлора необходимо пару раз иметь n -> + inf предположений. Так, например, теоретически - лично я не понимаю, как люди выполняют суммирование 12 irv с равномерным распределением.
В университете я изучал теорию вероятностей. И, в частности, для меня это просто математический вопрос. В университете я увидел такую модель:
Такой способ, как это сделать, был всего лишь примером, я думаю, существуют другие способы его реализации.
Доказательство ее правильности можно найти в книге "Москва, БМГТУ, 2004: XVI Теория вероятностей, пример 6.12, с.246-247" в издании Крищенко Александра Петровича ISBN 5-7038-2485-0
К сожалению, мне неизвестно о существовании перевода этой книги на английский язык.
источник