Random Number Generator


Category: functors 
Component type: concept 
Description
A Random Number Generator is a function object that can be used to
generate a random sequence of integers. That is: if f is a Random
Number Generator and N is a positive integer, then f(N) will return
an integer less than N and greater than or equal to 0. If f is
called many times with the same value of N, it will yield a sequence
of numbers that is uniformly distributed [1] in the range [0, N). [2]
Refinement of
Unary Function
Associated types
Argument type

The type of the Random Number Generator's argument. This must
be an integral type.

Result type

The type returned when the Random Number Generator is called. It must
be the same as the argument type.

Notation
F

A type that is a model of Random Number Generator.

Integer

The argument type of F.

f

Object of type F.

N

Object of type Integer

Definitions
The domain of a Random Number Generator (i.e. the set
of permissible values for its argument) is the set of numbers that are
greater than zero and less than some maximum value.
The range of a Random Number Generator is the set of nonnegative
integers that are less than the Random Number Generator's argument.
Valid expressions
None, except for those defined by Unary Function.
Expression semantics
Name

Expression

Precondition

Semantics

Postcondition

Function call

f(N)

N is positive.

Returns a pseudorandom number of type Integer. [2]

The return value is less than N, and greater than or equal to 0.

Complexity guarantees
Invariants
Uniformity

In the limit as f is called many times with the same argument
N, every integer in the range [0, N) will appear an equal number
of times.

Models
Notes
[1]
Uniform distribution means that all of the numbers in the range
[0, N) appear with equal frequency. Or, to put it differently,
the probability for obtaining any particular value is 1/N.
[2]
Random number generators are a very subtle subject: a good random
number generator must satisfy many statistical properties beyond
uniform distribution. See section 3.4 of Knuth for a discussion of
what it means for a sequence to be random, and section 3.2 for several
algorithms that may be used to write random number generators.
(D. E. Knuth, The Art of Computer
Programming. Volume 2: Seminumerical Algorithms, second edition.
AddisonWesley, 1981.)
See also
Copyright ©
1996 Silicon Graphics, Inc. All Rights Reserved.
TrademarkInformation