Качество генерации псевдослучайных чисел в системах имитационного моделирования OpenGPSS, GPSS World и AnyLogic Диденко Дмитрий Георгиевич Старший преподаватель кафедры ММСА ННК «ІПСА» Национальный технический университет Украины «Киевский политехнический институт» Киев, Украина
Диденко Д.Г. © Качество генерации псевдослучайных чисел в системах моделирования От Бернулли до Вейбула: OpenGPSS (29 распределений); GPSS World (24 распределения); AnyLogic (29 распределений). 1. Большое количество вероятностных распределений
Диденко Д.Г. © Качество генерации псевдослучайных чисел в системах моделирования Наборы (батареи) тестов: NIST; TEST-U01; CRYPT-X; The pLab Project; DIEHARD; ENT. 2. Тесты псевдослучайных последовательностей
Диденко Д.Г. © Качество генерации псевдослучайных чисел в системах моделирования Наборы (батареи) тестов: NIST; TEST-U01; CRYPT-X; The pLab Project; DIEHARD; ENT. 2. Тесты псевдослучайных последовательностей
Диденко Д.Г. © Качество генерации псевдослучайных чисел в системах моделирования Схема проведения эксперимента OpenGPSS, GPSS World, AnyLogic TXT- Файл 46 МБайт 4 млн. строк TXT- Файл результатов GPSS- программа, JAVA- программа BIN-Файл 15 МБайт VB- скрипт Тесты Diehard
Диденко Д.Г. © Качество генерации псевдослучайных чисел в системах моделирования Схема проведения эксперимента OpenGPSS, GPSS World, AnyLogic TXT- Файл 46 МБайт 4 млн. строк TXT- Файл результатов GPSS- программа, JAVA- программа BIN-Файл 15 МБайт VB- скрипт Тесты Diehard
Диденко Д.Г. © Качество генерации псевдослучайных чисел в системах моделирования Схема проведения эксперимента OpenGPSS, GPSS World, AnyLogic TXT- Файл 46 МБайт 4 млн. строк TXT- Файл результатов GPSS- программа, JAVA- программа BIN-Файл 15 МБайт VB- скрипт Тесты Diehard
Диденко Д.Г. © Качество генерации псевдослучайных чисел в системах моделирования Схема проведения эксперимента OpenGPSS, GPSS World, AnyLogic TXT- Файл 46 МБайт 4 млн. строк TXT- Файл результатов GPSS- программа, JAVA- программа BIN-Файл 15 МБайт VB- скрипт Тесты Diehard
Диденко Д.Г. © Качество генерации псевдослучайных чисел в системах моделирования Схема проведения эксперимента OpenGPSS, GPSS World, AnyLogic TXT- Файл 46 МБайт 4 млн. строк TXT- Файл результатов GPSS- программа, JAVA- программа BIN-Файл 15 МБайт VB- скрипт Тесты Diehard
Диденко Д.Г. © Качество генерации псевдослучайных чисел в системах моделирования Схема проведения эксперимента OpenGPSS, GPSS World, AnyLogic TXT- Файл 46 МБайт 4 млн. строк TXT- Файл результатов GPSS- программа, JAVA- программа BIN-Файл 15 МБайт VB- скрипт Тесты Diehard
Диденко Д.Г. © Качество генерации псевдослучайных чисел в системах моделирования Схема проведения эксперимента OpenGPSS, GPSS World, AnyLogic TXT- Файл 46 МБайт 4 млн. строк TXT- Файл результатов GPSS- программа, JAVA- программа BIN-Файл 15 МБайт VB- скрипт Тесты Diehard
Диденко Д.Г. © Качество генерации псевдослучайных чисел в системах моделирования Схема проведения эксперимента OpenGPSS, GPSS World, AnyLogic TXT- Файл 46 МБайт 4 млн. строк TXT- Файл результатов GPSS- программа, JAVA- программа BIN-Файл 15 МБайт VB- скрипт Тесты Diehard
Диденко Д.Г. © Качество генерации псевдослучайных чисел в системах моделирования RMULT 300;начальное смещение GENERATE 1 ;переносим псевдослучайное число в сохраняемую ;величину SAVEVALUE XN1,RN1 TERMINATE ;временной сегмент GENERATE 1024 TERMINATE 1 START Тестовая программа для OpenGPSS
Диденко Д.Г. © Качество генерации псевдослучайных чисел в системах моделирования FACTORY FUNCTION RN1,C2 0,-0.5/1,0.5 ;Scale1 = 2 ^ = PLATE VARIABLE FN$FACTORY# \1 GENERATE 1 WRITE V$PLATE,1 TERMINATE ;генерируем один из транзактов, который будет открывать/закрывать файл GENERATE 1,,,1 OPEN "d:\test.txt",1,ERROR_BLOCK_1 ADVANCE ;устанавливаем количество сгенерированных чисел CLOSE 100,1 TERMINATE 1 ERROR_BLOCK_1 TERMINATE 1 RMULT 200 START Тестовая программа для GPSS World
Диденко Д.Г. © Качество генерации псевдослучайных чисел в системах моделирования double x; int z; for( int i=0; i
Диденко Д.Г. © Качество генерации псевдослучайных чисел в системах моделирования Результаты прохождения тестов из пакета DIEHARD ТестOpenGPSSGPSS WorldAnyLogic 1Дни рождения+-+ 2Пересекающиеся перестановки-+- 3Ранги матриц+/-/-+/+/+ 4Поток битов+-+ 5Обезьяньи тесты-++ 6Подсчёт единичек-/--/++/+ 7Тест на парковку-++
Диденко Д.Г. © Качество генерации псевдослучайных чисел в системах моделирования Результаты прохождения тестов из пакета DIEHARD (продолжение) ТестOpenGPSSGPSS WorldAnyLogic 8Тест на минимальное расстояние-++ 9Тест случайных сфер+++ 10Тест сжатия-+- 11Тест пересекающихся сумм+++ 12Тест последовательностей+++ 13Тест игры в кости-/-+/+
Диденко Д.Г. © Качество генерации псевдослучайных чисел в системах моделирования Проверка статистической гипотезы о случайности потока данных Система моделирования Количество пройденных тестов Критерий Хи- квадрат Анализ результата OpenGPSS590,00- GPSS World1029,45+ AnyLogic1128,17+ Табличное значение критерия Хи-квадрат 36,2
Диденко Д.Г. © Качество генерации псевдослучайных чисел в системах моделирования Работа с системным пакетом dbms_random: 1) начальное смещение для ГПЧ dbms_random.seed(300); 2) получение следующего числа a := dbms_random.random; 8. Использование встроенного ГПЧ из СУБД Oracle
Диденко Д.Г. © Качество генерации псевдослучайных чисел в системах моделирования Преимущества и недостатки dbms_random: + встроенный в Oracle; + широкое использование; - нельзя получить текущее смещение. 8. Использование встроенного ГПЧ из СУБД Oracle (продолжение)
Диденко Д.Г. © Качество генерации псевдослучайных чисел в системах моделирования линейный конгруэнтный метод X n+1 = (aX n + c) mod m; квадратичный конгруэнтный метод Х n+1 = (dX n 2 +aX n +c) mod m; генератор на основе объединения путём сложения по mod 2 32 двух генераторов: запаздывающего генератора Фибоначчи X n = X n-99 X n-33 mod 2 32 и генератора на основе произведения с переносом Y n = Y n-1 carry mod 2 16 ; генератор М-последовательностей; вихрь Мерсена. 9. Способы улучшения ГПЧ
Диденко Д.Г. © Качество генерации псевдослучайных чисел в системах моделирования расширенный конгруэнтный генератор - X n = 2 13 (X n-1 + X n-2 + X n-3 ) mod ( ); алгоритм Marsaglia-Multicarry (Джордж Марсаглия); алгоритм xor-shift (Джордж Марсаглия); алгоритм Блюма-Блюма-Шуба; генератор на базе произведения с переносом - X n = ( X n X n X n X n-1 ) carry mod 2 32 ; генератор на базе произведения с переносом - X n = a X n-1 carry mod Модификации Линейного Конгруэнтного Метода
Диденко Д.Г. © Качество генерации псевдослучайных чисел в системах моделирования Примеры Линейного Конгруэнтного Метода ИсточникmacБиты 1Numerical Recipes Borland C/C GNU Compiler Collection glibc (используется в GCC) ANSI C: Open Watcom, Digital Mars, Metrowerks, IBM VisualAge C/C Borland Delphi, Virtual Pascal Microsoft Visual/Quick C/C Apple CarbonLib
Диденко Д.Г. © Качество генерации псевдослучайных чисел в системах моделирования Примеры Линейного Конгруэнтного Метода (продолжение) ИсточникmacБиты 9 Microsoft Visual Basic (версия 6 и ниже) RtlUniform from Native API MMIX Дональда Кнута VAX's MTH$RANDOM (старая версия библиотеки glibc) LC53 в языке программирования Forth Random class in Java API MS Fortran
Диденко Д.Г. © Качество генерации псевдослучайных чисел в системах моделирования Результаты прохождения тестов из пакета DIEHARD Тест OpenGPSS GPSS WorldAnyLogic Дни рождения+--+ 2Пересекающиеся перестановки-++- 3Ранги матриц+/-/-+/+/-+/+/+ 4Поток битов+--+ 5Обезьяньи тесты-+++ 6Подсчёт единичек-/--/+ +/+ 7Тест на парковку-+++
Диденко Д.Г. © Качество генерации псевдослучайных чисел в системах моделирования Результаты прохождения тестов из пакета DIEHARD (продолжение) Тест OpenGPSS GPSS WorldAnyLogic Тест случайных сфер Тест сжатия Тест пересекающихся сумм Тест последовательностей Тест игры в кости-/-+/+
Диденко Д.Г. © Качество генерации псевдослучайных чисел в системах моделирования Проверка статистической гипотезы о случайности потока данных Система моделирования Количество пройденных тестов Критерий Хи- квадрат Анализ результата OpenGPSS ,00- OpenGPSS MS Fortran 1224,46+ GPSS World1029,45+ AnyLogic1128,17+ Табличное значение критерия Хи-квадрат 36,2
Диденко Д.Г. © Качество генерации псевдослучайных чисел в системах моделирования Настройка ГПЧ в системе OpenGPSS
Диденко Д.Г. © Качество генерации псевдослучайных чисел в системах моделирования 29 Спасибо за внимание