From:	Kbwms AT aol DOT com
Message-ID:	<6faf3a97.366d789b@aol.com>
Date:	Tue, 8 Dec 1998 14:06:03 EST
To:	dj AT delorie DOT com
Cc:	djgpp-workers AT delorie DOT com
Mime-Version:	1.0
Subject:	RNG random()
X-Mailer:	AOL 3.0 16-bit for Windows sub 38
Reply-To:	djgpp-workers AT delorie DOT com

Dear DJ Delorie,

I see that my suggested changes to random() were not implemented in
the latest release.  It is probably just as well.  In a recent letter,
Pierre L'Ecuyer, of the University of Montreal, tells me that there
are problems both with the original implementation and my suggested
fix.

His letter is appended to this.

K.B. Williams
++++++++++++++++++++++++++++++++++++++++++++++++++
Subj:	 Re: Concerning "Bad Lattice Structures ..."
Date:	98-11-30 10:12:25 EST
From:	lecuyer AT IRO DOT UMontreal DOT CA (Pierre L Ecuyer)
To:	Kbwms AT aol DOT com

Dear Mr. Williams,
>
> Dear Pierre L'Ecuyer,
>
> I reread with interest your paper "Bad lattice structures for vectors
> of non-successive values produced by some linear recurrences."
> I want to reassure myself that I have the picture here.  On page 5,
> you cite the Mitchell and Moore generator which Knuth (vol 2, 1981)
> suggested "may well prove to be the very best ..." as having "highly
> unfavorable properties and should be avoided."  The implication is
> that all such generators exhibit the same properties.  In particular,
> Knuth displays a table at the top of page 28 that lists many pairs
> of lags.  Will any lagged-Fibonacci generator that uses lags from
> this table suffer the same fate?

Yes, exactly.

>
> A popular generator in the Unix system is random().  This program
> uses one of four lagged-Fibonacci generators - selected by the user.
> (I tested this generator using Marsaglia's birthday spacings test
> and it fails as predicted.)  If I understand you correctly, no matter
> what I try (such as Marsaglia's additive generator fix-up), nothing
> can save it.

Yes, you are right.

>
> Are there any tests that I can use to demonstrate this failure?
> The lagged-Fibonacci generators in random(), mentioned above,
> apparently pass the tests in DIEHARD after I implement a 31-bit
> version of the additive-sequence generator proposed by Marsaglia
> in "Toward a universal random number generator."  As you point
> out, such a fix up is illusory.

This proposed RNG is a little bit better, but still has deficiencies.


P.L.

- Raw text -