Accession Number:

AD0689295

Title:

REGULARITIES IN CONGRUENTIAL RANDOM NUMBER GENERATORS

Descriptive Note:

Corporate Author:

BOEING SCIENTIFIC RESEARCH LABS SEATTLE WA MATHEMATICS RESEARCH LAB

Personal Author(s):

Report Date:

1969-05-01

Pagination or Media Count:

8.0

Abstract:

The paper suggests that points in n-space produced by congruential random number generators are too regular for general Monte Carlo use. Regularity was established previously for multiplicative congruential generators by showing that all the points fall in sets of relatively few parallel hyperplanes. The existence of many containing sets of parallel hyperplanes was easily established, but proof that the number of hyperplanes was small required a result of Minkowski from the geometry of numbers--a symmetric, convex set of volume 2 to the nth power must contain at least two points with integral coordinates. The present paper takes a different approach to establishing the course lattice structure of congruential generators. It gives a simple, selfcontained proof that points in n-space produced by the general congruential generator r sub i1 is identically equal to ar sub i b mod m must fall on a lattice with unit-cell volume at least m to the power n-1. There is no restriction on a or b this means that all congruential random number generators must be considered unsatisfactory in terms of lattices containing the points they produce, for a good generator of random integers should have an n-lattice with unit-cell volume 1.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE