Abstracting Psuedorandom Number Generators
Advisor(s): Paolo Bucci
Participants: Matthew Thornton
Start Date: Autumn Quarter 2001
Project Status: Active
Index:
Abstract:
Pseudo Random Number Generators (PRNGs) play an important role in
computer science and mathematics in testing,
sampling, and cryptography. Other branches of
the sciences and the humanities use them in
various applications such as simulations. PRNGs
are built on algorithms that generate sequences
of random numbers with desirable statistical
properties. While random number algorithms have
been extensively researched, relatively little
attention has been given to how to describe a
general abstraction for PRNGs that describe the
properties and functions of as many Pseudo
Random Number Generators as possible and
supports most (if not all) applications of
PRNGs.
This research involves the creation of a general
abstraction of a pseudo random number generator
that can be shown to model the traits all good
PRNGs demonstrate. The abstraction includes a
mathematical model that generalizes the behavior
of most PRNGs, so that implementers have
sufficient freedom to create a PRNG tailored to
a client's needs. It also includes a
description of all of the necessary operations
for a client to manipulate objects of this
type.
The model and the set of operations must provide a minimal but
complete abstraction, which can be applied to a
variety of situations and, if necessary, can be
extended to support future applications.
To accomplish this goal, the abstraction will be
created using the RESOLVE philosophy. RESOLVE
is a software design framework using C++ as a
backend that requires strict attention to
specifications and software engineering
principles. It includes a robust mathematical
specification language, and a set of principles
and guidelines that will guide the design of the
new abstraction.
Calendar:
October 2001--Project Begins.
November 2001--Begin research of random numbers, finding a concrete
definition of randomness, pseudorandomness.
December 2001--"Rough Draft" of AI/Random_Number/Type.h and the
abstract operations.
January 2002-March 2002--Reading scholarly works on random number
generator algorithms in an attempt to find
generalities in the algorithms.
March 2002-Ongoing--Continuing to iron out the abstraction, and
demonstrating its correctness with the
implementiaton of concrete_instances of
the Random_Number object.
Project Development:
This is a scratch pad of my progress. If anyone has any ideas, please
let me know.
At first, I planned on
creating the mathematical model of Random
Numbers. However, as my readings
progressed, it turns out that it may be
easier and make more logical sense to
start with creating an implementation of
random number and then create the math
model.
However, I've realized now
that this is a trivial exercise and
doesn't really answer the question
of how random numbers can be defined
on a computer. Back to the Math
Model.
I was originally
trying to create a mathematical
definition that would use number
theory to describe the
characteristics of random
numbers. However, this will not
work because it doesn't take
into account random sequences
that would not be useful in an
application. (all 1's, for
example, is theoretically
random, but not particularly
useful) Now I am looking for
ways of describing a sequence
statistically; a looser
definition, true, but more
useful for the purposes of this
random number
generator.
I have written
a Concrete Instance Class of
a random number generator.
The problem here is that a
Concrete Instance class
locks in the specific types
of algorithms that can be
used based on the
definition.
My
problem right now is how
to generalize the tests
used to prove a sequence
of numbers is random,
but I am realizing now
that it may be easier to
look at it in terms of
what you can say about
the sequence of numbers,
rather than a sequence
"passes" or "fails" one
of several tests. In
other words, you need to
look at what
applications a PRNG
would be used for.
There are many different
"flavors" of
PRNG's.
I have finished a "final" draft of the Random_Number object and its
specifications. I
am not entirely
happy with it, but
it does provide a
better understanding
of the Properties of
a PRNG than the
informal comment in
the current
specification.
Using probability as
part of the argument
isn't good as it is
impossible to prove
that a PRNG
algorithm is
correct.
Findings and Contributions:
A great deal of the abstraction still relies on
implementation-specific values, including
the specific period length of the
algorithm, the tests of correctness that
were provided, the maximum value, and the
algorithm used to generate the next
value. However, given this data, the
client is able to understand completely
what he can expect from the
object.
The problem of using probability in
the model is troublesome from the
standpoint of being able to prove an
algorithm is truly pseudorandom, but
from a client standpoint, it makes
sense since he just wants to know what
he can expect about the next value
generated.
Another issue that needs to be
looked into is the issue of
performance. PRNG's should be
fast and not including this
specification could result in some
potentially slow implementations.
As this field is further examined,
performance may be introduced into
the abstraction. A paper written
recently by Dr. Ogden on performance
specification may shed light on
how to do this for object-oriented
software.
This project is, obviously,
incomplete, and while I am not
finished working on it, I am
not committing all of my time
to it like I have. I invite
anyone who is interested in
component design or
abstraction to look at what I
have worked on and expand on
it or revise it in any way you
see fit.
Links and References:
Return to Europa
Matthew Thornton <thornton.124@osu.edu>
Last modified: Fri Feb 14 23:10:04 EST 2003
Abstract