Subject: Random thoughts on HP48 random functions
Date: 31 May 1997 05:31:05 GMT
From: jhmeyers@miu.edu (John H Meyers)
Newsgroups: comp.sys.hp48
In article <5mjgrv$qps@ee.utah.edu>
(29 May 1997 03:05:03 -0600),
kirkland@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!"
-----------------------------------------------------------
With best wishes from: John H Meyers <jhmeyers@mum.edu>
