Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!usc!jarthur!nntp-server.caltech.edu!piglet!madler
From: madler@piglet.caltech.edu (Mark Adler)
Newsgroups: comp.sys.handhelds
Subject: Re: Spectral test on HP28/48 random generator
Message-ID: <1990Sep5.041507.13226@laguna.ccsf.caltech.edu>
Date: 5 Sep 90 04:15:07 GMT
References: <2056@charon.cwi.nl>
Sender: news@laguna.ccsf.caltech.edu
Organization: California Institute of Technology, Pasadena
Lines: 47


Jurjen N.E. Bos writes:
>> Did anybody out there ever try Knuth's Spectral Test on the random
>> generator of the HP28/48?

Yes.

>> Observe that there is no addition; this makes it a little bit harder to
>> apply the spectral test, because it has to be adapted (otherwise I would
>> have done it myself).

The spectral test has nothing to do with the addition---it only tests the
multiplier, so no modification is needed.  (For some other test that might
use the additive constant, one would simply set it to zero anyway.)

Not that anyone is really going to be doing multidimensional Monte-Carlo
calculations on their calculator, but here are the results anyway:

         nu_2^2        nu_3^2     nu_4^2   nu_5^2  nu_6^2
404070635459210   10543036718   23687130   927946   88212

           mu_2          mu_3       mu_4     mu_5    mu_6
           1.27          4.53       2.77     4.37    3.55

According to Knuth, a multiplier passes the spectral test if all the mu's
are 0.1 or more, and passes with "flying colors" if they are all greater
than one.  This multiplier (2851130928467 (mod 10^15)) passes with flying
colors.  Also, the generator is considered to be "adequate in most
applications" if nu_t >= 2^(30/t).  This multiplier easily passes that
test as well.  Since such multipliers are not that easy to find, it would
seem that HP did take the spectral test into account when choosing the
multiplier.

The only difficulty with a purely multiplicative random number generator
like the one used in the HP-28 and 48 is that it is not possible to get the
maximum length sequence (which would be 10^15 - 1 for the HP).  The longest
possible sequence for any purely multiplicative generator mod 10^15 is
5x10^13, and this length is achieved if the initial seed is not a multiple
of 2 or 5 and the multiplier is a primitive element modulo 10^15.  It can
be shown that since 2851130928467 (mod 200) = 67, that this multiplier
satisfies the condition.  I don't know how the seed is set on the HP, so I
don't know if the seed condition (not a mutliple of 2 or 5) is met.  If the
seed condition is met, then 5x10^13 is a more than adequate period, since
only 12 of the digits become part of the actual random number.

Mark Adler
madler@piglet.caltech.edu