Запись 84 - Прохвессиональное продолжается
Возвращаясь к старой теме. Вот мне чего тогда не хватало. Пришлось самому.
Это результаты применения батарей "Rabbit" (26 тестов для целых чисел) и "SmallCrush" (10 тестов для вещественных чисел в диапазоне [0..1]) из комплекта TestU1. Проверяется вероятность истинности гипотезы: генератор плохой, но сумел обмануть и пройти тест. Очевидно, если p -> 1, то генератор тест провалил заслуженно. Если p -> 0, то генератор близок к идеалу. В результатах применяется обозначение "eps" и "eps1" - это очень маленькие чиселки, 10 в минус какой-то степени. То есть, вердикт "1-eps" означает, что чего-то в генераторе неладно, а "eps" - все очень и очень хорошо. Стоп! А нафига "eps" тоже считается провалом теста? Дёло в тём, что тесты проверяют не близость к идеалу, а похожесть на настоящий шум и бардак, полученный из природы. Природа может позволить себе изредка 10 снарядов в одну воронку, но искусственный генератор никогда не выкинет в тетрисе подряд 10 палок. Поэтому с точки зрения теста "слишком хорошо" это тоже "плохо".
Вот так (на примере xorshift 32 bit) выглядят сами результаты.
Test p-value
----------------------------------------------
1 BirthdaySpacings eps
2 Collision 1 - eps1
6 MaxOft 5.6e-16
8 MatrixRank eps
10 RandomWalk1 H 1.0e-12
----------------------------------------------
All other tests were passed
Test p-value
----------------------------------------------
1 MultinomialBitsOver 8.0e-20
4 AppearanceSpacings 1 - eps1
6 LempelZiv 1 - eps1
10 PeriodsInStrings 6.0e-04
11 HammingWeight 2.5e-07
15 HammingIndep, L = 16 eps
20 Run of bits eps
24 RandomWalk1 H 1.4e-04
26 RandomWalk1 H (L = 10016) 3.4e-05
----------------------------------------------
All other tests were passed
А это сводка.
Кто же чемпион? Самый модный и распиаренный сейчас это "Мерсенн Твистер", но он: 1) сложный и медленный, моделировать на 10000 процессорах погоду я бы с его помощю не стал; 2) не слишком равномерный, вычислять площадь фигуры, кидая на плоскость случаныйе точки, я бы ему не поручил. Как ни странно, рулит старый (как говно мамонта) и добрый (как папа Карло) линейный конгруэнтный метод x[i+1]=(a*x[i]+c)%m (лучше даже с с=0) и его простейшие преобразования.
З.Ы. К вопросу о "случайности" природы. Мужик взял и обсчитал результыты спорлото за все годы. И офигел. То ли лохотрон оказался "с магнитиками" (спрашивается, нафига?). То ли боженька mwc1616 заюзал? А вот еще пример. Радиусы орбит планет Солнечной системы подчиняются очень простой закономерности, которая не обосновывается никами математическими теоремами и физическими законами. Просто вот так получилось. Или опять боженька не нашел ничего лучшего, кроме RANDU?
Это результаты применения батарей "Rabbit" (26 тестов для целых чисел) и "SmallCrush" (10 тестов для вещественных чисел в диапазоне [0..1]) из комплекта TestU1. Проверяется вероятность истинности гипотезы: генератор плохой, но сумел обмануть и пройти тест. Очевидно, если p -> 1, то генератор тест провалил заслуженно. Если p -> 0, то генератор близок к идеалу. В результатах применяется обозначение "eps" и "eps1" - это очень маленькие чиселки, 10 в минус какой-то степени. То есть, вердикт "1-eps" означает, что чего-то в генераторе неладно, а "eps" - все очень и очень хорошо. Стоп! А нафига "eps" тоже считается провалом теста? Дёло в тём, что тесты проверяют не близость к идеалу, а похожесть на настоящий шум и бардак, полученный из природы. Природа может позволить себе изредка 10 снарядов в одну воронку, но искусственный генератор никогда не выкинет в тетрисе подряд 10 палок. Поэтому с точки зрения теста "слишком хорошо" это тоже "плохо".
Вот так (на примере xorshift 32 bit) выглядят сами результаты.
Test p-value
----------------------------------------------
1 BirthdaySpacings eps
2 Collision 1 - eps1
6 MaxOft 5.6e-16
8 MatrixRank eps
10 RandomWalk1 H 1.0e-12
----------------------------------------------
All other tests were passed
Test p-value
----------------------------------------------
1 MultinomialBitsOver 8.0e-20
4 AppearanceSpacings 1 - eps1
6 LempelZiv 1 - eps1
10 PeriodsInStrings 6.0e-04
11 HammingWeight 2.5e-07
15 HammingIndep, L = 16 eps
20 Run of bits eps
24 RandomWalk1 H 1.4e-04
26 RandomWalk1 H (L = 10016) 3.4e-05
----------------------------------------------
All other tests were passed
А это сводка.
Кто же чемпион? Самый модный и распиаренный сейчас это "Мерсенн Твистер", но он: 1) сложный и медленный, моделировать на 10000 процессорах погоду я бы с его помощю не стал; 2) не слишком равномерный, вычислять площадь фигуры, кидая на плоскость случаныйе точки, я бы ему не поручил. Как ни странно, рулит старый (как говно мамонта) и добрый (как папа Карло) линейный конгруэнтный метод x[i+1]=(a*x[i]+c)%m (лучше даже с с=0) и его простейшие преобразования.
З.Ы. К вопросу о "случайности" природы. Мужик взял и обсчитал результыты спорлото за все годы. И офигел. То ли лохотрон оказался "с магнитиками" (спрашивается, нафига?). То ли боженька mwc1616 заюзал? А вот еще пример. Радиусы орбит планет Солнечной системы подчиняются очень простой закономерности, которая не обосновывается никами математическими теоремами и физическими законами. Просто вот так получилось. Или опять боженька не нашел ничего лучшего, кроме RANDU?