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

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

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

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

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

Генерация случайных чисел (2) 6 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. Генерация согласно заданному распределению вероятностей. Такие методы в основном используют числа с равномерным распределением и известную функцию плотности некоторого распределения (например нормального). В зависимости от источника равномерного распределения результат будет либо псевдослучайным либо случайным.

Генерация псевдослучайных чисел 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) Borland Delphi, Virtual Pascal m, m > 0 – модуль (modulus); a, m > a > 0 – мультипликатор (multiplier); c, m > c 0 – инкремент (increment) x 0 – случайное зерно.

GNU C Library (glibc) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 8 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)

GNU C Library (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 9 glibc-2.18/stdlib/random_r.c /* 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 /* x 31 + x */ #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