TestU01

TestU01 to biblioteka oprogramowania , zaimplementowana w języku ANSI C , która oferuje zbiór narzędzi do empirycznego testowania losowości generatorów liczb losowych (RNG). Biblioteka została po raz pierwszy wprowadzona w 2007 roku przez Pierre'a L'Ecuyera i Richarda Simarda z Université de Montréal .

Biblioteka implementuje kilka typów generatorów liczb losowych, w tym niektóre proponowane w literaturze i niektóre spotykane w powszechnie używanym oprogramowaniu. Zawiera ogólne implementacje klasycznych testów statystycznych dla generatorów liczb losowych, a także kilka innych proponowanych w literaturze i kilka oryginalnych. Testy te można zastosować do generatorów predefiniowanych w bibliotece, generatorów zdefiniowanych przez użytkownika oraz strumieni liczb losowych przechowywanych w plikach. Specyficzne zestawy testów dla obu sekwencji uniformów dostępne są również liczby losowe w [0,1] lub sekwencje bitów. Udostępniono również podstawowe narzędzia do wykreślania wektorów punktów wytwarzanych przez generatory.

Historia

Początkowa bateria testów losowości dla RNG została zaproponowana w pierwszym wydaniu The Art of Computer Programming z 1969 roku przez Donalda Knutha . Testy Knutha zostały następnie wyparte przez testy Diehard (1996) George'a Marsaglii, składające się z piętnastu różnych testów. Brak możliwości modyfikacji parametrów testu lub dodania nowych testów doprowadził do powstania biblioteki TestU01.

Cechy

TestU01 oferuje cztery grupy modułów do analizy RNG:

Wdrażanie (wstępnie zaprogramowanych) RNG;
Implementacja określonych testów statystycznych;
Implementacja baterii testów statystycznych;
Stosowanie testów do całych rodzin RNG.

₀ Gdy określony test zostanie zastosowany do próbki o wielkości n wyprodukowanej przez RNG, wartość p testu zwykle pozostanie rozsądna, gdy wielkość próbki wzrośnie, dopóki wielkość próbki nie osiągnie n , powiedzmy. Po tym str -wartość rozbiega się do 0 lub 1 z prędkością wykładniczą. Moduł 4 umożliwia badaczowi zbadanie interakcji między konkretnym testem a strukturą zbiorów punktowych wytwarzanych przez daną rodzinę RNG. Technikę tę można wykorzystać do określenia, jak duża powinna być wielkość próbki w funkcji długości okresu generatora, zanim generator zacznie systematycznie zawodzić test.

TESTU01 oferuje kilka baterii testów, w tym „Small Crush” (składający się z 10 testów), „Crush” (96 testów) i „Big Crush” (106 testów). Konkretne testy stosowane przez każdą baterię są szczegółowo opisane w podręczniku użytkownika. Pentium 4 1,7 GHz z systemem Red Hat Linux 9.0, dla prostego RNG, Small Crush zajmuje około 2 minut. Crush trwa około 1,7 godziny. Big Crush trwa około 4 godzin. W przypadku bardziej złożonego RNG wszystkie te czasy zwiększają się dwukrotnie lub więcej. Dla porównania, testy Diehard trwają około 15 sekund.

Ograniczenia

TestU01 akceptuje tylko 32-bitowe dane wejściowe i interpretuje je jako wartości z zakresu [0, 1]. Powoduje to, że jest bardziej wrażliwy na błędy w najbardziej znaczących bitach niż w najmniej znaczących bitach. Ważne jest, aby przetestować generatory ogólnego przeznaczenia w postaci odwróconej bitowo, aby zweryfikować ich przydatność do zastosowań wykorzystujących bity niskiego rzędu.

Generatory, które wytwarzają 64 bity na wyjściu dodatkowo wymagają osobnych testów dla ich górnej i dolnej połowy.

Zobacz też