Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

New Empirical Test to the Goodness of Random Integer Generators

IP.com Disclosure Number: IPCOM000042751D
Original Publication Date: 1984-Jun-01
Included in the Prior Art Database: 2005-Feb-04
Document File: 3 page(s) / 28K

Publishing Venue

IBM

Related People

Savir, J: AUTHOR

Abstract

This publication describes a compact inexpensive empirical test for the goodness of random integer generators. Several empirical tests for the goodness of random integer (or number) generators have been proposed over the years *. The reason for doing it is that all the generators do not generate "true" random integers, but pseudo random integers. The question then arises as to how good an approximation is the pseudo random sequence to the true random one. In other words, are the integers generated really equally likely? To name a few empirical tests proposed in the past: 1. The frequency test 2. The serial test 3. The gap test 4. The coupon collector test 5. The permutation test 6. The ran test.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 3

New Empirical Test to the Goodness of Random Integer Generators

This publication describes a compact inexpensive empirical test for the goodness of random integer generators. Several empirical tests for the goodness of random integer (or number) generators have been proposed over the years *. The reason for doing it is that all the generators do not generate "true" random integers, but pseudo random integers. The question then arises as to how good an approximation is the pseudo random sequence to the true random one. In other words, are the integers generated really equally likely? To name a few empirical tests proposed in the past: 1. The frequency test 2. The serial test 3. The gap test 4. The coupon collector test 5. The permutation test 6. The ran test. The unique thing about those tests is that they examine the sequence of integers, and their digit representation, as they appear when generated. In this article we take a different approach. Rather than examining the sequence of integers generated and evaluating their goodness, we first compress the data of the generated sequence to a new number and only then evaluate the goodness of this number. The benefit of doing that is the ability to generate long sequences fast and evaluate only the final compressed result. The Basic Idea To ease the explanation, let us use the roll function in the APL language. Suppose we try ?10. The computer will respond with an integer, randomly generated between 1 and 10. Let the response be 6. As a second trial, let us request ?6, namely a number between 1 and 6. Suppose the answer is
3. As a third trial, request ?3; the computer responds with 1. In other words, if we keep generating numbers in the form ??...?N the result should eventually become 1. If the sequence generated by the pseudo integers generator is truly selected from a uniform distribution, then the statistics of empirical tests of that kind must be close to those that may be computed. By testing how close the empirical results are to the expected ones, one can determine whether or not the random integer generator is a good one. The Empirical Test Description Choose an integer N. Select a pseudo random integer between 1 and N, and call it X1; select a pseudo random integer between 1 and X1, and call it X2 . Continue this process m times. At the end of the experiment you are left with a number, say, Xm<_N. Repeat this experiment k times, each time recording the final number Xm. Average over all these outcomes, and call it X. Check whether or not X falls within a 95% confidence interval around its expected value. If it does, then it is a good random integer generator. Note that in order to insure a meaningful result to the outcome of the experiment, one should test for X for about 100 times and see whether or not its value falls out o...