Boost logo

Boost :

From: Beman Dawes (beman_at_[hidden])
Date: 1998-12-07 17:31:08


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

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk