Random thoughts on HP48 random functions

[John H Meyers]

Everything you never wanted to know about the HP48 Random Number generator,
and were afraid to even ask:

On 1996/07/16, Steve VanDevender posted the following description
of the HP48 RAND function, as implemented by SysRPL function
%RAN at address #2AFC2h:

: Take the 15-digit seed S (0 <= S < 10^15) stored in memory.
: If S == 0, store 999500333083533 in S. To generate the next
: pseudorandom number, multiply S by 2851130928467 and take the result
: modulo 10^15 (yes, there is no additive constant involved).
: Store that result back in S. Then divide the result by 10^15 and
: take the 12 most significant digits (truncating rather than rounding
: if more there are more than 12 significant digits), and return that
: floating-point number as the next pseudorandom number. [End of quote]

The 15-digit integer random number seed is located at address RANDOMSEED
(#706A4h in the S/SX, #80822h in the G/GX), and may be viewed with
a memory scanner, such as SC from HACK.LIB or "Mon" from DONNELY.GX
(the latter is a utility library actually written by Detlef Mueller,
found at <ftp://hpcvbbs.cv.hp.com/dist/hp48g/utils/misc>).

The RDZ command sets this seed, and each subsequent RAND command then
replaces it with the new 15-digit random integer, as described above;
the details below will serve to illustrate what values are meaningful
for use as arguments to RDZ:

RDZ uses its (real number) argument (X) to set the 15-digit integer
seed; the general idea is that the significant digits of the argument
(but sometimes not all of them, perhaps even none) are used to set the
first twelve digits of the random seed; the exponent of the argument (X)
is sometimes used to set the next two digits, and the last digit
of the random integer seed is always initialized to 1.

More precisely:

o The sign of X is ignored.

o If X is 1 or greater, all twelve mantissa digits of X are used; three
digits are appended, which are equal to '((XPON(X)+1) MOD 100)*10+1'
E.g 3.14159265359 --> 314159265359011
^^^^^^^^^^^^ (from mantissa of X)
^^ (from exponent of X)
^ (final digit always set to 1)

It is thus possible to set any one of 9E13 different starting seeds
using arguments of 1 or greater (the first digit of these can not be
zero, because all mantissas begin with a non-zero digit); it will
later be seen that the period of the random number generator
(before it exactly repeats) is at most 5E13, so there must be
more than one completely distinct sequence which can be produced
(sixteen are theoretically possible, but only two are ever generated).

o If X is less than 1 but not less than 1E-12,
the random integer seed is set to 'IP(1E12*X)*1000+1'
E.g.
3.14159265359E-1 --> 314159265359001 (exponent of X is not used)
3.14159265359E-7 --> 000000314159001
3.14159265359E-12 --> 000000000003001

Note that the trailing digits get truncated as X gets smaller; this
is reminiscent of the HP15C, where all ten fixed digits of the current
random number (i.e. ten fixed digits following the decimal point)
could be saved and later restored to resume the sequence, but since
the HP48 usually truncates the last digits of the 15-digit current seed
when it returns a real number as a result (and since the last digits
are usually not 001 after some multiplications have occurred from
using RAND), it is not possible to do the same on the HP48.

You could, however, write your own ML function to recall the current
seed, with 15 digits packed into either a Long Real or Hex string
object, and likewise another ML function to restore the seed.

o If X is less than 1E-12, all the mantissa digits of X are completely
ignored, and only the exponent (power of ten) is used to set the seed;
if XPON(X) is between -13 and -15, the seed is set to 000000000000001;
otherwise the seed is set to '((XPON(X)+16) MOD 100)*10+1'
E.g.
3.14159265359E-13 --> 000000000000001
3.14159265359E-14 --> 000000000000001
3.14159265359E-15 --> 000000000000001
3.14159265359E-16 --> 000000000000001
3.14159265359E-17 --> 000000000000991
3.14159265359E-50 --> 000000000000661 etc.

As you can see, quite a wide range of input values all generate
the same random seed 000000000000001, and it is somewhat inadvisable
to ever use any value less than 1E-12 as an argument for RDZ; for
most purposes, you wouldn't even think of using values less than .1,
where any trailing significant mantissa digits would be lost.

o If X is zero (requesting a starting value randomized from the clock),
the least significant 20 bits of the TICKS value are converted
to an integer, which is then used as above, e.g.
123456 ticks --> 123456000000061
234567 ticks --> 234567000000061

Note that using only 20 bits of TICKS gives us only 2^20 = 1048576
possible different starting points, which is a lot fewer than we might
expect, when we could ourselves choose nearly 1E14 different specific
non-zero starting values for RDZ. Not only that, but the low-order
20 bits of TICKS repeats every two minutes or so, giving rise to
a distinct possibility of repeating the same sequence.

Finally, the fact that the significant digits of the seed are all
at the far left, leaving a generally constant portion at the right,
makes the first RAND value after 0 RDZ most commonly have the
same six least significant digits (986636) about 85% of the time,
which makes it quite apparent that a "more random" seed
could have been chosen.

If this is of concern to you, here is an alternative to 0 RDZ,
which chooses from among 1E12 possible different starting points,
rather than from only about 1E6, and which can not possibly repeat
the same starting point again for about 3.87 years:

\<< RCWS 64 STWS 1E12 TICKS OVER DUP2 / * - B\->R SWAP / RDZ STWS \>>

This is a slightly improved version of the RDZ0 function which
I previously posted in a "simple XOR cipher" package, in order
to provide at least 2^32 different randomized keys per user key,
so that neither re-using keys nor having common plaintext would
have the usual bad effects common to such a ciphering method.

HP could have used TICKS MOD 1E14 had they thought about it,
which would have made it impossible to repeat in a lifetime;
hex digits in the seed do not seem to bother RAND at all, so
it would even seem that the whole 13-nibble TICKS value could
be pasted in directly, without bothering with the arithmetic!

BTW, when you need a sequence of random numbers, you should do
RDZ only once, and thereafter use only RAND; the repeated use of
0 RDZ (or RDZ0) may paradoxically not produce a distribution
that passes "randomness" tests as well as the completely
deterministic sequence generated by RAND; I'm not overly impressed,
for example, with the slightly skewed results of my old Casio's,
which I suspect of doing some kind of timing of each keypress
to generate a "spontaneous" random number (and why only 3 digits?).

Well, so much for RDZ; now, what about RAND?

The HP48 RAND merely multiplies the 15-digit seed by a 13-digit constant
and keeps the low-order 15 digits; what is the period of this sequence,
before it repeats? Well, the last digit repeats every 4th time, the
last two digits repeat every 20th time, the last three digits repeat
every 100th time, and the last four digits repeat every 500th time.

However, the last five digits repeat only after 5000 RAND's,
the last six digits after 50000, the last seven digits after 5E5,
the last eight digits after 5E6, and the last nine digits after 5E7.

At this rate, the period for 15 digits is at best 5E13;
naturally, this means that some 12-digit truncated real values repeat
during the sequence, even though the internal 15-digit value does not.

Curiously, if you can set the internal seed to 500000000000000, then
every subsequent RAND will return the same value .5; however, you can
not normally arrive at such an internal value using only RDZ and RAND.
You can do it with a memory scanner, however, and then astound your
classmates with a random number generator that outputs a constant :)

This weird behavior could never have happened in the HP15C, where the
internal seed is 10 digits in length, and where it just so happens
that the period of the sequence is also exactly 1E10; you can thus set
any starting seed you want, and every possible seed will produce the same
sequence, just starting at a different point; this is the case because,
unlike the HP48, the HP15C uses a general LCRNG with an additive constant,
and the pair was chosen to yield the maximal period.

Okay, the random rainfall rate is currently down two standard dev's
below the past four hours' moving average, and I'm gettin' outta here
while the chances are maximized :)

-----------------------------------------------------------
With best wishes from: John H Meyers <jhme...@mum.edu>

[Dan Kirkland]

In article <5mgqih$bm4$1...@news.iastate.edu>,

jhme...@miu.edu (John H Meyers) writes:

>Everything you never wanted to know about the HP48 Random Number generator,
>and were afraid to even ask:

[Lots of deletions]

> Finally, the fact that the significant digits of the seed are all
> at the far left, leaving a generally constant portion at the right,
> makes the first RAND value after 0 RDZ most commonly have the
> same six least significant digits (986636) about 85% of the time,
> which makes it quite apparent that a "more random" seed
> could have been chosen.

This I have noticed...

> HP could have used TICKS MOD 1E14 had they thought about it,
> which would have made it impossible to repeat in a lifetime;
> hex digits in the seed do not seem to bother RAND at all, so
> it would even seem that the whole 13-nibble TICKS value could
> be pasted in directly, without bothering with the arithmetic!

I am currently using: TICKS 16 * 1 +

The 16* shifts the digits to the left, then the 1+ is used
to make sure the seed is odd and not 5.

>The HP48 RAND merely multiplies the 15-digit seed by a 13-digit constant
>and keeps the low-order 15 digits; what is the period of this sequence,
>before it repeats? Well, the last digit repeats every 4th time, the
>last two digits repeat every 20th time, the last three digits repeat
>every 100th time, and the last four digits repeat every 500th time.

I don't really know anything about random number generation.

I need some random hex digits for my chess program. One hex digit
for each root move. And I don't want to spend too much time to
generate these digits.

So...
I decide to see if I could modify the HP48 routine to suit.
First I noticed how "0 RDZ" would often cause the same six
least significant digits (986636). This is NOT acceptable!

So I decided to use: TICKS 16 * 1 +

And then I will NOT use the first random number generated.

This uses the full 13 digits from TICKS so the seed should
never be duplicated as long as the time is kept fairly
accurate. Also by shifting to the left (16*) and adding
1, it would always start odd (but not 5). (Not sure this
is needed for what I want.)

Next I changed the multiplier to a 16 digit hex multiplier.

Still there was a problem of the least significant digits
being repeated. The less significant the more frequent the
repeats (much as you stated above).

To fix this I just rotated the most significant digit around
as the least significant digit and then used this to seed
the next number.

This seems to solve the often repeating pattern of the least
significant digits. While it looked like there was somewhat
of a repeating pattern now and then, there was always some
change in it. I couldn't find an exact repeat of the pattern
of the least significant digit with 65,536 numbers generated.

Still, I have a couple of concerns...

Even though the starting seed (from TICKS) should never be
repeted, it could still maybe start the same pattern as a
different starting seed???

By rotating the most significant digit around as the least
significant, I am wondering if maybe there could be some
cases where I lose randomness?

For example, sometimes the digit rotated will not be odd.
Could I somehow lose complete oddness? (All even random
numbers.)

For that matter, the digit rotated will sometimes be zero.
But it should not matter as long as I have digits somewhere
that are non-zero, right?

I do check and if the seed is zero I change it to one.
So even of I lose all non-zero digits it should be okay...?

I don't want to force the seed to always be odd because then
the last digit of the random number, before it is rotated,
will always be odd. And then I couldn't use it. (In fact,
it, and all digits should be allwoed to be anything including
zero!)

I could do something like the HP48 routine which always keeps
the seed odd but doesn't use the last three digits in the
random numbers generated???

But I like it my way. Keeping the multiplier odd, but allowing
the seed to be anything but zero...?

For that matter, even though I won't be using the first random
number generated, I am thinking about NOT forcing the starting
seed to be odd... (Just using TICKS as is...?)

Thoughts?
Ideas?

Oh, and one more thing...
I need a 16 digit hex number that is prime!
And just for fun, I would like it to include all 16 possible
hex digits (0 through F, if possible...).

Currently I am just using a number that I made up that is
odd and does not end with 5. But it is NOT prime.

Thanks for reading, and many more thanks for input!

And yes, I really am working on a BETTER chess program!
Yes, I know it was quite a while ago that I first mentioned
this (a couple years even!). But there has been a couple
other chess programs released after that and so I have not
been in too much of a hurry...

But I do hope to get something finished this summer, so
by next fall...?

(Fingers crossed...)
dan

[John H Meyers]

In article <5mjgrv$q...@ee.utah.edu>
(29 May 1997 03:05:03 -0600),
kirk...@ee.utah.edu (Dan Kirkland) writes:

> I am currently using [as a random seed]: TICKS 16 * 1 +
> This uses the full 13 [hex] digits from TICKS...

> The 16* shifts the digits to the left, then the 1+ is used
> to make sure the seed is odd and not 5.

Hmm.. I was not sure in reading this whether you meant:

o Using the above as an argument to RDZ, then using RAND.
o Pasting the above (using ML) into the internal seed location,
then using RAND, which should in fact work!
o Using the above with other binary constants to make your own RNG,
completely in lieu of using the built-in RNG at all.

In the first case, it would not work as suggested, because with TICKS
being on the order of 5E14, the full value of TICKS can not be converted
to a real number (for RDZ) without truncating several low-order digits;
because of this, if TICKS B->R RDZ is executed rapidly several
times in succession, it is likely to produce identical results,
whereas if either 0 or TICKS MOD 1E12 is used as the argument for RDZ,
then the effective value changes once per clock tick, and can not
possibly be the same when executed twice in succession (because
all commands take longer than a clock tick to execute).

For going the standard RDZ,RAND route, I recommend using
(TICKS MOD 1E12)/1E12 as the argument to RDZ, as I posted in the most
recent version of the RDZ0 program; the final division by 1E12 ensures
that the digits of TICKS MOD 1E12 will always be right-justified in
the first 12 digits of the random seed, rather than left-justified,
which will make a significant difference when the value has recently
"rolled over" and started counting up again from zero (you have already
noticed how 0 RDZ left-justifies the small number of digits it produces,
and thus almost always repeats the same right-side digit sequence).

This improves upon 0 RDZ, which is in effect the same as using
TICKS MOD 2^20, where 2^20 = 1048576, which limits the number of possible
starting points for the RNG to many orders of magnitude less than does
TICKS MOD 1E12, the latter being much closer to the probable RNG period
of 5E13 (before the sequence starts to repeat).

2^20 ticks is only about two minutes, whereas 1E12 ticks is about
3.87 years, so the using latter modulus for the argument to RDZ
guarantees no possible repetition of the exact same starting point
for several years, while the former allows some small possibility
of an exact same repetition over a relatively brief period.

One way to compute (TICKS MOD 1E12)/1E12 for RDZ without
truncating any digits is, as previously posted:

RCWS 64 STWS 1E12 TICKS OVER DUP2 / * - B->R SWAP / RDZ STWS

BTW, when using RDZ, the user does not need to be concerned with
any multiples of 2 or 5, because RDZ always pastes a "1" into the
final digit of the 15-digit decimal seed; only if you paste
the digits yourself into the internal memory location need
you bother to do this kind of adjusting yourself.

> I need some random hex digits for my chess program. One hex digit
> for each root move. And I don't want to spend too much time to

> generate these digits [...]

> I changed the multiplier to a 16 digit hex multiplier.

Sure, why use the internal decimal RAND when you can make your
own binary LCRNG. Just choose how many digits long you want
the factors and result to be; 64 bits is about the maximum
readily usable in the HP48. You could then use the entire TICKS
value as a starting seed, and by choosing the two LCRNG constants
as per Knuth (I believe the precise requirements have been posted
either here or in sci.crypt), you will be all set to generate
a sequence longer than necessary for any practical purpose :)
(well, you might shorten it to 32 bits, or even to 20 bits,
depending on how much speed vs. minimum cycle length you want).

If you choose the correct constants, you do not need to do anything
to TICKS to create a good starting value, because all possible
binary values will be part of the complete sequence.

For example, in the HP15C, every decimal 10-digit starting seed is
equally good; the period of the HP15C LCRNG being exactly 1E10, the
complete sequence includes every possible 10-digit value exactly once.

In the HP48, however, the period of the 15-digit value is less than
1E15, and only certain starting seeds can produce a period of at most
5E13; these seeds must not, it turns out, be multiples of 2 or 5.

If you make your own RNG, you can eliminate this weirdness entirely
by choosing appropriate constants (including the additive constant,
which adds so trivial a percentage of time to the whole computation
that it hardly pays to leave it out).

Finally, use only the high-order 4 bits of each binary "random" value,
to avoid the ever-decreasing randomness of the lower-order bits/digits
output by any LCRNG. Or, to do less computing per digit, compromise
by using the first several hex digits of each output.

If you didn't mean to use your own RNG, but to use the built-in one,
then you can use RAND 16 * CEIL 1 - for each value of 0-15. If you
are tempted instead to use RAND 16 * IP, note that the result of the
latter can be anywhere from 0 to 16 (.999999999999*16), and would need
a subsequent 15 MIN to prevent the value 16 from sneaking through.

> Even though the starting seed (from TICKS) should never be

> repeated, it could still maybe start the same pattern as a
> different starting seed???

An LCRNG having a maximum-length cycle has only one "pattern,"
but the starting seed determines where in the cycle to start.

Nonetheless, looking at only the leading bits/digits of the output,
the values look random and unpredictable. However, if we are using a
32- or 64-bit LCRNG and we have, say, 32 samples of the first 4 bits of
consecutive outputs, there is probably only one place in the complete
cycle where this sequence occurs, and if only we could find that place,
then we could predict all future outputs. More "secure" RNG's remedy
this "weakness," but for a chess-playing game, rather than for
high-security cryptography, an LCRNG might do very well.

The built-in decimal RDZ/RAND may possess two independent complete
sequences, as previously noted, but this doesn't change things
in any significant way; at worst, half the time you start
somewhere within the "A" cycle, and the other half of the time
you start somewhere in the "B" cycle (the cycles are probably
correlated in some way, but I don't know exactly how).

> By rotating the most significant digit around as the least
> significant, I am wondering if maybe there could be some
> cases where I lose randomness?

Tampering with a well-known and well-analyzed method having proven
properties can easily create something which has less desirable
properties; if the properties of a standard, simple LCRNG are
satisfactory for your purpose, then why mess with it? Just
initialize it once, use the LC formula thereafter, and be done with it!

If seeking a "cryptographically secure" RNG, there are apparently
some treatises covering various already-studied ones; these generally
seem to eat up memory and CPU time in direct proportion to how
"good" they are for this purpose, demonstrating once again that
"there is no free lunch" :)

> Oh, and one more thing... I need a 16 digit hex number that is prime!

To make a binary LCRNG? Well, why not use ALG48's PRIM+ function
to find the next prime number after some starting value of your
choosing in the range 2^60 to 2^64, then enter that value as a
user-binary decimal integer (#XXX...d) and display its hex equivalent?

> And just for fun, I would like it to include all 16 possible
> hex digits (0 through F, if possible...).

Easy; just write yourself a program to do the above, test all
the 4-bit hex digits for being different (there are so many
interesting ways to do this that Richard Nelson might want
to consider this as a programming contest problem) and then
keep trying until either you find one or your batteries run out;
if you really want this to be fun, run it on a high-power
workstation rather than on the HP48, or else we may never
hear from you again :)

"Remember the Prime Directive, Captain!"