mwm@eris.berkeley.edu (Mike (I'll think of something yet) Meyer) (09/26/89)
In article <16646@watdragon.waterloo.edu> ccplumb@rose.waterloo.edu (Colin Plumb) writes: <In article <1989Sep22.082034.1405@agate.berkeley.edu> mwm@eris.berkeley.edu (Mike (I'll think of something yet) Meyer) writes: <>> A trick recommended by the authors of <>> _Numerical Recipes_ (in addition to their own, portable generators) is to <>> "scramble " your generator by calling it twice; the first time is <>> used as an index to an array of numbers from the generator. <> <> Knuth recommends a better version of this - use two generators, one <> to generate indices, one to generate values. < <No, if you read Knuth, he says using the same generator is better worst- <case and at least as good on average. I have read Knuth. What he says about using one generator instead of two is: The randomizing effect would be quite minimized, because .... However, some similar approaches could be used: .... This is an inexpensive way to improve the randomness of a sequence which is already reasonably good. [This is the answer to question #5, section 3.2.2] Did he recant in a later work? If so, could you provide the reference? <mike -- That time we slept together Mike Meyer That's as far as it went mwm@berkeley.edu Yet though we're not quite lovers ucbvax!mwm You're more than a friend mwm@ucbjade.BITNET
ccplumb@rose.waterloo.edu (Colin Plumb) (09/26/89)
I wrote: >> No, if you read Knuth, he says using the same generator is better worst- >> case and at least as good on average. And Mike Meyer <mwm@eris.berkeley.edu> took me to task. My memory was slightly faulty. I was thinking about algorithm B (algorithm M with X_n = Y_{n+/-1}, I can't be bothered to work out which) and algorithm M with X_n and Y_n *sucessive* values from the same random-number stream, as described at the end of section 3.2.2, which references F. Gebhardt [Math. Comp. 21 (1967), 708-709]. Algorithm B Knuth say, "...can be recommended for use in combination with any other random-number generator." Start with an array V of size k and a variable Y set to random values. Then, int good_rand() { int j; j = Y*k/MAX_RAND; /* Or Y%k, but the high bits are usually better */ Y = V[j]; V[j] = bad_rand(); return Y; } j = bad_rand()%k; also works well, I believe, but Mike is right that I don't have Knuth backing me up on that. I wish Knuth wasn't written in such a ridiculous assembly language. It would make the algorithms much more accessible. -- -Colin