генерация случайных чисел с. Доклад Генерация случайных чисел. Генерация случайных чисел
 Скачать 138.14 Kb.
|
|
Федеральное государственное образовательное бюджетное учреждение высшего образования «Ульяновский государственный университет» Факультет математики информационных и авиационных технологий Доклад на тему: «Генерация случайных чисел» Выполнил студент группы: МОАИС-О-21/1 Вдовина О.Н. Ульяновск 2022 Содержание 1. Введение……………………………………………………………………3 2.Случайные числа…………………………………………………………...4 3.Метод середин квадратов фон Неймана…………………………….……5 4. Линейный конгруэнтный метод………………………………………….6 5. Другие методы…………………………………………………………….11 6.Источник литературы……………………………………………………...14 1.Введение Каждый, кто использует арифметические методы генерирования случайных чисел, безусловно, грешит (Джон Фон Нейман) О вероятности коль кто забудет, обманщиком вовек не будет (Джон Гей) Достаточно лишь нескольких лучей света, чтобы помочь людям в совершенствовании их «стохастических» способностей (Джон Оуэн) В сфере программирования случайные числа играют не последнюю роль. Само понятие «случайное число» является частью теории вероятности. И представляет из себя какую-то последовательность, которая характеризуется тем, что каждое число последовательности не зависит от всех остальных чисел последовательности. Это значит, что случайное число непредсказуемо и предугадать следующее число в последовательности невозможно. Получить случайные числа можно следующими способами: 1)с помощью таблиц случайных чисел; 2)с помощью специальных устройств — генераторов случайных чисел; 3)путем замены случайных чисел последовательности так называемых псевдослучайных чисел. Такие числа находят множество полезных применений. Во 2 томе Дональда Кнута «Искусство программирования» приведены следующие примеры: 1) Моделирование. «При использовании компьютера для моделирования естественных явлений случайные числа нужны для того, чтобы сделать эти модели похожими на реальность» [1, c.18]. 2) Выборочный метод. «Часто бывает невозможно исследовать все варианты, но случайная выборка обеспечивает понимание того, что можно назвать «типичным» поведением» [1, c.18]. 3) Численный анализ. «Для решения сложных задач численного анализа была разработана остроумная техника, использующая случайные числа» [1, c.18]. 4) Компьютерное программирование. «Случайные величины являются хорошим источником данных для тестирования эффективности компьютерных алгоритмов» [1, c.18]. 5) Принятие решений. «Иногда важно принять полностью «беспристрастное» решение. Случайные числа также являются важной частью оптимальных стратегий в теории матричных игр» [1, c.19]. 6) Эстетика. «Небольшая добавка случайности оживляет музыку и компьютерную графику» [1, c.19]. 7) Развлечение. «Многие считают, что они замечательно проводят время, бросая игральные кости, тасуя колоду карт, вращая колесо рулетки и тд. Такие традиционные способы использования случайных чисел получили название метод Монте-Карло» [1, c.19]. 2.Случайные числа Существует вопрос «А что является случайным числом?». Случайно ли число 2? Предпочитают говорить о последовательности независимых случайных чисел с заданным распределением, то есть каждое число было получено случайно, не имея ничего общего с другими числами этой последовательности. Равномерным распределением на конечном множестве чисел называется такое распределение, при котором любое из возможных чисел имеет одинаковую вероятность появления. Если взять цифры от 0 до 9, то каждая из них будет появляться примерно один раз из 10 в такой последовательности. Много лет случайные числа получали, бросая игральные кости, тасуя и раскладывая карты, таская шары из урны и другими способами. Наряду с этими способами применялись и механические генераторы чисел. Такие как использование таблиц (1927 г.). С появлением компьютеров появились и новые способы получения случайных чисел. Использование таблиц не запрещалось, однако в этом не было пользы из-за ограниченной памяти компьютера и времени, требуемого при вводе. Такие неудобства были ни к чему. Но это не означает, что таблицы были забыты. Так в 90-е годы Дж. Марсалья вернул таблицы в использование, продемонстрировав диск со случайными числами, которые генерировались сочетанием записи шума диодной цепи и определённым образом скомпонованной музыкой в стиле «реп». 3.Метод середин квадратов фон Неймана Метод середин квадрата Джона фон Неймана, созданный в 1946 году, является одним из ранних генераторов случайных чисел. Суть метода: предыдущее случайное число возводится в квадрат, а затем из результата извлекаются средние цифры. Алгоритм: 1.[Инициализация.] х = х0. 2.[Основной цикл.] For j = 1 To m Do шаг 2; Stop. 3.[Генерация нового случайного числа.] Xj: 1x890 Пример: x0=5468 y = 29 899 024 x1=8990 y = 80 820 100 x2 =8201 y =67 256 401 Однако есть существенный недостаток такого метода. Стоит встретить последовательность нулей, как произойдет зацикливание и никакой последовательности случайных чисел не будет. Пример: х0=1000 y =1 000000 x1=0000 y = 0000 и так далее. Реализация на с++: #include using namespace std; int main() { int x, n; cout << "Enter the number" << endl; cin >> x; cout << "Enter the number of random numbers" << endl; cin >> n; int square, random = 0; for (int i = 0; i < n; i++) { square = x * x; random = (square % 1000000) / 100; x = random; cout << random << " "; } } Результат выполнения программы:  4.Линейный конгруэнтый метод. В 1949 году Д.Г. Лехмер предложил следующую схему получения последовательности случайных чисел. Выбирается четыре числа: m-модуль (m > 0); a, множитель; (0 ≤ a < m); c, приращение (0 ≤ c X₀, начальное значение (0 ≤ X₀ < m); Предположив Xₙ₊₁ = (aXₙ + c) mod m, n > 0 получим последовательность случайных чисел. Эта последовательность называется линейной конгруэнтной последовательностью. Но такая последовательность не может быть случайной при некоторых значениях m, a, c и X₀ Например, для m = 10 и X₀ = a = c = 7 получим последовательность 1 7, 6, 9, 0, 7, 6, 9, 0, ……. Повторяющиеся циклы называются периодами. Замечание: чем длиннее период последовательности, тем более случайной она будет казаться. Так же есть интересный случай при с = 0, такую последовательность называют мультипликационным конгруэнтным методом (см. подробнее с.30) 4.2 Выбор модуля. Нахождение хороших значений параметров первое, на что нужно обратить внимание. Выбирая модуль m, необходимо , чтобы m было довольно большим, так как период не может иметь больше m элементов.2 Еще одним фактором выбора m является скорость генерирования. Поэтому нужно подобрать такое значение m, чтобы (aXₙ + c)mod m вычислялось быстро. 4.3 Выбор множителя. Да, длинный период необходим для случайной последовательности, однако это только одно из требований к линейным конгруэнтным последовательностям. Например при а = с = 1, последовательность примет простой вид: Xₙ₊₁ = (Xₙ+1)mod m. Она имеет период длиной m, но несмотря на это, в ней нет ничего случайного². Теорема 1. [Д.Э. Кнут Искусство программирования 2 том (2003). С.36] Линейная конгруэнтная последовательность, определённая числами m, a, c, и X₀, имеет период длиной m тогда и только тогда, когда: Числа c и m взаимно простые; в = a – 1 кратно p для каждого простого p, являющегося делителем m; в кратно 4, если m кратно 4. Лемма 1. [см. там же. С.36.] Пусть p – простое число, а е – положительное целое число, такое, что pᵉ> 2, если x ≡ 1(по модулю pᶱ, x не ≡ 1 (по модулю pᶱ⁺¹), то xᵖ≡1(по модулю pᵉ⁺¹), xᵖ не ≡ 1(по модулю pᵉ⁺²). Лемма 2. [см. там же. С.36.] Пусть число m допускает разложение на простые множители в виде m ≡ pᵉ₁ ….. pᵉₜͭ. Длина периода λ линейной конгруэнтной последовательности, определенной параметрами (X₀, a, c, m1, m2), является наименьшим общим кратным длин λj периодов линейных конгруэнтных последовательностей (X₀ mod pᵉʲj, a mod pᵉʲj, c mod pᵉʲj , pᵉʲj), 1 ≤ j ≤ t. Лемма 3. [см. там же. С.36.] Предположим, что 1 < a < pᵉ, где p – простое Число. Если λ- наименьшее целое положительное число, для которого (a^λ -1)/(a-1) ≡ 0(по модулю pᵉ), то λ = pᵉ тогда и только тогда, когда  .Теорема 2. [см. там же. С.36.] Максимальным периодом, возможным, когда с = 0, является λ(m).Этот период достигается, если: X₀ и m – взаимно простые числа; а является первообразным элементом по модулю m; График линейного конгруэнтного метода:  Пример работы алгоритма при a = 2, c = 3, m = 5, X0 = 1. Из графика видно, что при данном методе последовательность повторяется, но если максимально увеличить период, то последовательность будет более случайной. Реализация на С++: #include #include using namespace std; int main() { unsigned int X = 0; //начальное значение (0<=X unsigned int A = 0; //множитель (0<=a unsigned int C = 0; //приращение (0<=c unsigned int M = 0; //модуль(натуральное число, относительно которовы вычисляется остатокот деления, m>=2 unsigned int iCount = 0; //необходимое колличество псевдослучайных чисел int nextNumber = 1; float x = 1; cout << "\t\tКонгруэнтный метод формирования псевдослучайных чисел\n"; cout << "Введите необходимые данные:\n"; cout << "Введите значение для M - модуля, где M > 2: "; cin >> M; cout << "Введите начальное значение для X, где (0<=X cin >> X; cout << "Введите множитель A, где (0<=A cin >> A; cout << "Введите приращение C, где (0<=C cin >> C; cout << "Введите какое кол-во псевдосулчайных чисел необходимо: "; cin >> iCount; nextNumber = (A * X + C) % M; for (int i = 0; i < iCount; i++) { nextNumber = (A * nextNumber + C) % M; x = (float)nextNumber / M; cout << fixed << setprecision(2) << x << " "; } return 0; } Результат выполнения программы:  5.Другие методы С попытками получить случайных чисел возникает ошибочное мнение, что достаточно взять хороший генератор случайных чисел и модифицировать его, чтобы получить «еще более случайную» последовательность. Это конечно же не так. Например, возьмем формулу Xₙ₊₁ (aXₙ+c) mod m. Она позволяет получить более или мене случайную последовательность. Но как бы не казалась новая формула Xₙ₊₁ = ((aXₙ) mod (m+1)+c) mod m более случайной прежней, это не так. Напротив, она менее случайна с большей долей вероятности. Давайте рассмотрим другое преобразование. На этот раз попытаемся получить подлинную случайную последовательность. Линейный конгруэнтный метод может быть обобщен в квадратичный конгруэнтный метод: Xₙ₊₁ = (dX²ₙ +aXₙ +c) mod m В этом методе ограничения получения необходимых и достаточных условий для a,c и d менее жесткие чем в линейном методе. Для m, которое является степенью 2, интересный квадратичный метод предложил Р.Р. Ковэю(подробнее смотреть Дональд Э. Кнут Искусство программирования том 2. М.,СПб.,2003.С. 46). 5.1 Аддитивный генератор случайных чисел Простейшая последовательность, в которой Xn+1 зависит от более чем от одного из предыдущих значений, -это последовательность чисел Фибоначчи Xn+1 = (Xn + Xn-1) mod m. Считается, что числа получаемые с помощью рекуррентного соотношения Фибоначчи недостаточно случайны, и таким образом это выражение является «плохим примером» источника случайных чисел. Намного лучший аддитивный генератор случайных чисел был изобретен Дж.Ж. Митчелом, Д.Ф. Муром в 1958 году. Xn =(Xn -24 +Xn-55) mod m, n ≥ 55; Числа 24 и 55 в данном определении выбраны не случайно (подробнее см. Дональд Э. Кнут Искусство программирования том 2. М.,СПб.,2003.С. 47) Алгоритм А(Аддитивный генератор случайных чисел) В ячейки памяти Y[1], Y[2],…,Y[55] записано множество значений X54, X53, …., X0 соответственно; j в начале равно 24, а k равно 55. При реализации этого алгоритма на выходе последовательно получаем числа X55, X56,…. A1.[Суммирование.] Если на выходе мы оказываемся в точке Xₙ, то Y[j] равно Xₙ-24 , а Y[k] равно Xn-55.) Запишем Y[k] <‒ (Y[k] +Y[j]) mod m2ᵉ, тогда на выходе получим Y[k]. A2.[Продвижение] Уменьшим j и k на 1. Если j = 0, то присвоим j <‒ 55; иначе, если k = 0, присвоить k <‒ 55. 5.2 Рандомизация промешиванием (М.Д. Мак-Ларен и Дж.Марсалья) Есть такое мнение, что линейные конгруэнтные, аддитивные и другие методы слишком просты для того, чтобы давать достаточно случайную последовательность. Существует достаточно эффективный метод способ объединения двух последовательностей в третью, которая была бы настолько случайной, что удовлетворяла бы всех. Алгоритм М(Рандомизация перемешиванием.) Если заданы методы генерирования двух последовательностей {Xₙ} И {Yₙ}, этот алгоритм будет последовательно генерировать элементы «значительно более случайной» последовательности. Воспользуемся вспомогательной таблицей V[0], V[1],…,V[k-1], где k – некоторое число, для удобства выбирается приблизительно равным 100. Вначале V-таблица заполняется первыми k значениями X-последовательности. М1.[Генерирование X,Y.] Положим X и Y равными следующим членам последовательностей {Xₙ} и {Yₙ} соответсвенно. М2.[Выбор j.] Присвоим j <‒ [kY/m], где m – модуль, используемый в последовательности {Yₙ}, т.е. j – случайная величина, определяемая Y, 0 ≤ j < k. М3.[Замена.] Выведем V[j], а затем присвоим V[j] <‒ X. Однако помимо этого метода существует еще лучший путь перемешивания элементов последовательности, открытый Картером Бейсом и С.Д. Дархамом. Алгоритм B(Рандомизация перемешиванием) Если задан метод генерирования последовательности {Xₙ}, этот алгоритм будет последовательно выводить элементы «значительно более случайной» последовательности, используя вспомогательную таблицу V[0], V[1],…,V[k-1]. Вначале V-таблица заполняется первыми k значениями X- последовательности, а вспомогательную переменную Y положим равной k+1–му значению. B1.[Выбор j.] Присвоим j <‒ [kY/m], где m – модуль, используемый в последовательности {Xₙ}; т.е. j- это случайная величина, определяемая Y, 0 ≤ j < k. B2.[Замена.] Выведем V[j], присвоим V[j] 0 <‒ X, выведем V[j] и установим V[j] следующим членом последовательности {Xₙ} Список используемой литературы: 1.Дональд Э. Кнут Искусство программирования том 2. М.,СПб.,2003 2. https://ps-group.github.io/cxx/cxx_random 3. https://moluch.ru/archive/142/40025/ 4. https://ci-plus-plus-snachala.ru/?p=15 5. https://habr.com/ru/post/151187/ 1 Дональд Э. Кнут Искусство программирования том 2. М.,СПб.,2003.С.29 2 Дональд Э. Кнут Искусство программирования том 2. М.,СПб.,2003.С. 31 |