ФГОБУ ВПО "СибГУТИ" Кафедра вычислительных систем Случайные числа и генерация тестовых данных Преподаватель: Доцент Кафедры ВС, к.т.н. Поляков Артем Юрьевич © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» ФГОБУ ВПО "СибГУТИ" Кафедра вычислительных систем ОСНОВЫ ПРОГРАММИРОВАНИЯ

План лекции © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 2 Случайные числа и их применение в вычислительной технике. Подходы к генерации случайных чисел. Псевдослучайные числа и алгоритмы их формирования. Статистическая проверка случайной природы чисел. Тестирование программного обеспечения Генерация входных данных

Применение случайных чисел © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 3 Компьютерное моделирование Азартные игры и лотереи. Криптография Компьютерные игры

Генерация случайных чисел 4 1. Ранние способы генерации случайных чисел. Их большим недостатком является крайне низкая скорость генерации. 2. Более эффективными являются физические генераторы случайных чисел, которые используют природные шумы. Random.org © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» HotBits

Генерация случайных чисел (2) 5 3. Генерация псевдослучайных чисел (ГСПЧ). Генератор псевдослучайных чисел, англ. Pseudo-random number generator (PRNG), это алгоритм, позволяющий генерировать длинные последовательности чисел, свойства которых близки к свойствам случайных чисел. Однако такие последовательности имеют период (повторяются с каким-то расстоянием). © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» seed значение for i 0 to n do rnd[i] = (seed / 1000) % ; seed = rnd[i] 2 ; Middle-square method 4. Генерация согласно заданному распределению вероятностей. Такие методы в основном используют числа с равномерным распределением и известную функцию плотности некоторого распределения (например нормального). В зависимости от источника равномерного распределения результат будет либо псевдослучайным либо случайным.

Линейный конгруэнтный генератор 6 Генератор псевдослучайных чисел, англ. Pseudo-random number generator (PRNG), это алгоритм, позволяющий генерировать длинные последовательности чисел, свойства которых близки к свойствам случайных чисел. Однако такие последовательности имеют период (повторяются с каким-то расстоянием). Конкретная последовательность чисел обычно определяется "зерном" из которого "прорастает" вся остальная последовательность. Алгоритм PRNG для одинакового значения зерна будет всегда порождать одинаковую последовательность. Наиболее простым вариантом PRNG является линейный конгруэнтный генератор (Linear Congruential Generator – LCG), который описывается следующим рекуррентным соотношением: x 0 = seed x n+1 = (ax n + b) mod m Период такого генератора (длина неповторяющейся последовательности) не превышает m. © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ»

Линейный конгруэнтный генератор (2) 7 Наиболее простым вариантом PRNG является линейный конгруэнтный генератор (linear congruential generator – LCG), который описывается следующим рекуррентным соотношением: x 0 = seed x n+1 = (ax n + b) mod m © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Sourcema c Биты x n, формирующие случайноге число Borland C/C rand(): lrand(): glibc (GCC) m = Borland Delphi, Virtual Pascal m, m > 0 – модуль (modulus); a, m > a > 0 – мультипликатор (multiplier); c, m > c 0 – инкремент (increment) x 0 – случайное зерно.

Период ГСПЧ (PRNG) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 8 Никакой детерминированный алгоритм не может генерировать полностью случайные числа, он может только аппроксимировать некоторые их свойства. Джон фон Нейман: « … всякий, кто питает слабость к арифметическим методам получения случайных чисел, грешен вне всяких сомнений … ». Любой ГПСЧ с ограниченными ресурсами рано или поздно зацикливается начинает повторять одну и ту же последовательность чисел. Длина циклов ГПСЧ зависит от самого генератора и часто составляет около 2 n / 2, где n размер внутреннего состояния в битах. Линейные конгруэнтные и LFSR- генераторы (Регистр сдвига с линейной обратной связью (РСЛОС, англ. Linear feedback shift register) обладают максимальными циклами порядка 2 n.

Период ГСПЧ (PRNG) (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 9 Большинство простых арифметических генераторов хотя и обладают большой скоростью, но страдают от многих серьёзных недостатков: Слишком короткий период/периоды. Последовательные значения не являются независимыми. Некоторые биты «менее случайны», чем другие. Неравномерное одномерное распределение. Обратимость.

С11. Pseudo-random sequence generation functions © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 10 В стандарте языка Си (ISO/IEC 9899:2011, сокр. С11) предусмотрены следующие функций генерации псевдослучайных чисел: #include int rand(void); void srand(unsigned int seed); …The rand function computes a sequence of pseudo-random integers in the range 0 to RAND_MAX … The value of the RAND_MAX macro shall be at least 32767… … The srand function uses the argument as a seed for a new sequence of pseudo-random numbers to be returned by subsequent calls to rand. If srand is then called with the same seed value, the sequence of pseudo-random numbers shall be repeated. If rand is called before any calls to srand have been made, the same sequence shall be generated as when srand is rst called with a seed value of 1. GLibC: RAND_MAX = C11

С11. Pseudo-random sequence generation functions (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 11 … EXAMPLE The following functions dene a portable implementation of rand and srand. static unsigned long int next = 1; int rand(void) // RAND_MAX assumed to be { next = next * ; return (unsigned int)(next/65536) % 32768; } void srand(unsigned int seed) { next = seed; } В стандарте также приведен пример линейного конгруэнтного генератора, который может быть использован для генерации случайных чисел. C11

GNU LibC © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 12 В реализации GNU LibC (GLibC) стандарта Си предлагается более широкий выбор функций генерации случайных чисел: ISO Random: PRNG, предусмотренный в С11 BSD Random: функции, заимствованные из BSD (Berkley Software Distribution). В настоящее время BSD называют семейство Unix- подобных операционных систем. SVID Random: функции, стандартизированные в системах SVID (System V Interface Definition) компании AT&T.

BSD random © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 13 // Выбор и инициализация начального состояния генератора char *initstate(unsigned int seed, char *state, size_t n); // Установка начального состояния генератора char *setstate(char *state); В BSD системах предусмотрен более сложный и гибкий генератор случайных чисел, который можно настраивать. Помимо линейного конгруэнтного генератора, аналогичного предложенному в стандарте языка СИ доступно еще 4 алгоритма генерации псевдослучайных чисел. Кроме стандартных функций, аналогичных функциям стандарта: BSD функцияАналог С11 long int random(void);int rand(void); void srandom(unsigned int seed);void srand(unsigned int seed); Доступны две дополнительные функции, которые позволяют выбирать тип используемого PRNG:

GNU C Library (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 14 glibc-2.18/stdlib/random_r.c /* Linear congruential. */ #define>TYPE_00 #define>BREAK_08 #define>DEG_00 #define>SEP_00 /* x[7] + x[3] + 1. */ #define>TYPE_11 #define>BREAK_132 #define>DEG_17 #define>SEP_13 /* x[15] + x + 1. */ #define>TYPE_22 #define>BREAK_264 #define>DEG_215 #define>SEP_21 /* x[31] + x[3] + 1. */ #define>TYPE_33 #define>BREAK_3128 #define>DEG_331 #define>SEP_33 /* x[63] + x + 1. */ #define>TYPE_44 #define>BREAK_4256 #define>DEG_463 #define>SEP_41 По умолчанию

Выбор ГСПЧ(PRNG) в GLibC © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 15 int __initstate_r (unsigned int seed, char *arg_state, size_t n, struct random_data *buf) { if (buf == NULL) goto fail; … int type; if (n >= BREAK_3) type = n < BREAK_4 ? TYPE_3 : TYPE_4; else if (n < BREAK_1) { if (n < BREAK_0) goto fail; type = TYPE_0; } else type = n < BREAK_2 ? TYPE_1 : TYPE_2; /* Linear congruential. */ #define>TYPE_00 #define>BREAK_08 #define>DEG_00 #define>SEP_00 /* x 7 + x */ #define>TYPE_11 #define>BREAK_132 #define>DEG_17 #define>SEP_13 /* x 15 + x + 1. */ #define>TYPE_22 #define>BREAK_264 #define>DEG_215 #define>SEP_21 glibc-2.18/stdlib/random_r.c

GNU C Library (glibc) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 16 glibc-2.18/stdlib/random_r.c int __random_r (struct random_data *buf, int32_t *result) {... if (buf->rand_type == TYPE_0) { int32_t val = state[0]; val = ((state[0] * ) ) & 0x7fffffff; state[0] = val; *result = val; }... Sourcema c Биты x n, формирующие случайноге число glibc (GCC) (m = 0x7FFFFFFF)

Алгоритм GLibC PRNG, TYPE0 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 17 #include int main() { int rval, i; int tmp[8]; // BREAK0 = 8 8 < BREAK1 = 32 initstate(1,(char*)tmp, 8); for(i=0;i

Алгоритм вычисления периода PRNG © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 18 input n for i 1 to n do rnd[i] = rand() // запомнить первые n псевдослучайных чисел found false // Флаг – признак обнаружения rnd i 1 // Проверяемый элемент rnd count n // Количество сгенерированных чисел while ( не found ) do if rnd[i] = rand() then // rnd[i] совпал, далее проверяем rnd[i+1] i i + 1 if i = n then // если совпали все n элементов - выход found true; else // если очередной элемент не совпал – проверяем сначала i 1; count count + 1 output count

Период GLibC ГСПЧ(PRNG), TYPE0 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 19 Sourcema c Биты x n, формирующие случайноге число glibc (GCC) Экспериментально полученное значение периода линейного конгруэнтного ГСПЧ, вычисленное согласно приведенному алгоритму, составляет Это означает, что последовательности чисел с номерами 1 – , – , – будут совпадать. Период такого генератора составляет примерно Такой период слишком мал, поэтому применение ГСПЧ типа 0 на практике не желательно.

Алгоритм GLibC PRNG, TYPE1 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 20 #include #define MAX 1000 #define seed 1 main() { int r[MAX], i, start = 0, tmp[32]; initstate(1,(char*)tmp,32); r[0] = seed; for (i=1; i 1, r1); } #define TYPE1 #define BREAK32 #define DEG7 #define SEP3

Период GLibC ГСПЧ(PRNG), TYPE1 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 21 Количество совпавших элементов Расстояние между совпадениями – n = Таким образом, период ГСПЧ типа 1 в ( / ) = 126 раз превышает период ГСПЧ типа 0. ГСПЧ типа 1 – 4 относятся к Аддитивным ГСПЧ и характеризуются существенно большим периодом по сравнению с линейным.

Принцип работы аддитивного ГСПЧ © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» #define TYPE1 #define BREAK32 #define DEG7 #define SEP3 DEGSEP Начальное заполнение массива производится при помощи линейного конгруэнтного генератора r[0] = seed; for (i=1; i

Принцип работы аддитивного ГСПЧ © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» #define TYPE1 #define BREAK32 #define DEG7 #define SEP3 DEGSEP Часть (SEP) элементов дублируется start = i; for (i=start; i < start + SEP; i++) { r[i] = r[i-DEG]; }

Принцип работы аддитивного ГСПЧ (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» #define TYPE1 #define BREAK32 #define DEG7 #define SEP3 DEGSEP start = i; for (i=start; i < start + DEG*10; i++) { r[i] = r[i-DEG] + r[i-SEP]; } 3. Первые k чисел обычно отбрасываются. В GLibC отбрасываются 10*DEG чисел.