> > By the way, I think Vladimir knows this. :-) > > Steve- Hide quoted text - >I think I may have misunderstood Vladimir's comment about "why add up 12 numbers ... " I answered the part about why "12" is sometimes done - to get a standard normal (approximation). Certainly when using more or fewer numbers in the sum, one just divides by the variance to make it standard normal - the sum of 12 part avoids this simple correction. As they say there is more than one way to skin a cat. About linear congruence pseudo random number generators - they have an interesting form of sample to sample correlation. If you take consecutive numbers from such a generator, form x-y pairs from them and plot them, the points will all lay along diagonal lines and not fill the field uniformly. Knuth gives some good examples of how to fix this sample to sample correlation with shuffling. I've had a lot of experience with making pseudo random number generators pass the statistical requirements for state lotteries and gaming. Clay
Gaussian Noise Generation
Started by ●July 31, 2007
Reply by ●August 2, 20072007-08-02
Reply by ●August 3, 20072007-08-03
Clay wrote:>> By the way, I think Vladimir knows this. :-) >> >> Steve- Hide quoted text - >> > > I think I may have misunderstood Vladimir's comment about "why add up > 12 numbers ... " > > I answered the part about why "12" is sometimes done - to get a > standard normal (approximation). Certainly when using more or fewer > numbers in the sum, one just divides by the variance to make it > standard normal - the sum of 12 part avoids this simple correction. As > they say there is more than one way to skin a cat. > > About linear congruence pseudo random number generators - they have an > interesting form of sample to sample correlation. If you take > consecutive numbers from such a generator, form x-y pairs from them > and plot them, the points will all lay along diagonal lines and not > fill the field uniformly. Knuth gives some good examples of how to fix > this sample to sample correlation with shuffling. I've had a lot of > experience with making pseudo random number generators pass the > statistical requirements for state lotteries and gaming.One of the commonest congruels, used in a lot of DSP code I've seen, has zero randomness in the LSB. Its goes 10101010 through successive samples. This doesn't matter much most of the time, because the rest of the 16 bits are pretty good. I've seen the LSB tested as a random logic value, though. :-) Steve
Reply by ●August 3, 20072007-08-03
On 3 Aug., 13:34, Steve Underwood <ste...@dis.org> wrote:> Clay wrote: > >> By the way, I think Vladimir knows this. :-) > > >> Steve- Hide quoted text - > > > I think I may have misunderstood Vladimir's comment about "why add up > > 12 numbers ... " > > > I answered the part about why "12" is sometimes done - to get a > > standard normal (approximation). Certainly when using more or fewer > > numbers in the sum, one just divides by the variance to make it > > standard normal - the sum of 12 part avoids this simple correction. As > > they say there is more than one way to skin a cat. > > > About linear congruence pseudo random number generators - they have an > > interesting form of sample to sample correlation. If you take > > consecutive numbers from such a generator, form x-y pairs from them > > and plot them, the points will all lay along diagonal lines and not > > fill the field uniformly. Knuth gives some good examples of how to fix > > this sample to sample correlation with shuffling. I've had a lot of > > experience with making pseudo random number generators pass the > > statistical requirements for state lotteries and gaming. > > One of the commonest congruels, used in a lot of DSP code I've seen, has > zero randomness in the LSB.Well, strictly speaking no PRNG has any randomness in it. If it can be computed, it ain't random :-).> Its goes 10101010 through successive > samples. This doesn't matter much most of the time, because the rest of > the 16 bits are pretty good.I once used a very simple but fast 32bit linear congruential PRNG (with parameters values suggested by Knuth). I wanted to use only a subset of the bits (I think the 10 least significant) to generate integers uniform at random from 0 - 1023. However, when I plotted consecutive values, nice diagonal stripes became visible. The numbers also failed a chi^2 test miserably. In the end I used all 32bits to generate 10 somewhat more random bits, which passed my simple requirements and was still damn fast.> I've seen the LSB tested as a random logic > value, though. :-)Nobody's perfect. :-) Regards, Andor> > Steve- Zitierten Text ausblenden - > > - Zitierten Text anzeigen -
Reply by ●August 3, 20072007-08-03
On 2007-08-03 11:34:51 -0300, Andor <andor.bariska@gmail.com> said:> On 3 Aug., 13:34, Steve Underwood <ste...@dis.org> wrote: >> Clay wrote: >>>> By the way, I think Vladimir knows this. :-) >> >>>> Steve- Hide quoted text - >> >>> I think I may have misunderstood Vladimir's comment about "why add up >>> 12 numbers ... " >> >>> I answered the part about why "12" is sometimes done - to get a >>> standard normal (approximation). Certainly when using more or fewer >>> numbers in the sum, one just divides by the variance to make it >>> standard normal - the sum of 12 part avoids this simple correction. As >>> they say there is more than one way to skin a cat. >> >>> About linear congruence pseudo random number generators - they have an >>> interesting form of sample to sample correlation. If you take >>> consecutive numbers from such a generator, form x-y pairs from them >>> and plot them, the points will all lay along diagonal lines and not >>> fill the field uniformly. Knuth gives some good examples of how to fix >>> this sample to sample correlation with shuffling. I've had a lot of >>> experience with making pseudo random number generators pass the >>> statistical requirements for state lotteries and gaming. >> >> One of the commonest congruels, used in a lot of DSP code I've seen, has >> zero randomness in the LSB. > > Well, strictly speaking no PRNG has any randomness in it. If it can be > computed, it ain't random :-). > >> Its goes 10101010 through successive >> samples. This doesn't matter much most of the time, because the rest of >> the 16 bits are pretty good. > > I once used a very simple but fast 32bit linear congruential PRNG > (with parameters values suggested by Knuth). I wanted to use only a > subset of the bits (I think the 10 least significant) to generate > integers uniform at random from 0 - 1023. However, when I plotted > consecutive values, nice diagonal stripes became visible. The numbers > also failed a chi^2 test miserably. In the end I used all 32bits to > generate 10 somewhat more random bits, which passed my simple > requirements and was still damn fast.By using the bottom 10 bits you effectively forced the generator to be a 10 bit generator with a correspondingly short cycle length. It is very hard for such a short generator to pass other than tests which are suitable for such a short cycle. It would look poor, or worse, when tested as if it were of a longer cycle length. As you found you should have used the top 10 bits.>> I've seen the LSB tested as a random logic >> value, though. :-)When carried to the extreme of just the bottom bit you get a cycle length of 2. So it must alternate.> Nobody's perfect. > > :-) > > Regards, > Andor >> >> Steve- Zitierten Text ausblenden - >> >> - Zitierten Text anzeigen -
Reply by ●August 3, 20072007-08-03
Gordon Sande wrote: ...> When carried to the extreme of just the bottom bit you get a cycle > length of 2. So it must alternate.Gordon, you surprise me. If the algorithm reversed the bits end for end before returning the number and only the (new) LSB were chosen, that would clearly not have a cycle length of 2. Jerry -- Engineering is the art of making what you want from things you can get. ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
Reply by ●August 3, 20072007-08-03
On 2007-08-03 12:29:20 -0300, Jerry Avins <jya@ieee.org> said:> Gordon Sande wrote: > > ... > >> When carried to the extreme of just the bottom bit you get a cycle >> length of 2. So it must alternate. > > Gordon, you surprise me. If the algorithm reversed the bits end for end > before returning the number and only the (new) LSB were chosen, that > would clearly not have a cycle length of 2. > > JerryIt was stated as a congruential gnerator which you just ruled out. The GF(2^p) generators, like you the one mention, are not the same as congruential generators mod 2^p. Such are the details that matter. All too easy to miss and ignore.
Reply by ●August 3, 20072007-08-03
On 3 Aug., 16:59, Gordon Sande <g.sa...@worldnet.att.net> wrote:> On 2007-08-03 11:34:51 -0300, Andor <andor.bari...@gmail.com> said: > > > > > > > On 3 Aug., 13:34, Steve Underwood <ste...@dis.org> wrote: > >> Clay wrote: > >>>> By the way, I think Vladimir knows this. :-) > > >>>> Steve- Hide quoted text - > > >>> I think I may have misunderstood Vladimir's comment about "why add up > >>> 12 numbers ... " > > >>> I answered the part about why "12" is sometimes done - to get a > >>> standard normal (approximation). Certainly when using more or fewer > >>> numbers in the sum, one just divides by the variance to make it > >>> standard normal - the sum of 12 part avoids this simple correction. As > >>> they say there is more than one way to skin a cat. > > >>> About linear congruence pseudo random number generators - they have an > >>> interesting form of sample to sample correlation. If you take > >>> consecutive numbers from such a generator, form x-y pairs from them > >>> and plot them, the points will all lay along diagonal lines and not > >>> fill the field uniformly. Knuth gives some good examples of how to fix > >>> this sample to sample correlation with shuffling. I've had a lot of > >>> experience with making pseudo random number generators pass the > >>> statistical requirements for state lotteries and gaming. > > >> One of the commonest congruels, used in a lot of DSP code I've seen, has > >> zero randomness in the LSB. > > > Well, strictly speaking no PRNG has any randomness in it. If it can be > > computed, it ain't random :-). > > >> Its goes 10101010 through successive > >> samples. This doesn't matter much most of the time, because the rest of > >> the 16 bits are pretty good. > > > I once used a very simple but fast 32bit linear congruential PRNG > > (with parameters values suggested by Knuth). I wanted to use only a > > subset of the bits (I think the 10 least significant) to generate > > integers uniform at random from 0 - 1023. However, when I plotted > > consecutive values, nice diagonal stripes became visible. The numbers > > also failed a chi^2 test miserably. In the end I used all 32bits to > > generate 10 somewhat more random bits, which passed my simple > > requirements and was still damn fast. > > By using the bottom 10 bits you effectively forced the generator > to be a 10 bit generator with a correspondingly short cycle length.Damn, I didn't know that :-). But now that you mention it, that's an obvious trait of linear congruential prngs because (a r + m) % p = ((a % p) (r % p) + m % p ) % p.> It is very hard for such a short generator to pass other than > tests which are suitable for such a short cycle. It would look > poor, or worse, when tested as if it were of a longer cycle length.Already one cycle looke pretty bad, where the diagnoal streaks were clearly visible. The formula is r_new = 1664525 r_old + 1013904223 % 2^32.> > As you found you should have used the top 10 bits.My hope was to be able to use 3 x 10 bits from the 32bits to generate three random integers in the range 0 - 1023. In the end, I just used all of the bits instead of only 10.> > >> I've seen the LSB tested as a random logic > >> value, though. :-) > > When carried to the extreme of just the bottom bit you get a cycle > length of 2. So it must alternate.Could also be constant with the wrong choices of parameters :-). Regards, Andor
Reply by ●August 3, 20072007-08-03
On 2007-08-03 13:04:11 -0300, Andor <andor.bariska@gmail.com> said:> On 3 Aug., 16:59, Gordon Sande <g.sa...@worldnet.att.net> wrote: >> On 2007-08-03 11:34:51 -0300, Andor <andor.bari...@gmail.com> said: >> >> >> >> >> >>> On 3 Aug., 13:34, Steve Underwood <ste...@dis.org> wrote: >>>> Clay wrote: >>>>>> By the way, I think Vladimir knows this. :-) >> >>>>>> Steve- Hide quoted text - >> >>>>> I think I may have misunderstood Vladimir's comment about "why add up >>>>> 12 numbers ... " >> >>>>> I answered the part about why "12" is sometimes done - to get a >>>>> standard normal (approximation). Certainly when using more or fewer >>>>> numbers in the sum, one just divides by the variance to make it >>>>> standard normal - the sum of 12 part avoids this simple correction. As >>>>> they say there is more than one way to skin a cat. >> >>>>> About linear congruence pseudo random number generators - they have an >>>>> interesting form of sample to sample correlation. If you take >>>>> consecutive numbers from such a generator, form x-y pairs from them >>>>> and plot them, the points will all lay along diagonal lines and not >>>>> fill the field uniformly. Knuth gives some good examples of how to fix >>>>> this sample to sample correlation with shuffling. I've had a lot of >>>>> experience with making pseudo random number generators pass the >>>>> statistical requirements for state lotteries and gaming. >> >>>> One of the commonest congruels, used in a lot of DSP code I've seen, has >>>> zero randomness in the LSB. >> >>> Well, strictly speaking no PRNG has any randomness in it. If it can be >>> computed, it ain't random :-). >> >>>> Its goes 10101010 through successive >>>> samples. This doesn't matter much most of the time, because the rest of >>>> the 16 bits are pretty good. >> >>> I once used a very simple but fast 32bit linear congruential PRNG >>> (with parameters values suggested by Knuth). I wanted to use only a >>> subset of the bits (I think the 10 least significant) to generate >>> integers uniform at random from 0 - 1023. However, when I plotted >>> consecutive values, nice diagonal stripes became visible. The numbers >>> also failed a chi^2 test miserably. In the end I used all 32bits to >>> generate 10 somewhat more random bits, which passed my simple >>> requirements and was still damn fast. >> >> By using the bottom 10 bits you effectively forced the generator >> to be a 10 bit generator with a correspondingly short cycle length. > > Damn, I didn't know that :-). But now that you mention it, that's an > obvious trait of linear congruential prngs because > > (a r + m) % p = ((a % p) (r % p) + m % p ) % p.Give the man a cigar!>> It is very hard for such a short generator to pass other than >> tests which are suitable for such a short cycle. It would look >> poor, or worse, when tested as if it were of a longer cycle length. > > Already one cycle looke pretty bad, where the diagnoal streaks were > clearly visible. The formula is r_new = 1664525 r_old + 1013904223 % > 2^32. > >> >> As you found you should have used the top 10 bits. > > My hope was to be able to use 3 x 10 bits from the 32bits to generate > three random integers in the range 0 - 1023. In the end, I just used > all of the bits instead of only 10.For the top 10 it would be like mod 2^32, for the second top 10 it would be like mod 2^22 and for the next top 10 it would be like 2^12. You did the analysis above but forgot to apply it. So sticking with the top 10 was sensible.>>>> I've seen the LSB tested as a random logic >>>> value, though. :-) >> >> When carried to the extreme of just the bottom bit you get a cycle >> length of 2. So it must alternate. > > Could also be constant with the wrong choices of parameters :-). > > Regards, > Andor
Reply by ●August 3, 20072007-08-03
Gordon Sande wrote:> On 2007-08-03 12:29:20 -0300, Jerry Avins <jya@ieee.org> said: > >> Gordon Sande wrote: >> >> ... >> >>> When carried to the extreme of just the bottom bit you get a cycle >>> length of 2. So it must alternate. >> >> Gordon, you surprise me. If the algorithm reversed the bits end for >> end before returning the number and only the (new) LSB were chosen, >> that would clearly not have a cycle length of 2. >> >> Jerry > > It was stated as a congruential gnerator which you just ruled out. > > The GF(2^p) generators, like you the one mention, are not the same as > congruential generators mod 2^p. > > Such are the details that matter. All too easy to miss and ignore.Then the two lowest bits together have a cycle length of 4? Jerry -- Engineering is the art of making what you want from things you can get. ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
Reply by ●August 3, 20072007-08-03
On 2007-08-03 15:12:30 -0300, Jerry Avins <jya@ieee.org> said:> Gordon Sande wrote: >> On 2007-08-03 12:29:20 -0300, Jerry Avins <jya@ieee.org> said: >> >>> Gordon Sande wrote: >>> >>> ... >>> >>>> When carried to the extreme of just the bottom bit you get a cycle >>>> length of 2. So it must alternate. >>> >>> Gordon, you surprise me. If the algorithm reversed the bits end for end >>> before returning the number and only the (new) LSB were chosen, that >>> would clearly not have a cycle length of 2. >>> >>> Jerry >> >> It was stated as a congruential gnerator which you just ruled out. >> >> The GF(2^p) generators, like you the one mention, are not the same as >> congruential generators mod 2^p. >> >> Such are the details that matter. All too easy to miss and ignore. > > Then the two lowest bits together have a cycle length of 4? > > JerryDepends on the multiplier and the additive constant. In general yes but for the common cases running around wild no. The additive constant of zero, which is very common, is enough for no. See Knuth or some other reliable source for the number theory details.
