How RAND Works
by Steve VanDevender & Detlef Mueller

(Comp.sys.hp48)
Item: 1661 by jollie@zambini.cs.uiowa.edu [Jeffrey C. Ollie]
Subj: HP's RAND algorithm
Date: 04 Sep 1992

I just got my 48SX, and I love it! But, I was wondering what algorithm
HP used for the random number generator. I'm hoping that it is a
prime modulus multiplicative linear conguential generator (I'm not
making this up) with a=16807 and m=2^31 - 1. I've written one of my own,
but would prefer to use the built in RAND.

Jeff Ollie
jollie@zambini.cs.uiowa.edu "The Happy User"

----------
Resp: 1 of 2 by stevev@miser.uoregon.edu [Steve VanDevender]
Date: 05 Sep 1992

The HP 48 uses a multiplicative linear congruential generator (I
know you're not making it up) but not the particular one you
speak of.  It uses the formula

R(n+1) = R(n) * 2851130928467 (mod 10^15)

to generate a 15 decimal digit internal seed.  The random number
returned is R(n+1) / 10^15 rounded to 12 decimal digits.

The random number seed R(n) is stored in BCD at #706A4.  If the
seed is 0, then the seed is reset to 999500333083533.

This information was obtained by disassembling the system RPL
routine %RAN, a primitive code object at #2AFC2.
--
Steve VanDevender       stevev@greylady.uoregon.edu

----------
Resp: 2 of 2 by detlef@dmhh.hanse.de [Detlef Mueller]
Date: 06 Sep 1992

Don't worry, RAND is based on a linear congruential method (see pg. 9 of
'The Art of Computer Programming', Vol.2 by D.E. Knuth):

    Xn+1 = (a * Xn + c) mod m

where
    a = 2851130928467
    c = 0
    m = 1E15

The intial value of X0 after a memory lost is 999500333083533.

If you choose an X0 which isn't a multiple of 2 or 5 then you'll get a
period of 5E13 (see pg. 20 of above book - a mod 200 is 67).

Bye,
        8-Detlef
--

[Note: Yes, 2851130928467 is a prime number.  999500333083533 factors
 into 3^2 * 19 * 5845031187623.  This computation was done with
 FCTR.LIB by Klaus Kalb, on Goodies Disk #8. Jeff wanted the modulus
 to be prime also, but since it's a power of 10, it's obviously not.
 The cycle is so huge, however, that it doesn't matter; if you were to
 generate 100 RAND's every second (that's about as fast as the 48 can
 go), it'd take more than 15,000 years for the cycle to start
 repeating!  This machine is fun to play with... -jkh-]