[boost] Re: www.boost.org updated

From: Kevlin Henney (Kevlin.Henney_at_[hidden])
Date: 1998-12-09 14:08:57

I am not sure that this is a fair characterisation of the algorithm used,
which is a linear feedback shift register which has well known properties
as a competent and efficient generator. The generator in question uses a 32
bit LSFR to produce bits, and so standard usage is to accumulate the bits
as necessary to create an integer of the appropriate size: no revalidation
is needed for different types if the underlying bit generation is sound; it
is needed if you mess with the LSFR size and composition -- no intention of
doing that!

The pseudo-container suggestion in the original work proved a point about
generated sequences, but is not essential to the random number issue. I
prefer the suggestion that a counting adapter, taking begin iterator and
count, would be more appropriate as this has general application. This is
definitely worth having.

Core to the original work was the idea of generated sequence as iterator,
and I think that is the most valuable thing, ie relationship to iterator
requirements, etc.

I do not see that having alternative implementations of a random number
generator is necessarily a bad thing, esp as the one I was proposing had
different usage properties (ie template parameterisation), performance
characteristics and explores a different model consistent with other parts
of the standard library.

Maybe a suitable area of convergence would be to separate out some concerns
and consider this as three separate layers:

* Random number generation, using a generator function conforming to std
requirements.
* An adaptor class, templated on (and initialised by an instance of) a
random generator type, that allows a generator to be used as a forward
iterator to const.
* An adaptor that creates the effect of a pseudo-container by taking a
begin iterator and count -- this last is more general purpose.

What do you think?

Kevlin

Beman Dawes <beman_at_[hidden]> on 07/12/98 22:31:08

Please respond to boost_at_[hidden]

To:   boost_at_[hidden], boost_at_[hidden]
cc:    (bcc: Kevlin Henney/QA Training Ltd)
Subject:  [boost] Re: www.boost.org updated

At 06:44 PM 12/7/98 +0000, Kevlin Henney wrote:

>I was planning to submit a generalised random number
>iterator/pseudo-container that I wrote over 3 years ago to the
library. It
>was distributed with ACCU's Overload as an example of how the
>container/iterator concept can be generalised.
>
>It is based on the linear feedback shift register described by Bruce
>Schneier in "Pseudo-random_numbers sequence generator for 32-bit
CPUs", DDJ
>February 1992. There is a bit iterator that actually has the
intelligence
>and produces random bits according to this algorithm. The
'container'
>notionally represents the seed of the sequence and an optional
bounding
>length, and is used to source iterators that dereference to unsigned
long
>-- the iterator simply collects the random bits. The iterators are
best
>classified as forward iterators to const.

It is very hard to find a random number generator which comes
anywhere close to the known characteristics, extensive peer review,
and 10 years of experience we have with the Park-Miller "minimal
standard" generator.  That's why as long ago as 1993 it appeared in
proposals to the C++ Committee.

>The updated model I was proposing (in fact, I discovered, I proposed
it in
>the comments to the existing implementation from May '95!) would
allow
>templates for the integer type parameterised, eg unsigned short, and
the
>bit iterator would simply become the bool specialisation.

The problem with that type of parameteriztion for a RNG is that it
then has to be revalidated for each parameter value, and since that
takes years of experience plus enough math professors willing to do
the work, it isn't practical.  For high reliability, high
repeatability work it seems to be better to stick with a generator
with known  characteristics.

>I am keen to put this code forward, as it is in fact an example of
freely
>available software that has already solved the issues and been used
in
>commercial code (at least one known use other than by its author
;->). What
>do others think?

Why don't you look at the proposed min_rand class and see if you
could propose a container/seed/bounding-length class to go with it
based on your prior work?  If the generator to use one of the
parameters, then people could make their own choice of generator.
You could supply your favorite to complement rather than compete with
the existing proposal.

Others keep asking for filter classes which yield various
distributions. So that is another area for exploration.

--Beman

------------------------------------------------------------------------
More trinkets than the 1996 Olympics. Fewer lines than the Goodwill Games
ESPN gear, SportsCenter gear, NBA NHL MLB NCAA NFL gear, Memorabilia
http://ads.egroups.com/click/146/1

Free Web-based e-mail groups -- http://www.eGroups.com

------------------------------------------------------------------------
Free Web-based e-mail groups -- http://www.eGroups.com