|
|
Boost : |
From: jeetsukumaran_at_[hidden]
Date: 1999-11-06 12:44:09
Ok people.
Based on suggestions made by Beman Dawes, as well as others on this
list, as well as looking around at some of the other PRNG libraries
available on the net, as well as sitting down with a pencil, paper,
cigarettes and coffee ...
... here is one possible scheme for the random number generator library
that I would like some feedback on.
1. There will be an abstract base class (protocol class) that shall
define the interface through which all random number requests by client
code are made. I've included a proposal of such a base class, called
"random_number" below.
2. From this base class, various template classes shall be derived.
Each template class is parameterized on "Generator," which can be any
type that fulfills certain minimum requirements:
(a) it must have a constructor that can take a single unsigned integer
as an argument, either directly or through conversion, and must use
this value to seed or set up the pseudo-random number generation
algorithm.
(b) it must provide an operator()(void) that, when invoked, returns a
UNIFORMLY DISTRIBUTED RANDOM integer.
3. Different template classes will apply different transformations to
the numbers generated by the uniform PRNG classes with which they are
instantiated to provide numbers of different distributions, such as
normal, gaussian, poisson etc.. The methods of each class shall then
map the final, correctly transformed, values so as to the range and
type that is expected from the methods.
As an illustration we can imagine the (hypothetical at the present
time) poisson_distribution template. In its implementation of each of
the methods of random_number's interface, it first pulls the next
number in the sequence by invoking its contained uniform PRNG object.
It then applies the transformation to suitably weight the number so
that the potential sequence falls into a poisson distribution, and then
further converts the number to the type and range to the return value
promised by the method. If the method promised a real in the range of
[0,1], for example, the transformed/weighted number is converted to
that type and range (hopefully without losing any of its desired
properties). If the value requested is an integer between 0 and a
user-specified limit, the transformed/weighted number is mapped onto
this. And so on. The same case applies with the (also hypothetical at
this time) gaussian_distribution class, except here the
transformation/weighting is, of course, designed to give the number
sequence a gaussian distribution -- the mapping to a requested
range/type is identical.
An example/proposal of a template in this line is given below. This,
"uniform_deviate," promises a uniform distribution, so it does not
apply any transformation to the output of the PRNG (or, another way of
looking at it -- it implements a null transfornation). It still maps
this output, however, to the appropriate ranges/types needed by each
method.
I think that this scheme is very flexible. It provides a common
interface to a wide range of combinations of PRNG algorithms, random
number distributions generated via these algorithms, and ranges and
types of return values. The scheme, in fact, seems to approach the
orthogonal decomposition of the STL -- we can vary PRNG algorithms
(through the generator classes we pass to the templates), random number
distributions (through the template implentations) and return
values/ranges (through the particular interface function invoked)
independently of each other. We can get reals in [-1,1] with a
gaussian distribution and generated by the R250 algorithm. We can get
integers in (0, 10) with a normal distribution, generated by the
MT19937B algorithm.
Mix and match to our delight!
To add a new PRNG algorithm, we just have to write the class
implementing it, or modify an existing class to provide the operator()
and constructor as specified above. To add a new distribution, a
template with the needed transformations in its methods can be written.
And so on. In each case, a change in one aspect does not entail a
change in any other part of the library. Of course, if we add a new
random number request type (e.g. an integer between two values, or a
random character etc..), then all the templates that implement the
abstract base class have to be changed.
Furthermore, we have achieved dynamic as well as static polymorphism.
A function that requires random numbers can have a reference argument
to "random_number." Calling code can pass ANY combination of PRNG
algorithm and distribution transformation to this function. We can
invoke this function by passing it an object that returns random
numbers in a poisson distribution obtained via the Mersenne Twister at
one point, and the next invoke it again with an object that returns
random numbers in a uniform distribution with the Mother algorithm. In
both cases, the function will only be dealing through the common
interface declared in "random_number," so it will know how to get the
numbers of the types and ranges it desires, but we can control the
properites of the numbers it gets.
I am aware of many problems with this scheme. I am aware that there
are probably many more that I am NOT aware of. That's why I've
submitted this proposal to this list.
Here are some of the most salient problems:
(1) The classes pass a single non-zero positive integer to the
constructors of the uniform PRNG objects to seed them. However,
different PRNG algorithms have different requirements. Some require
negative numbers. Some require two or more seeds. Some require
several seeds, with specific ranges and properties for each seed (e.g.
odd values between xxx and xxx). This needs to be catered for. Right
now, the best that I can think of is adapters, either built-in to the
constructors of the PRNG classes, or entire adapter classes wrapped
around the PRNG classes.
(2) Also, the PRNG objects are seeded once during construction. In its
present incarnation, there is no room for resetting the PRNG objects,
or reseeding them with different seeds. This can be handled by adding
the appropriate methods in the protocol base class, but it will require
further specifications to be fulfilled by our PRNG classes -- e.g. the
definition of a function reseed(n) or reset().
(3) At present, I have assumed 32-bit integers as the universal
currency. This need not be the case. Before long we can be talking
about 64-bit integers, and PRNG's that generate this. Both
"random_number" and "uniform_deviate" below allow for easy changes to
this since everything has been typedef'd. But I don't think that this
is enough. I think that the library classes should be able to handle
different data representations and ranges from their PRNG's, both
dynamically and statically. I propose the class generator_traits to
take care of this. Each and every PRNG class will have to define their
generator_traits, which will specify typedef's for the type of number
returned, as well as max values, min values, appropriate ratios to
divide to obtain 0-1 ranges etc.. More information on this is in the
comments in my "uniform_deviate" class below.
(4) Ok. I know that the names that I have chosen for the
"random_number" interface is NOT the best. uint(), sint(), ureal(),
sreal() etc.. Somewhat cryptic. The problem is that I am used to
coding longAndDescriptiveNames like this, and the C++ Standard Library
type names require a little different way of thinking. I am sure that
you will all be quite forthcoming on suggestions for the methods.
I look forward to criticisms, critiques or feedback of any other sort.
How practical/workable is this design? How can it be improved? Or
does it need to be ditched altogether? What complications might arise?
In what way is portability compromised (I'm actually worried about the
32-bit requirement for the numbers -- it's not guaranteed by the
standard, is it)? What methods need to be added to the interface?
What methods need to be removed?
-- jeet sukumaran (jeetsukumaran_at_[hidden])
p.s. I hope that this time the copyrights and such are to everyone's
liking.
p.p.s. I have not thoroughly debugged the code below (i.e. testing it a
million times under all the expected or unexpected but imaginable
situations), but that is ok, because it is not meant as a release code
or anything (yet).
//- random_number.hpp --------------------------------------------- //
/**
* random_number.hpp
*
* Declaration of the abstract base (protocol) class
* random_number.
*
* (C) Copyright 1999 Jeet Sukumaran. Permission to copy, use, modify,
* sell and distribute this software is granted provided this
* copyright notice appears in all copies. This software is provided
* "as is" without express or impliedwarranty, and with no claim as
* to its suitability for any purpose.
*/
#ifndef BOOST_RANDOMNUMBER_H
#define BOOST_RANDOMNUMBER_H
// #include "cstdint.hpp"
namespace boost {
/**
* This class provides a common set of protocols for requesting
* random variate of different types, properties and ranges.The
* interface that this class specifies can be implemented by
* different generators, whether those returning a uniform
* distribution or a weighted one.
*
* @author Jeet Sukumaran (jeetsukumaran_at_[hidden])
* @date November 7 1999
*/
class random_number {
public:
// temporary hack: will be replaced by cstdint types
// when ready ...
// I want to be able this class to handle 64-bit
// numbers if required
typedef unsigned long uinteger_t;
typedef signed long sinteger_t;
typedef double real_t;
public:
///////////////////////
// virtual destructor
virtual ~random_number(void) { }
///////////////////////////
// random number requests
// 0 <= i <= 2^32-1, i: integer
virtual uinteger_t uint(void) = 0;
// 0 <= i < n, i: integer
virtual uinteger_t uint(uinteger_t n) = 0;
// 2^31-1 <= i <= 2^31-1, i: integer
virtual sinteger_t sint(void) = 0;
// 0.0 <= r <= 1.0, r: real
virtual real_t ureal(void) = 0;
// -1 <= r <= 1
virtual real_t sreal(void) = 0;
// STL "Generator" and "RandomNumberGenerator" conformance
// 0 <= i <= 2^32-1
virtual uinteger_t operator()(void) = 0;
// 0 <= i < n
virtual uinteger_t operator()(uinteger_t n) = 0;
}; // random_number
} // namespace boost
#endif // #ifndef BOOST_RANDOMNUNBER_H
//-- uniform_deviate.hpp -------------------------------------//
/**
* uniform_deviate.hpp
*
* Declaration/definition of template class implementing a uniform
* random number generator.
*
* (C) Copyright 1999 Jeet Sukumaran. Permission to copy, use, modify,
* sell and distribute this software is granted provided this
* copyright notice appears in all copies. This software is provided
* "as is" without express or impliedwarranty, and with no claim as
* to its suitability for any purpose.
*/
#ifndef BOOST_UNIFORMDEVIATE_H
#define BOOST_UNIFORMDEVIATE_H
// Standard C Library
#include <ctime>
#include <stdlib>
#include "random_number.hpp" // base class
namespace boost {
/**
* Generic uniformly distributed random number class.
*
* This is a generic class derived from random_number, that
* is designed to encapsulate the generation of random numbers
* of uniform distribution in a variety of formats and ranges.
* It is instantiated by being passed a uniform random number
* function object class ("Generator") as a parameter.
*
* The result will be a shallow hierarchy of uniform random
* variate classes (thanks to the common derivation from
* random_number), each implementing a different algorithm,
* or even with different implementations of the same algorith,
* that can be used interchangably -- thus we get dynamic as
* well as static (through the template) polymorphism.
*
* Minimal requirements for Generator are:
*
* - Constructor takes unsigned integer value as an argument,
* and uses it to seed/setup the number generation algorithm;
* In general, different PRNG algorithms vary in their
* requirements for the seed: some require non-zero values,
* some require odd values, some require several different
* values in different ranges. Given the current design,
* it is difficult to cater to all these. Currently the
* template can promise a NON-ZERO 32-BIT UNSIGNED VALUE
* will be passed to this constructor, If this is
* unacceptable, or insufficient, then an adapter function,
* or some degree of "hackery" in Generator's constructor,
* is required to convert the non-zero 32-bit value into
* an acceptable or set of acceptable seeds. I think that
* this is the biggest weakness of my design.
*
* - Operator() with no arguments returns unsigned random
* integer value:
* When its operator() is invoked with no arguments,then
* Generator must return a 32-BIT UNSIGNED VALUE or a value
* that is otherwise convertable to it. This restriction
* may be dropped in the future with the implementation of
* the generator_traits class, which will provide the
* transformation classes (such as this is) with the
* information required to correctly convert the generator
* output to the ranges and values requested by the
* client code.
*
* @author Jeet Sukumaran (jeetsukumaran_at_[hidden])
* @date Nov 7 1999
*/
template <typename Generator>
class uniform_deviate : public random_number {
public:
// lifecycle & assignment
uniform_deviate(void);
explicit uniform_deviate(uinteger_t seed);
uniform_deviate(const uniform_deviate& rhs);
uniform_deviate& operator=(const uniform_deviate& rhs);
virtual ~uniform_deviate(void);
// random number requests
virtual uinteger_t uint(void);
virtual uinteger_t uint(uinteger_t n);
virtual sinteger_t sint(void);
virtual real_t ureal(void);
virtual real_t sreal(void);
// STL "Generator" and "RandomNumberGenerator" conformance
virtual uinteger_t operator()(void);
virtual uinteger_t operator()(uinteger_t n);
protected:
// returns random seed
virtual uinteger_t auto_seed(void);
// At present, we assume that all and any random number
// generator passed to us will return 32-bit unsigned
// integers when invoked. This need not be the case. When
// standards have settled somewhat, we can look to a
// generator_traits class that will define the appropriate
// types and values for each generator, or groups of
// generators. Then, we will rely on the generator_traits
// class for each specific generator to provide the typedef
// and value below. Until then, we code it this way ...
// Note that rand_max is defined in the implementation
// section
typedef uinteger_t randnum_t;
static const randnum_t rand_max;
// Numbers used to manipulate the output of the prng.
// Defined in the implementation section.
static const uinteger_t uint_div;
static const uinteger_t sint_div;
private:
Generator prng_;
}; // uniform_deviate
} // namespace boost
// Until export is provided:
namespace boost {
////////////////////////////////////////////////////////////////
// type and value definitions
// These values are used to parse/manipulate the generator
// output and transform them to the ranges and types promised
// by our random number protocols.
// Right now, we assume 32-bit integers are the universal
// value sizes generated by whatever prng functor is passed to
// us.
// Down the road, we will use a generator_traits class, defined
// for each generator class (or groups of classes), that we can
// depend on to provide these values and types.
template <typename Generator>
const uniform_deviate<Generator>::randnum_t
uniform_deviate<Generator>::rand_max = 0xffffffff;
template <typename Generator>
const uniform_deviate<Generator>::uinteger_t
uniform_deviate<Generator>::uint_div = rand_max;
template <typename Generator>
const uniform_deviate<Generator>::uinteger_t
uniform_deviate<Generator>::sint_div = rand_max/2;
////////////////////////////////////////////////////////////////
// lifecycle & assignment
/**
* Default constructor.
*
* Constructs a uniform deviate prng using Generator seeded
* with an auto-supplied value.
*/
template<typename Generator>
uniform_deviate<Generator>::uniform_deviate(void)
: prng_(this->auto_seed()) {
} // default constructor
/**
* Seeded constructor.
*
* Constructs a uniform deviate prng using Generator seeded with
* a user-supplied value.
*
* @param seed requirements vary from generator to
* generator
*/
template<typename Generator>
uniform_deviate<Generator>::uniform_deviate(uinteger_t seed)
: prng_(seed) {
} // constructor wit seed
/**
* Copy constructor.
*
* The default member-wise copy constructor should do well
* enough. This is just a developmental stub that does the
* same thing.
*
* @param rhs object to be copied
*/
template<typename Generator>
uniform_deviate<Generator>::uniform_deviate(const uniform_deviate&
rhs)
: prng_(rhs.prng_) {
} // copy constructor
/**
* Assignment operator.
*
* As with the copy constructor, the default is quite usable.
* Probably delete this if still unrequired at the end of
* development.
*/
template<typename Generator>
uniform_deviate<Generator>&
uniform_deviate<Generator>::operator=(const uniform_deviate& rhs) {
this->prng_ = rhs.prng_;
return *this;
}
/**
* Virtual destructor.
*
* Doesn't do very much.
*/
template<typename Generator>
uniform_deviate<Generator>::~uniform_deviate(void) {
} // destructor
/**
* Generates autoseed value.
*
* This uses the implementation random number generator (usually
* a bad linear congruential generator) to pull a non-zero
* 32-bit integer value to be used as a generator seed value.
*
* @return random non-zero unsigned 32-bit integer
*/
template<typename Generator>
uniform_deviate<Generator>::uinteger_t
uniform_deviate<Generator>::auto_seed(void) {
uinteger_t s;
std::srand( std::time(NULL) );
while ( (s = std::rand()) == 0 ); // while zero
return s;
} // operator(n)
////////////////////////////////////////////////////////////////
// random number requests
/**
* Returns a uniform integer variate in [0, 2^32-1] -- i.e. the
* direct output of a 32-bit pseudo-random number generator.
*
* @return 0 <= i <= 2^32-1, i: integer
*/
template<typename Generator>
uniform_deviate<Generator>::uinteger_t
uniform_deviate<Generator>::uint(void) {
return this->prng_();
} // uint
/**
* Returns a uniform integer variate in [0, n) -- i.e. the
* output of the psuedo-random number generator, suitably
* parsed.
*
* @param upper-bound, non-inclusive, of the range of
* possible values to be returned
* @return 0 <= i < n, i: integer
*/
template<typename Generator>
uniform_deviate<Generator>::uinteger_t
uniform_deviate<Generator>::uint(uinteger_t n) {
// Taking the modulus of the output may seem like
// an easy way to achieve this, but it is strongly
// discouraged -- the lower bits of numbers generated
// by most prng's are usually weak, and since these
// are the bits the modulus retrieves, we find that
// the "randomness" is destroyed; this applies
// particularly severely to linear congruential
// generators, which usually have horrble low-bit
// "randomness"
// So we use division to retrieve the high-bits ...
// Here though, we must check to see if the maximum value
// is returned, since if it does, we must reject it and
// select another, otherwise our algorithm will obtain
// n .. which is outside of the promised range ...
// Note that the odds of returning a maximum value is 1 in
// 2^32-1 for a 32-bit prng.
uinteger_t i;
while ( (i=this->prng_()) == uint_div );
return uinteger_t( (real_t(i) / uint_div) * n );
} // uint(n)
/**
* Returns a uniform integer variate in [-2^31-1, 2^31-1] --
* i.e., basically a 32-bit unsigned value
*
* @return -2^31-1 <= i <= 2^32-1
*/
template<typename Generator>
uniform_deviate<Generator>::sinteger_t
uniform_deviate<Generator>::sint(void) {
return sinteger_t(this->prng_());
} // sint
/**
* Returns a uniform real variate in the range of [0.0, 1.0],
* i.e. from 0.0 to 1.0, inclusive of the endpoints.
*
* return 0.0 <= r <= 1.0, r: real
*/
template<typename Generator>
uniform_deviate<Generator>::real_t
uniform_deviate<Generator>::ureal(void) {
return real_t(this->prng_()) / uint_div;
} // ureal
/**
* Returns a uniform real variate in the range of [-1.0, 1.0],
* i.e. from -1.0 to 1.0, inclusive of the endpoints.
*
* return -1.0 <= r <= 1.0, r: real
*/
template<typename Generator>
uniform_deviate<Generator>::real_t
uniform_deviate<Generator>::sreal(void) {
return real_t( sinteger_t(this->prng_()) ) / sint_div;
} // sreal
/**
* Returns a uniform 32-bit integer variate in [0, 2^32-1].
*
* Basically reduplicates the functionality of uint(), but with
* a signature that conforms to the STL "Generator"
* requirement.
*
* @return 0 <= i <= 2^32-1, i: integer
*/
template<typename Generator>
uniform_deviate<Generator>::uinteger_t
uniform_deviate<Generator>::operator()(void) {
return this->prng_();
} // operator()
/**
* Returns a uniform 32-bit integer variate in [0, n)
*
* As with operator()(void), this, too, duplicates the
* functionality of an existing method (only this time it
* is unit(n)), but with a signature that conforms to the
* STL "RandomNumberGenerator" requirement.
*
* @param upper-bound, non-inclusive, of the range of
* possible values to be returned
* @return 0 <= i < n, i: integer
*/
template<typename Generator>
uniform_deviate<Generator>::uinteger_t
uniform_deviate<Generator>::operator()(uinteger_t n) {
// copied from uint(n) ...
// Taking the modulus of the output may seem like
// an easy way to achieve this, but it is strongly
// discouraged -- the lower bits of numbers generated
// by most prng's are usually weak, and since these
// are the bits the modulus retrieves, we find that
// the "randomness" is destroyed; this applies
// particularly severely to linear congruential
// generators, which usually have horrble low-bit
// "randomness"
// So we use division to retrieve the high-bits ...
// Here though, we must check to see if the maximum value
// is returned, since if it does, we must reject it and
// select another, otherwise our algorithm will obtain
// n .. which is outside of the promised range ...
// Note that the odds of returning a maximum value is 1 in
// 2^32-1 for a 32-bit prng.
uinteger_t i;
while ( (i=this->prng_()) == uint_div );
return uinteger_t( (real_t(i) / uint_div) * n );
} // operator(n)
} // namespace
#endif // #ifndef BOOST_UNIFORMDEVIATE_H
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk