Емельянов Эдуард Владимирович (eddy_em) wrote,
Емельянов Эдуард Владимирович
eddy_em

Categories:

Инициализация генератора псевдослучайных чисел

С этой проблемой я столкнулся довольно давно, когда для моделирования эксперимента по восстановлению зашумленных данных мне требовалось генерировать длинные псевдослучайные последовательности, не повторяющиеся при следующем запуске программы.

Немного "покурив манов" и попробовав разные варианты я остановился на одном — инициализация генератора псевдослучайных чисел с использованием системного таймера.

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

#define RAND_INI() do{}while(0)
#include <stdio.h>		// printf
#include <stdlib.h>		// random number functions
#include <sys/time.h>		// gettimeofday
#include <limits.h>		// LONG_MAX
#include <math.h>		// floor
#include <unistd.h>		// read
#include <sys/types.h>		// open
#include <sys/stat.h>		// open
#include <fcntl.h>		// open

double dtime(){
	double t;
	struct timeval tv;
	gettimeofday(&tv, NULL);
	t = tv.tv_sec + ((double)tv.tv_usec)/1e6;
	return t;
}

void urandom_ini(){
	double tt = dtime() * 1e6;
	double mx = (double)LONG_MAX;
	srand48((long)(tt - mx * floor(tt/mx)));
}

void dev_random_ini(){
	long r_ini;
	int fd = open("/dev/random", O_RDONLY);
	if(-1 == fd){fprintf(stderr,"Error open /dev/random!\n"); urandom_ini(); return;}
	if(sizeof(long) != read(fd, &r_ini, sizeof(long))){
		fprintf(stderr,"Error read /dev/random!\n"); urandom_ini();
		close(fd); return;
	}
	close(fd);
	srand48(r_ini);
}

int main(int argc, char **argv){
	int i;
	printf("\trandom\t\tdrand48\n");
	RAND_INI();
	for(i = 0; i < 10; i++){
		printf("\t%ld\t%g\n", random(), drand48());
	}
	printf("\n");
	return 0;
}
(для экономии места я сразу добавил функции для тестирования способов инициализации генератора).

Итак, макрос RAND_INI() пока что ничего не делает. Компилируем программку и запускаем ее:

gcc random_numbers.c -lm -o random_numbers && ./random_numbers && ./random_numbers
	random		drand48
	1804289383	3.90799e-14
	846930886	0.000985395
	1681692777	0.041631
	1714636915	0.176643
	1957747793	0.364602
	424238335	0.0913306
	719885386	0.0922976
	1649760492	0.487217
	596516649	0.52675
	1189641421	0.454433

	random		drand48
	1804289383	3.90799e-14
	846930886	0.000985395
	1681692777	0.041631
	1714636915	0.176643
	1957747793	0.364602
	424238335	0.0913306
	719885386	0.0922976
	1649760492	0.487217
	596516649	0.52675
	1189641421	0.454433
Оба раза и функция random, и функция drand48 дают нам одинаковые наборы данных, чего и следовало ожидать.

Теперь инициализируем генератор функцией urandom_ini():

#define RAND_INI() do{urandom_ini();}while(0)
И посмотрим, что получилось:
gcc random_numbers.c -lm -o random_numbers && ./random_numbers && ./random_numbers
	random		drand48
	1804289383	0.242206
	846930886	0.271541
	1681692777	0.542762
	1714636915	0.110237
	1957747793	0.887529
	424238335	0.666325
	719885386	0.111704
	1649760492	0.580617
	596516649	0.306465
	1189641421	0.816699

	random		drand48
	1804289383	0.0632047
	846930886	0.428704
	1681692777	0.53463
	1714636915	0.356859
	1957747793	0.497169
	424238335	0.570711
	719885386	0.333679
	1649760492	0.675633
	596516649	0.651444
	1189641421	0.191509
Функция urandom_ini() инициализирует начальное значение генератора псевдослучайных чисел числом, которое получается из количества миллионных долей секунд, прошедших с 1 января 1970 года, посредством "обрезания его" на целое количество LONG_MAX (чтобы это количество секунд лежало в диапазоне 0..LONG_MAX).

Так как функции random и drand48 используют разные переменные для хранения последнего псевдослучайного числа, поведение random от такой инициализации не меняется, а вот drand48 начинает выдавать уже "псевдоразные" псевдослучайные последовательности. Чтобы random работал так же, достаточно немного изменить функцию-инициализатор: вместо LONG_MAX ограничить диапазон UINT_MAX, а вместо srand48 вызвать srand.

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

Для того, чтобы "почти гарантированно" получать каждый раз разные псевдослучайные последовательности, необходимо добавить еще какой-либо элемент случайности. Им может быть комбинация чисел, получаемых из текущих параметров системы: нагрузки процессора, объема свободной памяти, температуры датчиков и т.п. Самостоятельно вычислять эти параметры смысла нет: придется лепить довольно сложный инициализатор. Да и не нужно это, ведь в системе уже есть нужный нам "ядерный" генератор псевдослучайных чисел, практически уже случайных. Это - /dev/random и /dev/urandom.

Для получения более-менее случайного числа "ядерные" генераторы случайных чисел используют так называемую "энтропию" системы, которая получается из огромного количества псевдослучайных величин, определяющихся текущим состоянием системы (в том числе и движения мыши, нажатие клавиш на клавиатуре и т.п.). Например, зависимость выдаваемых генератором /dev/random чисел от движений мыши можно увидеть, запустив в терминале cat /dev/random и двигая мышью: чем активнее вы двигаете мышкой, тем чаще генерируются числа. Однако, генерируются они довольно медленно по причине того, что /dev/random — сложный генератор, который используется в криптографических нуждах. И отдает он псевдослучайное число лишь тогда, когда накопит достаточно "энтропии" (т.е. до накопления происходит блокировка).

В отличие от /dev/random, /dev/urandom не блокирует считывание, а лишь генерирует набор псевдослучайных чисел, периодически "подправляя" их при накоплении нужного количества "энтропии".

Обычно в программах, не требующих повышенной безопасности, для инициализации псевдослучайных чисел используют более быстрый /dev/urandom. Его даже можно использовать для генерирования этих чисел (правда, т.к. нам каждый раз придется считывать число из псевдоустройства, лишние сисвызовы будут притормаживать программу). /dev/random по понятным причинам для генерирования псевдослучайных чисел использовать бессмысленно, однако, им удобно инициализировать псевдослучайные последовательности.

Для получения нужного инициализатора, необходимо лишь считать требуемое количество байт из /dev/random или /dev/urandom. Естественно, чем меньше байт будет занимать инициализатор, тем быстрее мы получим его (особенно это касается /dev/random, выдающего порядка восьми байт "за присест"). Если до выполнения нашей программы кто-то еще считывал данные из буфера /dev/random, то для считывания, скажем, 80 байт, пользователю придется ждать довольно долго (если, конечно, он не будет активно крутить мышкой по экрану). Кстати, быть может, привычка некоторых водить мышкой в ожидании чего-то и пошла от желания ускорить работу /dev/random? :)

Итак, завершающий тест нашей программы. Переопределяем инициализатор:

#define RAND_INI() do{dev_random_ini();}while(0)
И запускаем:
gcc random_numbers.c -lm -o random_numbers && ./random_numbers && ./random_numbers 
	random		drand48
	1804289383	0.176947
	846930886	0.835512
	1681692777	0.489867
	1714636915	0.585424
	1957747793	0.964114
	424238335	0.118075
	719885386	0.118784
	1649760492	0.0958298
	596516649	0.13887
	1189641421	0.421761

	random		drand48
	1804289383	0.625318
	846930886	0.344886
	1681692777	0.472568
	1714636915	0.958766
	1957747793	0.955779
	424238335	0.0952954
	719885386	0.0511651
	1649760492	0.945531
	596516649	0.41042
	1189641421	0.623248

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

Tags: c, велосипедостроение
Subscribe

  • Дурацкий перекресток

    Был на днях в Пятигорске. Ну и движение там! Просто жесть!!! Вечные пробки, куча "кругов" и грохотящие трамваи… А когда выезжал оттуда, на углу пр.…

  • А что, в С так нельзя?

    Пытаюсь передать в функцию цвет как массив. Функция такая: void Pattern_draw3(Img3 *img, Pattern *p, int xul, int yul, uint8_t colr[3]); И…

  • DHT22/DHT11 на STM32F103

    Добил шайтана! Сначала ожидал, что нужно будет полноценным захватом ШИМ пользоваться, но т.к. в протоколе неинформативная часть имеет постоянную…

promo eddy_em august 17, 2019 12:33 3
Buy for 10 tokens
Юра намедни напечатал корпус для хронометра. Для первого блина получилось неплохо: И еще немного фотографий:
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

  • 3 comments