Реализация класса RandomNumber

Для создания псевдослучайных чисел используется линейный конгруэнтный алгоритм. Этот алгоритм использует большой нечетный постоянный множитель и постоянное слагаемое вместе с seed-значением для итеративного создания случайных чисел и обновления seed-значения:

const unsigned long maxshort = 65536;

const unsigned long multiplier = 1194211693;

const unsigned long adder = 12345;

Последовательность случайных чисел начинается с начального значения для длинного целого randSeed. Задание этого значения называется настройкой (seeding) генератора случайных чисел и выполняется конструктором.

Конструктор позволяет клиенту передавать seed-значение или использовать для его получения машинно-зависимую функцию time. Мы подразумеваем, что функция time объявляется в файле <time.h>. При вызове конструктора с параметром 0 функция time возвращает беззнаковое длинное (32-битовое) число, указывая количество секунд, прошедших после базового времени. Используемое базовое время включает полночь 1-го января 1970 года и полночь 1-го января 1904 года. В любом случае, это большое беззнаковое длинное значение:

//генерация seed-значения

RandomNumber::RandomNumber (unsigned long s)

{

if (s == 0)

randSeed = time(0); //использование системной функции time

else

randSeed = s; //пользовательское seed-значение

}

В каждой итерации используем константы для создания нового беззнакового длинного seed-значения:

randSeed=multiplier*randSeed+adder;

В результате умножения и сложения верхние 16 битов 32-битового значения randSeed являются случайными ("хорошо перемешанными") числами. Наш алгоритм создает случайное число в диапазоне от 0 до 65535, сдвигая 16 битов вправо. Мы отображаем это число на диапазон 0…n-1, беря остаток от деления на n. Результатом является значение Random(n).

//возвращать случайное целое 0<=value<=n-1<65536

unsigned short RandomNumber::Random (unsigned long n)

{

randSeed=multiplier*randSeed+adder;

return (unsigned short) ((randSeed)>>16)%n) ;

}

Для числа с плавающей точкой сначала вызываем метод Random(maxshort), который возвращает следующее случайное целое число в диапазоне от 0 до maxshort-1. После деления на double(maxshort) получаем действительное число в интервале 0<=fRandom() < 1.0.

double RandomNumber::fRandom (void)

{

return Random(maxshort)/double(maxshort);

}

Объявление и реализация RandomNumber содержится в файле "random.h".

Приложение: Частота выпадения лицевой стороны при бросании монет. Класс RandomNumber используется для имитации повторяемого бросания 10 монет. Во время бросания некоторые монеты падают лицевой стороной (head)1 вверх, а другие - обратной. Бросание десяти монет имеет результатом число падений лицевой стороной в диапазоне 0-10. Интуитивно вы подразумеваете, что 0 лицевых сторон или 10 лицевых сторон в бросании 10 монет - это относительно невероятно. Более вероятно, что количества выпадений разных сторон будут примерно равными. Число лицевых сторон будет находиться где-нибудь в середине диапазона 0-10, скажем, 4-6. Мы проверим это интуитивное предположение большим числом (50 0000) повторений бросания. Массив head ведет подсчет количества раз, когда соответствующий подсчет лицевых сторон составляет 0,1,…,10.

Значение head[i] (0<=i<=10) - это количество раз в 50 000 повторениях, когда ровно i лицевых сторон выпадает во время бросания 10 монет.

Программа 3. График частоты

Бросание 10 монет составляет событие. Метод Random с параметром 2 моделирует одно бросание монеты, интерпретируя возвращаемое значение 0 как обратные стороны, а возвращаемое значение 1 как лицевые стороны. Функция TossCoins объявляет статический объект coinToss типа Random-Number, использущий автоматическое задание seed-значения. Так как этот объект является статическим, каждый вызов TossCoins использует следующее значение в одной последовательности случайных чисел. Бросание указанного количества монет выполняется суммированием 10 значений, выдаваемых CoinToss.Random(2). Возвращаемый результат приращивает соответствующий счетчик в массиве лицевых сторон.

Выходом программы является частотный график количества лицевых сторон. График с числом лицевых сторон на оси х и относительным числом событий (occurences) — на оси y обеспечивает наглядное представление того, что известно как биномиальное распределение. Для каждого индекса i относительное число событий, при которых лицевые стороны выпали ровно i раз, составляет

heads[i]/float(NTOSSES)

Это значение используется для помещения символа * в относительном местоположении между 1-й и 72-й позицией строки. Результирующий график является аппроксимацией биномиального распределения.

#include <iostream.h>

#include <iomanip.h>

#include "random.h" // включает генератор случайных чисел

// "бросить" numberCoins монет и возвратить общее число

// выпадений лицевой стороны

int TossCoins(int numberCoins)

{

static RandomNumber coinToss;

int if tosses = 0;

for (i=0;i<numberCoins;i++ )

// Random (2)=1 индицирует лицевую сторону

tosses += coinToss.Random(2) ;

return tosses;

}

void main (void)

{

// число монет в бросании и число бросаний

const int NCOINS = 10;

const long NTOSSES = 50000;

// heads [0]=сколько раз не выпало ни одной лицевой стороны

// heads [1]=сколько раз выпала одна лицевая сторона и т .д.

long i, heads [NCOINS+1] ;

int j, position;

// инициализация массива heads

for (j=0;j<=NCOINS+1; j++)

heads [j] = 0;

//"бросать" монеты NTOSSES раз и записывать результаты

//в массив heads

for (i=0;i<NTOSSES; i++)

heads [TossCoins(NCOINS)] ++;

// печатать график частот

for (i=0;i < NCOINS+1;I++)

{

position=int(float(heads[i])/float(NTOSSES)*72);

cout << setw(6) << i << " ";

for (j=0;j<position-1; j++)

cout << " " ;

// ' *' относительное число бросаний с i лицевыми сторонами

cout << ' *' << endl;

}

}