jurjen@cwi.nl (Jurjen NE Bos) (09/04/90)
Did anybody out there ever try Knuth's Spectral Test on the random generator of the HP28/48? For interested people, the formula is X(k+1) = X(k) * 2851130928467 (mod 10^15) . 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). Did anybody at HP already do it? (Reference: D.E. Knuth: You-know-what; Vol. 2) Thanks, Jurjen -- | | "Never imagine yourself not to be otherwise than what | | Jurjen N.E. Bos | it might appear to others that what you were or might | | | have been was not otherwise than what you had been | | jurjen@cwi.nl | would have appeared to them to be otherwise." |
madler@piglet.caltech.edu (Mark Adler) (09/05/90)
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
jurjen@cwi.nl (Jurjen NE Bos) (09/06/90)
Mark Adler, thanks for your reply. It doesn't surprise me the least that they used a multiplier that passes with "flying colors". Isn't that what every HP buyer expects them to do? We want _the best_. We buy HP. Also, you write: > 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. The seed condition is met by forcing the lst digit to a one. To be exact, the seed is set from the real number given as first the 12 digits of the mantissa, then the last two digits of the exponent, then a 1. -- | | "Never imagine yourself not to be otherwise than what | | Jurjen N.E. Bos | it might appear to others that what you were or might | | | have been was not otherwise than what you had been | | jurjen@cwi.nl | would have appeared to them to be otherwise." |