How do computers, which are completely deterministic devices, generate random numbers?

HOW COMPUTERS GENERATE RANDOM NUMBERS


by

David W. Deley

1991



INTRODUCTION

Many computer programming languages today include a function for generating random numbers. For example, the C programming language includes a function named rand() as a standard part of its language. Supposedly once you get the generator going by giving it a "seed" value then all you have to do is call it repeatedly and it will give you a "random" number every time. But how is it that computers, which are completely deterministic machines, can generate "random" numbers?

This paper presents some background theory in basic probability theory and inferential statistics. We then present a number of empirical tests for analyzing a computer generated sequence of random numbers, and we apply these tests to several popular random number generators.


CONTENTS:

INTRODUCTION

1.0  PROBABILITY THEORY
1.1ROLLING DIE
1.2THE LANGUAGE OF PROBABILITY

2.0INFERENTIAL STATISTICS
2.1THE PROBABILITY OF ERROR
2.2GENERAL TEST PROCEDURE
2.3THE CHI-SQUARE TEST
2.42.4 THE KOLMOGOROV-SMIRNOV TEST

3.0ANALYSIS OF A SEQUENCE OF RANDOM NUMBERS
3.1ONE-DIMENSIONAL TESTS
3.2TWO-DIMENSIONAL TESTS
3.3THREE-DIMENSIONAL TESTS
3.4HIGHER DIMENSIONAL TESTS

4.0LINEAR CONGRUENTIAL RANDOM NUMBER GENERATORS
4.1GENERATORS TESTED FOR THIS REPORT AND THEIR DEFINITION
4.2GENERAL FORMAT OF LINEAR CONGRUENTIAL RANDOM NUMBER GENERATORS
4.3THE MTH$RANDOM ALGORITHM
4.4THE RANDU ALGORITHM
4.5STARTING THE MTH$RANDOM GENERATOR
4.6STARTING THE RANDU GENERATOR
4.7STARTING THE ANSI C GENERATOR

5.0RATINGS FOR VARIOUS GENERATORS
5.1REVIEW OF TESTS PERFORMED
5.1.4THE 1-D TEST
5.1.4THE 2-D TEST
5.1.4THE 3-D TEST
5.1.4THE 4-D TEST
5.2 TEST RESULTS
5.2.1MTH$RANDOM
5.2.2RANDU
5.2.3C and ANSI C
5.2.4Microsoft C
5.2.5Turbo Pascal
5.3Why did they all fail after 1-10 million iterations?

6.0THE SPECTRAL TEST

7.0SHUFFLING

8.0DES AS A RANDOM NUMBER GENERATOR

9.0HOW GOOD A RANDOM GENERATOR DO YOU NEED?

10.0WHAT IS A RANDOM NUMBER GENERATOR?

11.0THE RANDOM SEUQUENCE {1, 1, 1, 1,... 1} (added September 2003)

CONCLUSION

SAMPLE PARADOXES OF PROBABILITY
The Monty Hall 3 Door Problem
Simpson's Paradox
The Three-Card Game
The Child Paradox
Which is safer? Flying vs. Automobile?
How to Make 44 a Majority of 140
ANSWERS
     Further analysis of Child Paradox question 3new (added October 2006)
     Further analysis of Child Paradox question 4new (added October 2006)

GENERATING RANDOM INTEGERS WITHIN A DESIRED RANGE

Using the C OR C++ rand() function

Additive Random Number Generators (Updated December 2007)

The Structure of Language

SOURCE CODE FOR PROGRAMMERS who wish to test the randomness of a random number generator

SOURCE CODE AND DISCUSSION OF NEWER & BETTER RANDOM NUMBER GENERATORSnew2a (added May 2005)

LINKS FOR FURTHER RESEARCH

REFERENCES




Begin the adventure!

Index

Back to DELEY'S home page


mailbox email David Deley: deleyd@ieee.org