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

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

Генерирование равномерно распределенной последовательности чисел.

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

void randu(unsigned seed, unsigned &uResult, double &dbResult)
{
	uResult = seed * 65539;
	if(uResult < 0)
	{
		uResult *= 214748367+1;
	}
	dbResult = uResult;
	dbResult *= 0.4656613e-09;
}

В dbResult возвращает число с плавающей точкой, равномерно распределенное на интервале [0..1]. В uResult возвращает целочисленное псевдослучайное значение, для передачи в параметре seed при следующем вызове. При первом вызове в seed передается случайное нечетное целое число, "сбрасывающее" генератор. Длина цикла генератора randu (до первого повторения uResult) составляет 2^29.

Генерирование нормально распределенной последовательности.

Для построения полноценного генератора псевдослучайных чисел нам необходимо преобразовать полученную выше последовательность равномерно распределенных чисел в последовательность нормально распределенных чисел. Для этого воспользуемся центральной предельной теоремой теории вероятности. Которая в частном случае гласит, что сумма N нормально распределенных чисел имеет распределение близкое к нормальному. На практике, как правило, используют N >= 6.

Итак, для генерации последовательности нормально распределенных чисел с мат. ожиданием am и среднеквадратичным отклонением s можно использовать следующую функцию:

//s - среднеквадратичное отклонение
//am - мат. ожидание
double gauss(unsigned &seed, double s, double am)
{
	static const unsigned STEPS = 12;
	static const double AM_Z = 6.0;
	double z = 0.0;
	double dbResult = 0.0;
	for(unsigned i = 0; i < STEPS; ++i)
	{
		randu(seed, seed, dbResult);
		z += dbResult;
	}
	return (z-AM_Z)*s + am;
}

За подробностями реализации функции gauss советую обратиться к специальной литературе, отмечу лишь, что Z - это сумма 12 равномерно распределенных в интервале [0..1] чисел, а AM_Z - это мат. ожидание Z (очевидно, что 6 т.к. 0.5 *12 = 6).

Генератор псевдослучайных нормально распределенных чисел можно использовать, например, так (с мат. ожиданием равным 0 и среднеквадратичным отклонением равным 1):

void test_gauss()
{
	unsigned seed = 73942;
	for(unsigned i = 0; i < 10; ++i)
	{
		std::cout << gauss(seed, 1.0, 0.0) << " ";
	}
	std::cout << std::endl;
}