changes to the design

[sebastian.egner@xxxxxxxxxxx]

Dear list,

The following issues have been raised in the discussion about 
SRFI-27 "Sources of Random Bits".

1. Which generator to use for the reference implementation?
2. How to deal with several streams and substream?
3. How to obtain streams of random bytes (e.g. for security appl.)?
4. How to deal with default-random-source?
5. How to name the procedures?

In particular the first and second question have led me to reconsider
the entire design. The result of this process is a revision of the SRFI
which will be announced by the editors shortly. I will now briefly discuss
the topics and my changes to the design.

Ad 1. 

My original reference implementation was based on George Marsaglia's
COMBO generator, which is a 32-bit implementable generator of
period 2^60. From my experience, this generator is usually quite
acceptable.

Brad Lucier suggested to use Pierre l'Ecuyer's MRG32k3a generator,
based on the fact that there is substantially more theory on this generators
than for the COMBO generator. In addition, its period is much larger and
it allows to advance the generator by more than one step at once, which
is necessary to provide more than one stream in a controlled fashion.

I have fully adopted Brad's proposal. The revised version of the reference
implementation is entirely based on MRG32k3a.

Ad 2.

An important issue for numerical simulation and other applications are
streams and substreams. This means that the interface provides a simple
way to obtain several streams derived from the same backbone generator.
Ideally, these streams appear to be statistically independent.

Moreover, as Pierre l'Ecuyer pointed out, a most frequent pattern of usage
for simulations is to obtain streams and then substreams of these streams.
In other words, the independent streams are S[i,j] for i, j >= 0 and not just
S[i] for i >= 0. Since it also represents a considerable amount of work (in
the case of MRG32k3a already done by P. l'Ecuyer) to find good points
in the entire period for the independent streams, I have adopted this two-
dimensional indexing for independent streams.

Technically, the interface has been augmented by the call

        (random-source-pseudo-randomize! s i j) 

which advances the random source s to the beginning of the (i,j)-th
independent stream. (Refer to the revised SRFI document for details.)

In effect, the reference implementation of the SRFI does now contains
most of the features of the software Pierre l'Ecuyer's has written to
provide random number generators (refer to l'Ecuyer's publications).

Ad 3. 

In certain applications it is desired to obtain a sequence of random bytes
in one way or the other. The current interface provides two ways to do this.
One can either repeatedly call (random-integer 256), maybe for more
than one byte at a time, or one can call (random-integer (expt 256 n))
where n is the number of bytes desired. Both ways have their applications 
and I suppose the potential performance gain for a dedicated procedure
is not worth the effort for the specification. Therefore I did not change the
interface for that.

Ad 4.

The interface specifies that there is a default random source that controls
the behavior of the "no fuss" procedures random-integer and random-real.
Felix proposed to replace the global variable default-random-source by
a procedure call to set or retrieve the default random source.

I have experimented with this idea. Unfortunately, it does not solve the
problem that the procedures random-integer and random-real have an
implicit reference to an object that controls their behavior. This become
particularly problematic when a caller wants to set a new default random
source. Does that automatically mean that the variables random-integer
and random-real should be changed as well?

Eventually, I have chosen to leave this decision to the (expert) user,
which means default-random-source is still a global variable, but
I advise the occasional user not to assign any new value to avoid
the miraculous "I set the default source, why does random-integer
seem to be unimpressed?"-effect that I had to endure a couple of times.
(An assignment to default-random-source does not change random-integer
in any way; it still uses the old object.)

Ad 5.

It has been proposed by Bengt Kleberg to change the naming convention
from "set-random-xyz!" into "random-xzy-set!". This has been done.


Additional Modifications to the SRFI

The largest modification in the interface specified by the SRFI is the
presence of a mechanism to obtain random real numbers. This has
two reasons. 

First, there are many applications (in particular numerical simulations)
that need real values as their primary source of randomness. I was just
to biassed towards my own (discrete) applications to understand how
fundamental it is to have reals available.

Second, there are (backbone) pseudo random number generators 
optimized to exploit floating point hardware nicely, MRG32k3a is an
example of that. It would be an untolerable waste of performance if
such a generator would have to convert its output into range-limited
integers, just for the next functions to reconstruct the reals if the application
needs it. 

Once I had fully adopted the need for real numbers, it became clear
that the old reference implementation (based on COMBO anyway)
had to be redone entirely. This has taken quite some time to accomplish
but it has resulted in three different implementations that are meant as a 
source of inspiration to Scheme implementors.

Please refer to the SRFI document once it is available online... :-)

Sebastian.

----
Dr. Sebastian Egner
Senior Scientist
Philips Research Laboratories
Prof. Holstlaan 4 (WY2)
5656 AA Eindhoven
The Netherlands
tel:       +31 40 27-43309
fax:      +31 40 27-44918
email: sebastian.egner@xxxxxxxxxxx