[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: srfi-27@xxxxxxxxxxxxxxxxx*Subject*: changes to the design*From*: sebastian.egner@xxxxxxxxxxx*Date*: Thu, 4 Apr 2002 19:18:07 +0200*Cc*: lecuyer@xxxxxxxxxxxxxxxx*Delivered-to*: srfi-27@xxxxxxxxxxxxxxxxx

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

- Prev by Date:
**Re: streams and substreams** - Next by Date:
**New revision of SRFI 27 available** - Previous by thread:
**Re: streams and substreams** - Next by thread:
**New revision of SRFI 27 available** - Index(es):