Stohastic / Stohastic / Методичка_Стохастика_Федунов

Лабораторная работа 1. Программная генерация псевдослучайных чисел.

Как правило, случайные числа получают на ЭВМ программным способом, производящим последовательности "псевдослучайных" чисел (псевдослучайными числа называются потому, что элементы последовательности почти независимы друг от друга). Для этого используются рекуррентные формулы, когда каждое последующее число x_i+1 образуется из предыдущего x_i на основании применения некоторого алгоритма. Подобная последовательность чисел, не будучи истинно случайной по своей природе, обладает свойствами, аналогичными свойствам случайных величин. Большинство алгоритмов получения псевдослучайных чисел основано на том, что при перемножении двух многоразрядных чисел x и y средние разряды произведения xy являются сложной функцией сомножителей и обладают "случайными"свойствами.

В составе стандартной библиотеки в языке C имеется функция генерации псевдослучайных чисел.

#include <stdlib.h>

void srand (unsigned seed);

int rand (void);

i=rand();

Первая функция инициализирует генератор случайных чисел. Случайное число seed воспроизводит одну и ту же последовательность случайных чисел seed. Вторая функция генерирует целочисленное случайное значение в диапазоне от 0 до max значения для переменной типа int. От 0 до RAND_MAX = 32767. Таким образом, rand() возвращает целое число в интервале [0, RAND_MAX]

Если используются вещественные случайные числа, необходимо выполнить масштабное преобразование:

float x=rand()/(RAND_MAX+1); .

К настоящему времени разработано множество алгоритмов получения псевдослучайных чисел. Рассмотрим некоторые из них.

Линейный конгруэнтный метод.

Алгоритм заключается в использовании формулы:

Где a, c, m – целочисленные константы. Вместо mod можно написать %. Последовательность генерирования таким генератором повторяется с периодом не превышающим m.

Длина периода равна m, тогда и только тогда, когда выполняется условие:

1) mod(c, m)=1, c и m – взаимно просты.

2) b= a – 1 кратно для всех простых делителей m.

3) b кратно 4 если m кратно 4, длина последовательности равна m.

Для реализации удобно выбрать , где s – число бит в машинном слове.

a , c – различны в различных компиляторах.

VS: a=214013; c=2531011; m=2³²-1;

Метод Фибоначчи с запаздыванием.

вещественные числа из диапазона от 0 до 1.

; а, b – целые положительные числа

Период:

l - число битов в мантиссе вещественного числа; а, b – магические числа и не могут выбираться произвольно.

(а, b) = (55, 24); (17, 5); (97, 33)

Содержание