рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Алгоритмы генераторов псевдослучайных чисел

Алгоритмы генераторов псевдослучайных чисел - раздел Философия, ИССЛЕДОВАНИЕ ОПЕРАЦИЙ. Методические указания по выполнению лабораторных работ Во Всех Языках Программирования (Pascal, C/c++, Java И Т. Д.) И В Приложе...

Во всех языках программирования (Pascal, C/C++, Java
и т. д.) и в приложениях Excel, MathCad, MathLab и др. есть стандартная функция, возвращающая случайное число. При этом существует возможность повторения одной и той же последовательности случайных чисел, например, в C++, Java. Наиболее распространенные алгоритмы, используемые в генераторах псевдослучайных чисел:

1. Линейный конгруэнтный метод (ЛКМ) − языки Borland С, Visual C++, Java, C++Builder;

2. Алгоритм Вичманна–Хилла (Wichmann–Hill) или AS 183 − языки Prolog, Python (версии 2.2 и предыдущие), Excel;

3. Алгоритм «Виток Мерсенна» (Mersenne Twister) или MT19937−Python (версии 2.3 и последующие);

4. Алгоритм Парка–Миллера;

5. Метод Фибоначчи с запаздыванием (Subtract-with-borrow Generators SWBG) −Mathematica, MatLab.

Рассмотрим эти алгоритмы.

Линейный конгруэнтный метод (ЛКМ)

В стандарте ANSI-C имеется функция , выдающая равномерно распределенные числа в интервале от 0 до , и связанная с ней функция , выполняющая начальную установку счетчика. Почти все подобные генераторы используют рекуррентную последовательность

.

Здесь равно остатку от деления на (или другими словами − это наименьший положительный вычет по модулю ). Число называется мультипликатором, число – инкрементом, а число – модулем. Ниже приведена реализация генератора ANSI-C, опубликованного в качестве «примера».

/* (в модуле stdlib.h) */

#define RAND_MAX 32767

/* "пример" от комитета ANSI-C */

unsigned long next=1; int rand(void) { next=next*1103515245+12345; return((unsigned int)(next/65536)%32768);} void srand(unsigned int seed) { next=seed;}

Значение мультипликатора и инкремента в этом примере не являются оптимальными.

Алгоритм Вичманна–Хилла (Wichmann–Hill или AS183)

Псевдослучайные числа вычисляются по формуле

,

где функция возвращает десятичную часть получившейся суммы. Рекуррентные формулы для вычисления ,
и имеют вид:

где функция возвращает целое число, равное остатку от деления. По сути, этот алгоритм есть линейная комбинация трех конгруэнтных генераторов. При этом требуется задание трёх начальных значений. Алгоритм обладает периодом (), что недостаточно для современных нужд.

 

Алгоритм «Виток Мерсенна»
(Mersenne Twister или MT19937)

Алгоритм разработан в 1997 году японскими учеными Макото Мацумото и Такуджи Нишимура. Обладает огромным периодом 219937−1 (создатели алгоритма доказали это свойство), имеет хорошее быстродействие и проходит все статистические тесты. В приложении 1 приведена реализация алгоритма на
языке С.

Алгоритм Парка−Миллера (Park, Miller)

Самая простая рекуррентная последовательность, которую можно предложить для реализации генератора равномерного распределения, имеет вид:

.

Значения констант

были предложены Park, Miller и протестированы в исследованиях Lewis, Goodman, Miller. Прямое использование этого метода возможно на языке ассемблер, но языки высокого уровня могут при этом зафиксировать переполнение. Для обхода этого Scharge предложил метод частичной факторизации модуля. Для этого модуль записывается в виде:

.

Если и , то при этом величины и всегда лежат в интервале 0,..., m-1. Для вычисления используется алгоритм:

 

t = a(z mod q)-r[z/q]

если t<0, то t += m.

(a*z)(mod m)=t.

В случае констант Парка−Миллера можно использовать значенияи .

Если требуется число вызовов, превышающее по порядку 108, то для этого случая L'Ecuyer рекомендует комбинировать две последовательностей с близкими, но отличающимися константами. В его исследованиях хороший результат был получен для значений:

m1 = 2147483563, a1 = 40014, q1 = 53668, r1 = 12211;

m2 = 2147483399, a2 = 40692, q2 = 52774, r2 = 3791.

При этом для современных компьютеров период повторения генерируемой последовательности оценивается по порядку примерно как 1018.

– Конец работы –

Эта тема принадлежит разделу:

ИССЛЕДОВАНИЕ ОПЕРАЦИЙ. Методические указания по выполнению лабораторных работ

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ... СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ ТУСУР... Кафедра автоматизированных систем управления АСУ...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Алгоритмы генераторов псевдослучайных чисел

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Псевдослучайные числа
Пригодность случайных чисел определяется не процессом их получения, а тем, что они должны обладать интересующими нас свойствами независимых, равномерно распределенных СВ.  

Метод Фибоначчи с запаздыванием
Статистические свойства чисел, генерируемых линейным конгруэнтным алгоритмом, делают невозможным их использование для решения задач, чувствительных к качеству случайных чисел. В связи с этим линейн

Оценка точности результатов, полученных методом Монте-Карло
Оценка точности результатов, полученных методом Монте-Карло, основана на центральной предельной теореме теории вероятностей, теореме Чебышева и ее следствиях. Из которых следует, что при большом об

Моделирование дискретных случайных величин
Рассмотрим дискретную СВ с рядом распределения

Моделирование случайных событий
Рассмотрим полную группу несовместных событий с вероятностями

Моделирование непрерывной случайной величины
Рассмотрим непрерывную СВ с плотностью вероятности

Экспоненциальное распределение
Случайной величине с экспоненциальной плотностью вероятности

Распределение вероятностей числа событий на интервале времени для пуассоновской СВ с параметром определяется выражением
. (14) Пуассоновский поток событий является простейшим потоком, для которого интервалы в

Гауссовская случайная величина
Гауссовская (нормальная) СВ имеет плотность вероятности

Случайная величина с логнормальным распределением
Плотность вероятности СВ с логнормальным распределением имеет вид:

Основы теории систем массового обслуживания
При решении различных задач часто приходится сталкиваться с анализом эффективности работы систем массового обслуживания (СМО). Примеры СМО: телефонная станция, ремонтные мастерские, билетные кассы,

Потоки событий
Основным понятием при рассмотрении случайных процессов, протекающих в системах с дискретными состояниями и непрерывным временем, к которым относятся СМО, является понятие потока событий

Многоканальная СМО с ожиданием
Структура многоканальной СМО показана на рис. 8. Рис. 8 Число мест в очереди равно

Основные характеристики СМО
Ниже перечислены основные характеристики СМО, определяемые при решении задач анализа. Аналитические результаты в виде формул приведены для случая пуассоновского потока заявок со средней интенсивнос

Моделирование систем массового обслуживания
Рассмотрим пример, связанный с моделированием методом Монте-Карло системы массового обслуживания. Имеется одноканальная СМО

Результаты тестирования датчиков случайных чисел
  Pascal Borland C MSVC 6.0* MSVC 2005** Python Алго- ритм ЛКМ

Критерий согласия хи-квадрат Пирсона
Критерием согласия называют статистический критерий проверки гипотезы о предполагаемом законе неизвестного распределения, полученного на основе выборочных данных. Для этого вводится количественная

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги