Случайные числа в стандартном си

Псевдослучайные числа

Генерация псевдослучайных чисел – это сложная математическая задача. Данная статья не ставит перед собой задачи охватить эту тему. Далее понятие «случайное число» будет означать псевдослучайное, если это не оговорено особо.

С примерами использования случайных чисел вы сталкиваетесь повсюду. Псевдослучайные числа используются в дизайне и графике, для генерации уровней в компьютерных играх и симулирования ИИ. Наборы случайных чисел используются в математических алгоритмах (см. Методы Монте-Карло).

Очевидно, что задача генерации случайных чисел на классическом процессоре не может быть решена, так как работа компьютера детерминирована по определению. Тем не менее, можно сгенерировать очень длинные наборы чисел такие, что их распределение будет иметь те же свойства, что и наборы истинно случайных чисел.

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

Посмотрим стандартный генератор.

#include <stdio.h>
#include <time.h>
#include <conio.h>

int main() {
	int i, r;

	srand(42);
	for (i = 0; i < 10; i++) {
		r = rand();
		printf("%d\n", r);
	}

	_getch();
	return 0;
}

Для начала необходимо инициализировать генератор случайных чисел (ГСЧ, или RNG - random number generator), задать зерно – seed, на основе которого в дальнейшем будет происходить генерация. Важно, что для одного и того же начального значения генератор будет возвращать одни и те же числа.

srand(42);

Присваиваем переменной r случайное значение

r = rand();

Значение будет лежать в диапазоне от 0 до RAND_MAX.

Для того, чтобы при следующем запуске получить новый набор чисел, нужно инициализировать генератор каждый раз разными значениями. Например, можно использовать системной время:

srand(time(NULL));

Или

srand(_getpid());

Функция getpid библиотеки process.h возвращает идентификатор процесса (можно также использовать getpid, не POSIX версию функции).

Центральная Предельная Теорема

Очень важно сразу напомнить или познакомить с центральной предельной теоремой. Неформальное определение – распределение суммы слабо зависимых случайных величин стремится к нормальному. Пальцеобразное объяснение: если сложить несколько случайных величин, независимо от их распределения, то распределение суммы будет нормальным. Часто можно увидеть такой код

#include <stdio.h>
#include <time.h>
#include <conio.h>

int main() {
	int i, r, r1, r2, r3;

	srand(time(NULL));
	
	r1 = rand();
	r2 = rand();
	r3 = rand();

	r = (r1 + r2 + r3) / 3;

	printf("%d", r);

	_getch();
	return 0;
}

Таким образом автор пытается сделать случайное число «более» случайным, но получает менее случайное число.

Генерация случайных чисел на заданном отрезке

Во-первых, получим случайное число от нуля до единицы:

const float RAND_MAX_F = RAND_MAX;

float get_rand() {
	return rand() / RAND_MAX_F;
}

Для получения числа в отрезке от нуля до N умножим N на случайное число от нуля до единицы. Для получения случайного числа от M До N, сдвинем полученное число на M.

float get_rand_range(const float min, const float max) {
	return get_rand() * (max - min) + min;
}

Для получения целого числа, будем брать остаток от деления на длину интервала. Но остаток от деления будет возвращать число на единицу меньше, чем наш интервал, поэтому увеличим его на единицу:

int get_rand_range_int(const int min, const int max) {
	return rand() % (max - min + 1) + min;
}

Пример использования случайных чисел для вычисления интеграла. Пусть у нас есть некоторая гладкая функция от одной переменной. Ограничим её квадратом от a до b, и от 0 до некоторой точки, которая заведомо больше нашей функции.

Будем случайным образом кидать точки на нашем квадрате. Если они лежат выше функции (на рисунке изображены зелёными крестиками), то отнесём их к первой группе A, если ниже функции (на рисунке красные), то отнесём их ко второй группе B. Положение точек случайное и распределено равномерно (т.к. стандартный генератор даёт равномерное распределение. Этот простой пример, кстати, уже показывает, насколько важно знать свойства ГСЧ). Тогда отношение красных точек к общему числу точек будет равно отношению площади под графиком к общей площади. А общая площадь – это квадрат (b-a) на q.

Применим наши выкладки – найдём интеграл функции x^2 на отрезке от 0 до двух двумя способами.

#include <stdio.h>
#include <time.h>
#include <conio.h>
#include <stdlib.h>
#include <math.h>

const float RAND_MAX_F = RAND_MAX;

float get_rand() {
	return rand() / RAND_MAX_F;
}

float get_rand_range(const float min, const float max) {
	return get_rand() * (max - min) + min;
}

#define ROUNDS 1000

float fun(float x) {
	return x * x;
}

float square_square(float a, float b, float q) {
	float h = (b - a) / (float)ROUNDS;
	float sum = 0;
	for (; a < b; a += h) {
		sum += fun(a) * h;
	}
	return sum;
}

float rand_square(float a, float b, float q) {
	float res;
	float x, y;
	int i;
	int lower = 0;
	float ratio;
	float square;

	srand(time(NULL));

	for (i = 0; i < ROUNDS; i++) {
		x = get_rand_range(a, b);
		y = get_rand_range(0, q);
		res = fun(x);
		if (res > y) {
			lower++;
		}
	}
	ratio = (float)lower / (float)ROUNDS;
	square = (b - a) * q * ratio;
	return square;
}

int main() {
	float abs_ans = 2.66667f;
	float sr = rand_square(0, 2, 4);
	float ss = square_square(0, 2, 4);
	printf("Rounds = %d\n", ROUNDS);
	printf("Sa = %.5f\n", abs_ans);
	printf("Sr = %.5f\n", sr);
	printf("Ss = %.5f\n", ss);
	printf("dr = %.5f\n", fabs(sr - abs_ans));
	printf("ds = %.5f\n", fabs(ss - abs_ans));
	
	_getch();
	return 0;
}

Поиграйте со значением ROUNDS, измените его и посмотрите, как меняется точность вычислений.

Генерация истинно случайных чисел

Для генерации настоящих случайных чисел используют генераторы, основанные на каких-то случайных физических процессах. Например, на тепловых шумах, на подсчёте числа делений радиоактивного вещества, на атмосферных шумах и т.п. Недостаток таких генераторов – низкая скорость работы (количество сгенерированных чисел в секунду) ; конечно, такие генераторы обычно являются отдельным устройством.

Если есть необходимость в большом наборе истинно случайных чисел, можно воспользоваться таблицами случайных чисел, например на сайте RANDOM.ORG

Всё ещё не понятно? – пиши вопросы на ящик