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