![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
eddy_em
Немного "покурив манов" и попробовав разные варианты я остановился на одном — инициализация генератора псевдослучайных чисел с использованием системного таймера.
Итак, напишем программку, позволяющую нам тестировать разные способы инициализации генератора псевдослучайных чисел:
#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. В случае работы с криптографией, так делать, конечно, нельзя. Но для обычных пользовательских экспериментов и/или математических моделей — вполне сгодится.
