Conferences in Research and Practice in Information Technology
  

Online Version - Last Updated - 20 Jan 2012

 

 
Home
 

 
Procedures and Resources for Authors

 
Information and Resources for Volume Editors
 

 
Orders and Subscriptions
 

 
Published Articles

 
Upcoming Volumes
 

 
Contact Us
 

 
Useful External Links
 

 
CRPIT Site Search
 
    

Tuning the Collision Test for Power

Tsang, W.W., Chong, C.F., Chow, K.P., Hui, L.C.K. and Tso, C.W.

    The collision test is an important statistical test for rejecting poor random number generators. The test simulates the throwing of balls randomly into urns. A problem in applying this test is to determine the number of urns, m, and the number of balls, n, so that the test is among the most powerful possible on a computer. The problem was tackled empirically. A set of canonical congruential generators with increasing periods was first implemented. The stringency of a test against congruential generators is measured as the number of canonical generators the test rejects. Experiments were then conducted to measure the stringencies of the collision tests for various (m, n) values. The results reveal that for a fixed m, the stringency of a test reaches maximum when m < n � 2m. Moreover, the stringency increases as m increases. Similar results were observed when the experiments were repeated on lagged Fibonacci generators and on shift-register generators. Further investigation showed that the variance of the number of collisions reaches maximum together with the stringencies, at n = |_1.256431m_| . Eighteen well-known generators were tested against the collision tests with m = , , �, up to . Many generators failed starting from some points along the way, including congruential generators, shift-register generators, lagged Fibonacci generators of lags less than 40, subtract-with-borrow generators of lags less than 24, and a combined generator.
Cite as: Tsang, W.W., Chong, C.F., Chow, K.P., Hui, L.C.K. and Tso, C.W. (2004). Tuning the Collision Test for Power. In Proc. Twenty-Seventh Australasian Computer Science Conference (ACSC2004), Dunedin, New Zealand. CRPIT, 26. Estivill-Castro, V., Ed. ACS. 23-30.
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS
 

 

ACS Logo© Copyright Australian Computer Society Inc. 2001-2014.
Comments should be sent to the webmaster at crpit@scem.uws.edu.au.
This page last updated 16 Nov 2007