[boost] Re: Proposal: random number library

From: Jens Maurer (jmaurer_at_[hidden])
Date: 2000-02-24 15:56:13

First a few organizational questions:
 - Should I put all the random number stuff in a sub-namespace boost::random?
Prior art would be boost::cast at least.

 - In the idea of numeric_cast<>, I implemented a
signed_unsigned_compare, which always does the right thing even if
the signedness of its arguments differs.  I needed this; is this of
general interest so that we should put it in <boost/utility.hpp>
or make a fresh header?

 - I currently rely on integer_traits<>, however, this has experimental
status. This would in effect prevent my library from leaving experimental
status.

I have just uploaded to http://www.egroups.com/docvault/boost/random
the next iteration of the random number generator classes, with
the following enhancements:

 - The modulus arithmetic is now in a separate class, but with lots
of template value parameters so that we can decide our overflow
tactics at compile-time.  This meant that the separate *_schrage
could be removed. Btw, does anybody know a better algorithm for
the modular inverse than the Euclidian Algorithm?

 - All PseudoRandomNumberGenerators are now EqualityComparable
and Streamable as explained in random-concepts.html.  random_demo.cpp
was updated to demonstrate the new features. I think my library
now provides at least the same functionality as Harry Erwin's
prototype header.  Note that I could not get Streamable to work
with BOOST_NO_OPERATORS_IN_NAMESPACE, i.e. gcc 2.95.2.

 - There's now a Bernoulli distribution, which says "true" with
probability p, "false" otherwise.

 - I implemented Box-Muller's Method for generating normal random
deviates as well.

The last point leads to an interesting problem:
For the usual fast basic random number generators, it may be
advantageous to save a sin() or cos() calculation and perform
an occasional additional call to the underlying generator instead.
This is what Box-Muller basically does, but it assumes that the
cost of a sin() call is much higher than an invocation of the
underlying generator.  However, in the generic framework of the
boost RNG library, this may not be the eternal truth.  For
example, using random_device or even inversive_congruential<>
makes Box-Muller significantly slower than the old method.
Additionally, there may be environments where invoking functions
with non-deterministic runtime (such as those using the rejection
method to generate random variates) is not advisable, real-time
games for example.

I currently use a template argument to decide which method to use,
which seems nice from a local point of view.  However, this puts
the burden of choosing the fastest generator on the user.
One might have the idea of devising a cost system, where every
generator and every (complicated) function get a cost assigned.
Then, we can decide what method's cost is cheapest in the
context of the current template instantiation parameters.  For
basic costs, we would need some additional class, which would
be specialized according to the arithmetic type we're dealing
with (int64_t operations probably have a different cost than
int8_t ones).

Is this something I should pursue?

Further open topic:
If you need several streams of random numbers, you can use
one generator with different seeds far enough apart.  With linear
congruential generators, it is quite easy to compute element n of
the sequence and use that as the seed for some substream.  If you
now say "random_access_iterator", that's about the semantics of it.

Jens Maurer