Спектральный тест

Трехмерный график из 100 000 значений, созданный с помощью RANDU . Каждая точка представляет собой 3 последовательных псевдослучайных значения. Хорошо видно, что точки лежат в 15 двумерных плоскостях .

Спектральный тест — это статистический тест качества класса генераторов псевдослучайных чисел (PRNG), линейных конгруэнтных генераторов (LCG). ^[1] LCG обладают свойством: при построении в двух или более измерениях образуются линии или гиперплоскости, на которых можно найти все возможные выходные данные. ^[2] Спектральный тест сравнивает расстояние между этими плоскостями; чем дальше они друг от друга, тем хуже генератор. ^[3] Поскольку этот тест разработан для изучения решетчатых структур LCG, его нельзя применять к другим семействам PRNG.

По словам Дональда Кнута , ^[4] это, безусловно, самый мощный из известных тестов, поскольку он может не дать результатов LCG, которые проходят большинство статистических тестов. Подпрограмма IBM RANDU ^[5]^[6] LCG не проходит этот тест для трех измерений и выше.

Пусть ГПСЧ генерирует последовательность $u_{1},u_{2},\dots$ . Позволять $1/\nu _{t}$ — максимальное расстояние между покрывающими параллельными плоскостями последовательности $\{(u_{n+1:n+t})|n=0,1,\dots \}$ . Спектральный тест проверяет, что последовательность $\nu _{2},\nu _{3},\nu _{4},\dots$ не разлагается слишком быстро.

Кнут рекомендует проверить, что каждое из следующих 5 чисел больше 0,01. ${\begin{aligned}\mu _{2}&=\pi \nu _{2}^{2}/m,&\mu _{3}&={\frac {4}{3}}\pi \nu _{3}^{3}/m,&\mu _{4}&={\frac {1}{2}}\pi ^{2}\nu _{4}^{4}/m\\[1ex]&&\mu _{5}&={\frac {8}{15}}\pi ^{2}\nu _{5}^{5}/m,&\mu _{6}&={\frac {1}{6}}\pi ^{3}\nu _{6}^{6}/m\end{aligned}}$ где $m$ – модуль ЛКГ.

Цифры достоинств

Кнут определяет показатель качества , который описывает, насколько близко разделение $1/\nu _{t}$ находится на теоретическом минимуме. В новой нотации Стила и Винья для измерения $d$ , фигура $f_{d}$ определяется как: ^[7]^: 3

f_{d}(m,a)=\nu _{d}/(\gamma _{d}^{\tfrac {1}{2}}{\sqrt[{d}]{m}})

,

где $a,m,\nu _{d}$ определяются, как и раньше, и $\gamma _{d}$ постоянная Эрмита размерности d . $\gamma _{d}^{\tfrac {1}{2}}{\sqrt[{d}]{m}}$ – минимально возможное межплоскостное расстояние. ^[7]^: 3

L'Ecuyer 1991 далее вводит две меры, соответствующие минимуму $f_{d}$ во многих измерениях. ^[8] Опять же под повторной записью, ${\mathcal {M}}_{d}^{+}(m,a)$ это минимум $f_{d}$ для LCG от габаритов от 2 до $d$ , и ${\mathcal {M}}_{d}^{*}(m,a)$ то же самое для мультипликативного конгруэнтного генератора псевдослучайных чисел (MCG), т.е. такого, в котором используется только умножение, или $c=0$ . Стил и Винья отмечают, что $f_{d}$ в этих двух случаях рассчитывается по-разному, что требует отдельных значений. ^[7]^: 13 Они также определяют «гармоничный» средневзвешенный показатель качества, ${\mathcal {H}}_{d}^{+}(m,a)$ (и ${\mathcal {H}}_{d}^{*}(m,a)$ ). ^[7]^: 13

Примеры

Небольшой вариант печально известного RANDU , с $x_{n+1}=65539\,x_{n}{\bmod {2}}^{29}$ имеет: ^[4]^{: (Таблица 1)}

д	2	3	4	5	6	7	8
н ² _д	536936458	118	116	116	116
μ_мкд	3.14	10 ⁻⁵	10 ⁻⁴	10 ⁻³	0.02
ж _д^[а]	0.520224	0.018902	0.084143	0.207185	0.368841	0.552205	0.578329

Совокупные показатели достоинств таковы: ${\mathcal {M}}_{8}^{*}(65539,2^{29})=0.018902$ , ${\mathcal {H}}_{8}^{*}(65539,2^{29})=0.330886$ . ^[а]

Джорджа Марсальи (1972) Соображения $x_{n+1}=69069\,x_{n}{\bmod {2}}^{32}$ как «кандидат на лучший из всех множителей», потому что его легко запомнить и он имеет особенно большие спектральные тестовые числа. ^[9]

д	2	3	4	5	6	7	8
н ² _д	4243209856	2072544	52804	6990	242
μ_мкд^[б]	3.10	2.91	3.20	5.01	0.017
ж _д^[а]	0.462490	0.313127	0.457183	0.552916	0.376706	0.496687	0.685247

Совокупные показатели достоинств таковы: ${\mathcal {M}}_{8}^{*}(69069,2^{32})=0.313127$ , ${\mathcal {H}}_{8}^{*}(69069,2^{32})=0.449578$ . ^[а]

Steele & Vigna (2020) предоставляют множителям самые высокие совокупные показатели качества для многих вариантов m = 2. ^н и заданная битовая длина файла . Они также обеспечивают индивидуальное $f_{d}$ значения и пакет программ для расчета этих значений. ^[7]^: 14–5 Например, они сообщают, что лучший 17-битный a для m = 2 ³² является:

Для LCG (c ≠ 0) 0x1dab5 (121525). ${\mathcal {M}}_{8}^{+}=0.6403$ , ${\mathcal {H}}_{8}^{+}=0.6588$ . ^[7]^: 14
Для MCG (c = 0) 0x1e92d (125229). ${\mathcal {M}}_{8}^{*}=0.6623$ , ${\mathcal {H}}_{8}^{*}=0.7497$ . ^[7]^: 14

Дополнительная иллюстрация

Несмотря на то, что оба отношения проходят тест хи-квадрат , первый LCG менее случайен, чем второй, поскольку диапазон значений, которые он может выдавать в том порядке, в котором он их производит, распределен менее равномерно.

Ссылки

^ Jump up to: Перейти обратно: ^а ^б ^с ^д Рассчитано с использованием программного обеспечения Steele & Vigna (2020), программа «mspect» (src/spect.cpp, мультипликативный режим).
^ Рассчитано по ν ²
_d сообщил Марсалья.

^ Уильямс, КБ; Дуайер, Джерри (1 августа 1996 г.), «Тестирование генераторов случайных чисел, часть 2» , Журнал доктора Добба , получено 26 января 2012 г.
^ Марсалья, Джордж (сентябрь 1968 г.). «Случайные числа падают в основном в плоскостях» (PDF) . ПНАС . 61 (1): 25–28. Бибкод : 1968ПНАС...61...25М . дои : 10.1073/pnas.61.1.25 . ПМЦ 285899 . ПМИД 16591687 .
^ Джайн, Радж. «Тестирование генераторов случайных чисел (лекция)» (PDF) . Вашингтонский университет в Сент-Луисе . Проверено 2 декабря 2016 г.
^ Jump up to: Перейти обратно: ^а ^б Кнут, Дональд Э. (1981), «3.3.4: Спектральный тест», Искусство компьютерного программирования, том 2: Получисловые алгоритмы (2-е изд.), Аддисон-Уэсли .
^ IBM, Пакет научных подпрограмм System/360, версия II, Руководство программиста, H20-0205-1, 1967, стр. 54.
^ Международная корпорация бизнес-машин (1968). «Пакет подпрограмм IBM/360 Scientific (360A-CM-03X), версия III» (PDF) . Библиотека Стэна . II . Уайт-Плейнс, штат Нью-Йорк: Отдел технических публикаций IBM: 77. doi : 10.3247/SL2Soft08.001 . Программа научного применения H20-0205-3.
^ Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г Стил, Гай Л. младший ; Винья, Себастьяно (февраль 2022 г.) [15 января 2020 г.]. «Простые в вычислении спектрально хорошие множители для конгруэнтных генераторов псевдослучайных чисел» (PDF) . Программное обеспечение: практика и опыт . 52 (2): 443–458. arXiv : 2001.05304 . дои : 10.1002/сп.3030 . Сопутствующее программное обеспечение и данные доступны по адресу https://github.com/vigna/CPRNG .
^ Л'Экуйер, Пьер (январь 1999 г.). «Таблицы линейных конгруэнтных генераторов разных размеров и хорошей решетчатой структуры» (PDF) . Математика вычислений . 68 (225): 249–260. Бибкод : 1999MaCom..68..249L . CiteSeerX 10.1.1.34.1024 . дои : 10.1090/S0025-5718-99-00996-5 . Обязательно прочтите « Ошибки» . также
^ Марсалья, ДЖОРДЖ (1972-01-01), Заремба, С.К. (редактор), «Структура линейных конгруэнтных последовательностей» , «Приложения теории чисел к численному анализу » , Academic Press, стр. 249–285, ISBN 978-0-12-775950-0 , получено 29 января 2024 г.

Дальнейшее чтение

Энтачер, Карл (январь 1998 г.). «Плохие подпоследовательности известных линейных конгруэнтных генераторов псевдослучайных чисел». ACM-транзакции по моделированию и компьютерному моделированию . 8 (1): 61–70. дои : 10.1145/272991.273009 . – перечисляет $f_{d}$ $f_ {d}$ (обозначается как $S_{s}$ $S_{s}$ в этом тексте) многих известных LCG
- Расширенная версия этой работы доступна по адресу: Энтачер, Карл (2001). «Коллекция избранных генераторов псевдослучайных чисел с линейными структурами — расширенная версия» .

[SSSoft-9] Jump up to: Перейти обратно: ^а ^б ^с ^д Рассчитано с использованием программного обеспечения Steele & Vigna (2020), программа «mspect» (src/spect.cpp, мультипликативный режим).

[11] Рассчитано по ν ²
_d сообщил Марсалья.

[1] Уильямс, КБ; Дуайер, Джерри (1 августа 1996 г.), «Тестирование генераторов случайных чисел, часть 2» , Журнал доктора Добба , получено 26 января 2012 г.

[Marsaglia68-2] Марсалья, Джордж (сентябрь 1968 г.). «Случайные числа падают в основном в плоскостях» (PDF) . ПНАС . 61 (1): 25–28. Бибкод : 1968ПНАС...61...25М . дои : 10.1073/pnas.61.1.25 . ПМЦ 285899 . ПМИД 16591687 .

[3] Джайн, Радж. «Тестирование генераторов случайных чисел (лекция)» (PDF) . Вашингтонский университет в Сент-Луисе . Проверено 2 декабря 2016 г.

[:0-4] Jump up to: Перейти обратно: ^а ^б Кнут, Дональд Э. (1981), «3.3.4: Спектральный тест», Искусство компьютерного программирования, том 2: Получисловые алгоритмы (2-е изд.), Аддисон-Уэсли .

[5] IBM, Пакет научных подпрограмм System/360, версия II, Руководство программиста, H20-0205-1, 1967, стр. 54.

[6] Международная корпорация бизнес-машин (1968). «Пакет подпрограмм IBM/360 Scientific (360A-CM-03X), версия III» (PDF) . Библиотека Стэна . II . Уайт-Плейнс, штат Нью-Йорк: Отдел технических публикаций IBM: 77. doi : 10.3247/SL2Soft08.001 . Программа научного применения H20-0205-3.

[Steele20-7] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г Стил, Гай Л. младший ; Винья, Себастьяно (февраль 2022 г.) [15 января 2020 г.]. «Простые в вычислении спектрально хорошие множители для конгруэнтных генераторов псевдослучайных чисел» (PDF) . Программное обеспечение: практика и опыт . 52 (2): 443–458. arXiv : 2001.05304 . дои : 10.1002/сп.3030 . Сопутствующее программное обеспечение и данные доступны по адресу https://github.com/vigna/CPRNG .

[LEcuyer99-8] Л'Экуйер, Пьер (январь 1999 г.). «Таблицы линейных конгруэнтных генераторов разных размеров и хорошей решетчатой структуры» (PDF) . Математика вычислений . 68 (225): 249–260. Бибкод : 1999MaCom..68..249L . CiteSeerX 10.1.1.34.1024 . дои : 10.1090/S0025-5718-99-00996-5 . Обязательно прочтите « Ошибки» . также

[10] Марсалья, ДЖОРДЖ (1972-01-01), Заремба, С.К. (редактор), «Структура линейных конгруэнтных последовательностей» , «Приложения теории чисел к численному анализу » , Academic Press, стр. 249–285, ISBN 978-0-12-775950-0 , получено 29 января 2024 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[а]

[9]

[б]