테스트U01

TestU01

TestU01은 ANSI C 언어로 구현된 소프트웨어 라이브러리로, RNG(Random number generator)의 경험적 무작위성 테스트를 위한 유틸리티 컬렉션을 제공한다.[1]이 도서관은 2007년 피에르 레쿠이어와 몬트레알 대학의 리처드 시마드에 의해 처음 소개되었다.[2]null

도서관은 문헌에서 제안된 것과 널리 사용되는 소프트웨어에서 발견되는 것을 포함하여 몇 가지 유형의 난수 생성기를 구현한다.그것은 문헌에서 제안된 다른 몇 개와 일부 원본뿐만 아니라 난수 발생기에 대한 고전적 통계적 시험의 일반적인 구현을 제공한다.이러한 테스트는 라이브러리에 미리 정의된 생성기, 사용자 정의 생성기 및 파일에 저장된 무작위 번호 스트림에 적용할 수 있다.[0,1] 또는 비트 시퀀스의 균일한 무작위 번호 시퀀스에 대한 특정 테스트 제품군도 이용할 수 있다.발전기에 의해 생성된 점의 벡터 플롯을 위한 기본 도구도 제공된다.null

역사

RNG에 대한 무작위 테스트의 초기 배터리는 1969년 도날드 크누스의 "The Art of Computer Programming" 초판에 제시되었다.크누스의 테스트는 15개의 다른 테스트로 구성된 조지 마르사글리아의 디하르트 테스트(1996)로 대체되었다.시험 매개변수를 수정하거나 새로운 시험을 추가할 수 없게 되어 TestU01 라이브러리가 개발되었다.null

특징들

TestU01은 RNG 분석을 위한 네 가지 모듈 그룹을 제공한다.

  1. RNG 구현(사전 프로그래밍)
  2. 특정 통계적 시험의 실시
  3. 통계적 시험의 배터리 구현.
  4. RNG 가족 전체에 시험 적용.

RNG에 의해 생산된 n 크기의 표본에 특정 시험을 적용할 때, 예를 들어, 표본 크기가0 n에 도달할 때까지 표본 크기가 증가함에 따라 시험의 p-값은 일반적으로 합리적으로 유지된다.이후 p-값은 지수 속도로 0 또는 1로 분산된다.모듈 4는 연구자가 특정 시험과 특정 RNG 계열에 의해 생성된 점 집합의 구조 사이의 상호작용을 연구할 수 있도록 한다.이 기법은 발전기가 시험에 체계적으로 실패하기 전에 발전기 주기 길이의 함수로 표본 크기가 얼마나 커야 하는지를 결정하는 데 사용할 수 있다.null

TESTU01은 "Small Crush" (10개의 테스트로 구성됨), "Crush" (96개 테스트), "Big Crush" (160 테스트)를 포함한 여러 테스트 배터리를 제공한다.각 배터리에 의해 적용되는 구체적인 테스트는 사용자 가이드에 자세히 설명되어 있다.[3]Red Hat Linux 9.0을 실행하는 1.7GHz 펜티엄 4에서는 간단한 RNG를 위해 Small Crush가 약 2분 정도 걸린다.크러쉬는 약 1.7시간이 걸린다.빅 크러쉬는 4시간 정도 걸린다.더 복잡한 RNG의 경우, 이 모든 시간이 2배 이상 증가한다.비교를 위해, 다이하르트 테스트는 실행하는데 약 15초가 걸린다.null

제한 사항

TestU01은 32비트 입력만을 받아들여 [0, 1] 범위의 값으로 해석한다.이로 인해 가장 중요한 비트의 결함에 가장 덜 중요한 비트보다 더 민감하게 된다.범용 발전기를 비트역전 형태로 테스트하여 저차 비트를 사용하는 어플리케이션에 적합성을 검증하는 것이 중요하다.[4]: 4 null

64비트의 출력을 추가로 생성하는 발전기는 하이비트와 로우비트에 대해 별도의 시험을 필요로 한다.[5]: 51 null

참고 항목

참조

  1. ^ TestU01 웹 사이트.
  2. ^ Pierre L'Ecuyer & Richard Simard(2007), "Random Number Generators의 경험적 시험에 대한 ANSI C의 소프트웨어 라이브러리", ACM Transactions on Mathematical Software, 33:22.
  3. ^ TestU01 사용 설명서.
  4. ^ Vigna, Sebastiano (July 2016). "An experimental exploration of Marsaglia's xorshift generators, scrambled" (PDF). ACM Transactions on Mathematical Software. 42 (4): 30. arXiv:1402.6246. doi:10.1145/2845077.
  5. ^ O'Neill, Melissa E. (5 September 2014). PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation (PDF) (Technical report). Harvey Mudd College. HMC-CS-2014-0905.