Тест для генератора случайных чисел Печать
Автор: Андрей   
22.01.2010 16:09

Описание программы
Код программы
Код с подробными комментариями
Советы по улучшению и расширению программы

Описание программы
Насколько хорош ваш генератор случайных чисел? Для повседневных нужд хватает, но... Прямо скажем - стандартный генератор, включенный в наш родной C++ Builder для моделирования квантовых систем будет мало пригоден. Данная программа демонстрирует, насколько тот или иной генератор случайных чисел отличается от идеального (на примере функции random из библиотеки stdlib).
Рассмотрим подробнее, что эта программа делает. Первым делом мы моделируем случайное бросание камешка в одну из клеток квадратного поля, в данном случае - размером 15*15. По идее, если работа поручена очень хорошему генератору случайных чисел (ГСЧ), то при большом числе бросаний количество попаданий в каждую из клеток должно быть приблизительно одинаковым и с ростом числа бросков различие должно становиться все меньше. Так это или нет в случае вполне конкретной функции, реализующей ГСЧ, нам покажет наша программа на первом этапе своего отчета о проделанной работе (рис. 1). Впрочем, если среднестатистический пользователь применяет для обработки этих значений только свою голову, то он сможет получить из них лишь общее представление - мол, даже при миллионе бросаний числа явно не одинаковые. Поэтому после того, как этот самый пользователь достаточно проникнется важностью циферок и нажмет любую клавишу, программа выдаст ему более наглядное представление о "шероховатостях" псевдослучайного распределения (рис. 2). Этот скромный график показывает распределение числа попаданий в какую-либо клетку. В идеале во всех клетках должно быть примерно одинаковое число попаданий и этот график должен иметь ярко выраженный максимум (практически нет клеток, в которые бы камешки попадали чаще или реже, чем в остальные).
Ну и что же мы видим на самом деле? Число попаданий в клетку, конечно, тяготеет к некоему среднему числу, но разброс все же очень сильный. График охватывает полосу шириной в 500 "попаданий" при среднем 4444 при данных параметрах программы. Получаем среднее число попаданий (4444 +/- 250), т.е. разброс порядка 5%. Таково распределение неравномерностей в генерации псевдослучайных чисел у функции random в моей версии C++ Builder'а. Для генерации небольшого числа псевдослучайных значений в обычных задачах - вполне достаточно, однако если перед вами будет стоять задача по моделированию сложных стохастических процессов, то вам придется искать специальный хороший ГСЧ.

Программа "Тест для генератора случайных чисел". Распределение числа бросаний по клеткам
Рис. 1
Программа "Тест для генератора случайных чисел". График распределение числа бросаний
Рис. 2

Код программы

#include <iostream>
#include <stdlib.h>
#include <conio.h>

int main()
{
const int NX = 15;
const int NY = 15;
int Nums[NX][NY];

for (int i = 0; i < NX; i++)
 for (int j = 0; j < NY; j++)
  Nums[i][j] = 0;
randomize();
int a, b;
for (int i = 0; i < 1000000; i++)
 {
 a = random(NX);
 b = random(NY);
 Nums[a][b]++;
 }
for (int i = 0; i < NX; i++)
 {
 for (int j = 0; j < NY; j++)
  {
  std::cout.width(5);
  std::cout << Nums[i][j];
  }
 std::cout << '\n';
 }
getch();

clrscr();
int f[25];
for (int i = 0; i < 25; i++)
 f[i] = 0;
for (int i = 0; i < NX; i++)
 for (int j = 0; j < NY; j++)
  {
  int c = Nums[i][j] - 4194;
  if (c >= 0 && c < 500)
   f[c / 20]++;
  }
for (int i = 0; i < 25; i++)
 {
 for (int j = 0; j < f[i]; j++)
  std::cout << '-';
 std::cout << '\n';
 }
getch();
}

Код программы с комментариями

#include <iostream> //Библиотека стандартного потокового ввода/вывода
#include <stdlib.h> //Библиотека, содержащая функции random и randomize
#include <conio.h> //Библиотека, содержащая функции getch и clrscr

int main()
{
const int NX = 15; //Размеры двумерного массива
const int NY = 15; //(поле размером NX * NY клеток)
int Nums[NX][NY]; //Количество попаданий в каждую из клеток поля

for (int i = 0; i < NX; i++) //Вначале во всех клетках по ноль попаданий
 for (int j = 0; j < NY; j++)
  Nums[i][j] = 0;
randomize(); //Делаем ряд будущих случайных значений более случайным за счет привязки к текущему системному времени
int a, b; //Случайно определяемые координаты клетки, в которую производится бросание
for (int i = 0; i < 1000000; i++) //Совершаем миллион случайных бросаний
 {
 a = random(NX); //Случайным образом определяем,
 b = random(NY); //в какую клетку попали
 Nums[a][b]++; //Увеличиваем счетчик попаданий в эту клетку
 }
for (int i = 0; i < NX; i++) //Выводим результаты бросаний
 { //В идеальном случае при 1000000 бросаний в каждой из 15*15 клеток
  //среднее число попаданий в каждую будет 4444
 for (int j = 0; j < NY; j++)
  {
  std::cout.width(5); //Ширина поля вывода - 5 символов (с расчетом на 4-значное число и пробел)
  std::cout << Nums[i][j]; //Выводим число попаданий в данную клетку
  }
 std::cout << '\n'; //Следующую строку двумерного массива выводим на новой строке
 }
getch(); //Прежде чем продолжить, ждем нажатия любой клавиши

clrscr(); //Очищаем экран
int f[25]; //Распределение числа попаданий в клетки (охватывает в сумме полосу шириной в 500)
 //(каждый элемент соответствует интервалу шириной в 20 "единиц количества попаданий")
for (int i = 0; i < 25; i++)
 f[i] = 0; //Вначале обнуляем массив
for (int i = 0; i < NX; i++)
 for (int j = 0; j < NY; j++)
  {
  int c = Nums[i][j] - 4194; //Положение числа попаданий на полосе от 4444 - 250 до 4444 + 250
  if (c >= 0 && c < 500) //Если укладывается в пределы этой полосы, ...
   f[c / 20]++; //Увеличиваем счетчик соответствующего интервала значений
  }
for (int i = 0; i < 25; i++) //Выводим график распределения
 { //Число знаков "-" показывает сколько раз число попаданий было из данного интервала
 for (int j = 0; j < f[i]; j++)
  std::cout << '-';
 std::cout << '\n'; //Выводим для следующего интервала
 }
getch(); //Перед окончанием работы ждем нажатия любой клавиши
}

Советы по улучшению и расширению программы
Данная программа тестировала генератор случайных чисел, реализуемый функцией random из библиотеки stdlib. Точно таким же образом вы можете протестировать любую другую функцию, генерирующую псевдослучайные числа - просто вместо random везде используйте эту функцию.
Используя графику вы также можете визуализировать распределение числа попаданий по клеткам, если вместо вывода чисел Nums[i][j] вы построите график по точкам с координатами (i, j, Nums[i][j]) соединив точку соответствующую Nums[i][j] с точками Nums[i - 1][j], Nums[i + 1][j], Nums[i][j - 1] и Nums[i][j + 1]. Впрочем, для удобного для восприятия вывода этого графика придется использовать не вполне тривиальные геометрические расчеты, и желательно также реализовать возможность поворота графика, поэтому вместь двумерного массива можно взять одномерный и строить по точкам обычный двумерный график.

Обновлено 25.01.2010 22:04