[boost] Re: Boost Random Number Library Framework Proposal

From: jeetsukumaran_at_[hidden]
Date: 1999-11-09 04:59:51

Ok.  The general consensus seems to be against rooting the user-end
classes in an abstract base class, due to the loss of efficiency
involved in the invocation of virtual functions.  The feeling is that
the user-end classes should be either requirements or templates or
both. Going with the latter, here is one revision of the scheme ...

We have a generic class "random_number" (version 2!) that is
parameterized on Generator, and is the end-user class.  Its
responsibility is solely to map the output of Generator into the ranges
and types requested by the user (no transformation/weighting applied). 
Thus it will have methods such as uint(), sint() etc. (or whatever
better names/signatures are ultimately decided upon), which simply
invoke the Generator -- using an object that is contained by value in
"random_number" -- and map it appropriately.  In this respect, the new
"random_number" can be seen as simply a renaming of the old
"uniform_deviate."   

The various distributions that might be required -- normal, uniform
etc. -- will be the responsibility of the Generator that is passed to
"random_number" as a parameter.  What we will do is to provide a set of
template classes, such as "poisson_distribution", "normal_distribution"
and so on, that take a Generator type as their parameter, and have the
responsibility of weighting its PRNG output to fall within their
promised distributions.  These transforming function object template
classes shall themselves conform to the Generator requirement, and
hence can be passed to random_number as a parameter.

So, for example, given a Generator-conforming class that implements the
R250 PRNG, "random_R250" --

// instantiates a random number generator object that returns uniformly
// distributed numbers
random_number<random_R250>  uniform_r250;  

// instantiates a random number generator object that returns normally 
// distributed numbers
random_number< normal_distribution<random_R250> > normal_r250;

// instantiates a PRNG weighted normally -- user is not interested in
// the mapping services provided by random_number, and is happy getting
// whatever operator() of the below object spits out
normal_distribution<random_250>  raw_normal_r250;

So, this way, client code can deal with the same interface all (or most
of the) time, i.e. "random_number," and the user is allowed to control
the algorithm and the distribution properties of the random number
sequence.

Jens Maurer raised some very good points.  Most important I think, was
the issue of polymorphism and the STL -- if I read you right, because
the STL takes the RandomNumberGenerator argument by value, if (assuming
that we had implemented the library as an inheritance hierarchy, as in
the original scheme) a function receives a random number object as a
base-class reference/pointer, then calls the STL algorithm with it, our
code will fail.  I believe that this is the most damning point against
my original scheme.  Full-integeration and cooperation with the STL --
and, for that matter, the entire C++ library -- should be a fundamental
design objective.  Of course, we could simply point out that users
should not passed base-class references or pointers to STL algorithms
... but this is unsatisfactory -- and I feel that this point alone is
enough to require rejection of my original scheme.

Another important point was the issue of the return values of the
distributions -- these may not fall neatly into ranges that are easily
mappable to the ranges promised by random_number.  For example, as he
points out, gaussian_distribution sits on +/- infinity.   Well, in that
case, I suppose, given the revised scheme outlined above, if the user
desired a gaussian distribution, they could simply use
"gaussian_distribution<random_250>" (for example).  I am not sure
exactly what will happen if the user tries to instantiate
"random_number" with this type.  It will depend on the sophistication
of the implementation of generator_traits and the capability of
"random_number" in handling extreme or exceptional cases.  For now, let
us just say it is illegal?

Regarding what should be the default return value of the PRNG,
throughout I have assumed that it would be an integer, most likely
32-bit.  My PERSONAL preference, though, would be for a real, either in
[0,1] or [0,1).  I find these ranges far more useful in far more
contexts than the straight 32-bit integer.  Furthurmore, given the
unsuitability of the modulus technique to map the PRNG integer output
onto a certain range, this means that virtually all random number
requests, except those that request a 32-bit integer directly, will
first map the PRNG output to this range before remapping it to whatever
range is required.  However, concerns about the cost of the division
involved, when such division may be uneccessary (imagine users who do
need the 32-bit integers -- if we go the [0,1] route, they will be
getting numbers that have been divided by 0xfffffff and then multiplied
by 0xfffffff: perverse!) led me to stick to the "PRNG gives 32-bit
integer" assumption.

One final issue -- with this, the revised scheme, we have lost dynamic
polymorphism.  I received some REALLY interesting e-mail from scleary
(Steve) discussing a technique to achieve dynamic polymorphism with
pure, non-inheritance, template classes like this.  It requires a lot
of work, and a lot of classes -- something like two or more for each
class actually used, but it provides maximum flexibility, in both
static and the dynamics senses.  If Steve permits, I will post his
e-mail here, so you all can comment on its suitability.

-- jeet