## Re: [Algorithms] [Fwd: [Fwd: Re: Random number generation that looks better than MS's rand() for vis work?]]

 Re: [Algorithms] [Fwd: [Fwd: Re: Random number generation that looks better than MS's rand() for vis work?]] From: Stephen Waits - 2007-02-28 04:19:23 ```On Feb 27, 2007, at 10:53 AM, robin_green@... wrote: > MT = 71 cycles Is this an average? Every MT implementation I've seen (doesn't everyone just use the reference implementation?) stores a block at a time, refilling when depleted. Is that what yours does too? If so, I'd like to see the min/max cycle counts too. --Steve ```

 [Algorithms] [Fwd: [Fwd: Re: Random number generation that looks better than MS's rand() for vis work?]] From: - 2007-02-27 19:04:38 ```Resending from a different server. - Robin Green. -------- Original Message -------- Subject: Re: [Algorithms] Random number generation that looks better Date: Tue, 06 Feb 2007 10:13:06 -0800 From: Robin Green To: Game Development Algorithms Many implementations of rand() in ANSI C libraries are direct copies of the K&R documentation that uses a linear congruent generator of the form: rand{i+1} = (a * rand{i} + c) % m where a = 1103515245 c = 12345 m = 2^15 (from http://members.cox.net/srice1/random/random4.html#CRAN, see also Numerical Recipes in C, p276) This generator with the suspiciously arbitrary "12345" has been shown to have poor randomness, especially in the lower bits (making expressions of the form "rand() % N" especially bad) and especially when ported to longer word lengths. This is why for the PS3 SDK we provided two hand optimized random number generators, one TT800 generator (has period of 2^800 and uses 33 words of storage) and one Mersenne Twister (period of 2^19937-1 and around 650 words of storage). Our timings for C implementations on the SPU were: Dinkumware = 160 cycles tt800 = 93 cycles MT = 71 cycles http://en.wikipedia.org/wiki/Mersenne_twister http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/C-LANG/tt800.c - Robin Green SCE US R&D Megan Fox wrote: > We've hit a snag wherein the Microsoft rand() is simply ineffective at > making a properly chaotic result - it has patterning that's clear to > the human eye. It's intrinsic to rand(), and has absolutely nothing > to do with our code. Damn the human brain's pattern recognition! > > Anyways, is there any particular algorithm known to have the best or > most organic distribution? Or am I honestly reduced to testing my > list of them, over and over, until we finally decide one looks "the > best"? > ```
 Re: [Algorithms] [Fwd: [Fwd: Re: Random number generation that looks better than MS's rand() for vis work?]] From: Jon Watte - 2007-02-27 22:44:53 ``` robin_green@... wrote: > This is why for the PS3 SDK we provided two hand optimized random number > generators, one TT800 generator (has period of 2^800 and uses 33 words > of storage) and one Mersenne Twister (period of 2^19937-1 and around 650 > words of storage). Our timings for C implementations on the SPU were: > > Dinkumware = 160 cycles > tt800 = 93 cycles > MT = 71 cycles > This is useful! Do you have data on the cost of start-up (the cost of seeding) vs successive numbers? Cheers, / h+ ```
 Re: [Algorithms] [Fwd: [Fwd: Re: Random number generation that looks better than MS's rand() for vis work?]] From: - 2007-03-02 18:50:22 ```These were average numbers from runs of, maybe, 10M values. On startup the MT algorithm makes itself a large seed table which it reads successive values from and every 600 values there is a long restart calculation. The TT800 does the same but restarts every [handwave] 20 values or so. Sorry, but I have no more details than that as the research was done several years ago by a coworker here. - Robin Green. Jon Watte wrote: > > robin_green@... wrote: >> This is why for the PS3 SDK we provided two hand optimized random number >> generators, one TT800 generator (has period of 2^800 and uses 33 words >> of storage) and one Mersenne Twister (period of 2^19937-1 and around 650 >> words of storage). Our timings for C implementations on the SPU were: >> >> Dinkumware = 160 cycles >> tt800 = 93 cycles >> MT = 71 cycles >> > > This is useful! > > Do you have data on the cost of start-up (the cost of seeding) vs > successive numbers? > ```
 Re: [Algorithms] [Fwd: [Fwd: Re: Random number generation that looks better than MS's rand() for vis work?]] From: Jon Watte - 2007-03-03 00:55:33 ``` robin_green@... wrote: > On startup the MT algorithm makes itself a large seed table which it > reads successive values from and every 600 values there is a long > restart calculation. The TT800 does the same but restarts every > [handwave] 20 values or so. > OK, thanks! The question came up because the original poster wanted a random generator where she could seed it with some value, and then pull out between 1 and 10 random numbers. I presume the idea is to procedurally generate some kind of geometry, features, or levels, possibly based on coordinates or some parameterization. For those kind of uses, generators with large start-up costs are not great, as you re-seed (and thus re-start-up) too often. Cheers, / h+ ```
 Re: [Algorithms] [Fwd: [Fwd: Re: Random number generation that looks better than MS's rand() for vis work?]] From: - 2007-03-03 01:09:41 ```Jon Watte wrote: > > OK, thanks! > > The question came up because the original poster wanted a random > generator where she could seed it with some value, and then pull out > between 1 and 10 random numbers. Which is why my (lost, enclosed) reply was to use a hashing function or something quasi random. - Robin Green SCE US R&D -------- Original Message -------- Subject: Re: [Algorithms] Random number generation that looks better than MS's rand() for vis work? Date: Tue, 06 Feb 2007 11:43:31 -0800 From: Robin Green To: Game Development Algorithms If you are going to reseed all the time, why not go with a hashing or quasi-random function instead of a random series generator? You'll get the "random" values you need and with perfect reproducibility. One family of quasi-random functions that have been proven good for visually displayed data are the "low discrepancy sampling points", a.k.a. the Hammersley and Halton point sets: http://www.cse.cuhk.edu.hk/~ttwong/papers/udpoint/udpoints.html Given an index you get a point back, simple as that. It all comes down to reversing the digits of a number (in some base) around the decimal point and the strange numerical properties that this operation has. - Robin Green SCE US R&D ```
 Re: [Algorithms] [Fwd: [Fwd: Re: Random number generation that looks better than MS's rand() for vis work?]] From: Jonathan B. - 2007-03-03 02:39:36 ```For Braid I had a situation where I needed to seed a random number generator with a very specific seed and then get a handful of numbers from it, and do that many times per frame. I had a lot of problems with the LCG that I had usually used, generating really obvious / horrible patterns, etc. Tried stuff like Mersenne Twister but it was way too slow. Eventually found that the LCG from BCPL was good enough if I munged up the seed and then generated about 6 junk numbers before using any for real.... (Here's that particular LCG): { state = state * 2147001325 + 715136305; // BCPL generator // shuffle non-random bits to the middle, and xor to decorrelate with seed return 0x31415926 ^ ((state >> 16) + (state << 16)); } Jon Watte wrote: > robin_green@... wrote: > >> On startup the MT algorithm makes itself a large seed table which it >> reads successive values from and every 600 values there is a long >> restart calculation. The TT800 does the same but restarts every >> [handwave] 20 values or so. >> >> > > OK, thanks! > > The question came up because the original poster wanted a random > generator where she could seed it with some value, and then pull out > between 1 and 10 random numbers. I presume the idea is to procedurally > generate some kind of geometry, features, or levels, possibly based on > coordinates or some parameterization. > For those kind of uses, generators with large start-up costs are not > great, as you re-seed (and thus re-start-up) too often. > > Cheers, > > / h+ > > > ------------------------------------------------------------------------- > Take Surveys. Earn Cash. Influence the Future of IT > Join SourceForge.net's Techsay panel and you'll get the chance to share your > opinions on IT & business topics through brief surveys-and earn cash > http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > ```
 Re: [Algorithms] [Fwd: [Fwd: Re: Random number generation that looks better than MS's rand() for vis work?]] From: Stephen Waits - 2007-02-28 04:19:23 ```On Feb 27, 2007, at 10:53 AM, robin_green@... wrote: > MT = 71 cycles Is this an average? Every MT implementation I've seen (doesn't everyone just use the reference implementation?) stores a block at a time, refilling when depleted. Is that what yours does too? If so, I'd like to see the min/max cycle counts too. --Steve ```
 Re: [Algorithms] [Fwd: [Fwd: Re: Random number generation that looks better than MS's rand() for vis work?]] From: Thatcher Ulrich - 2007-02-28 12:57:20 ```Did you look at Marsaglia's complementary-multiply-with-carry? The periods are similar for similar data size (and the data size is parameterizable upwards and downwards), but the generator is incremental and pretty simple. I measure 18 cycles/number on my Pentium M (I have no idea how that compares to SPU). -T On 2/27/07, robin_green@... wrote: > > Resending from a different server. > > - Robin Green. > > -------- Original Message -------- > Subject: Re: [Algorithms] Random number generation that looks better > Date: Tue, 06 Feb 2007 10:13:06 -0800 > From: Robin Green > To: Game Development Algorithms > > Many implementations of rand() in ANSI C libraries are direct copies of > the K&R documentation that uses a linear congruent generator of the form: > > rand{i+1} = (a * rand{i} + c) % m > > where > > a = 1103515245 > c = 12345 > m = 2^15 > > (from http://members.cox.net/srice1/random/random4.html#CRAN, see also > Numerical Recipes in C, p276) > > This generator with the suspiciously arbitrary "12345" has been shown to > have poor randomness, especially in the lower bits (making expressions > of the form "rand() % N" especially bad) and especially when ported to > longer word lengths. > > This is why for the PS3 SDK we provided two hand optimized random number > generators, one TT800 generator (has period of 2^800 and uses 33 words > of storage) and one Mersenne Twister (period of 2^19937-1 and around 650 > words of storage). Our timings for C implementations on the SPU were: > > Dinkumware = 160 cycles > tt800 = 93 cycles > MT = 71 cycles > > http://en.wikipedia.org/wiki/Mersenne_twister > http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html > http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/C-LANG/tt800.c > > - Robin Green > SCE US R&D > > > Megan Fox wrote: > > We've hit a snag wherein the Microsoft rand() is simply ineffective at > > making a properly chaotic result - it has patterning that's clear to > > the human eye. It's intrinsic to rand(), and has absolutely nothing > > to do with our code. Damn the human brain's pattern recognition! > > > > Anyways, is there any particular algorithm known to have the best or > > most organic distribution? Or am I honestly reduced to testing my > > list of them, over and over, until we finally decide one looks "the > > best"? > > > > > > > > > ------------------------------------------------------------------------- > Take Surveys. Earn Cash. Influence the Future of IT > Join SourceForge.net's Techsay panel and you'll get the chance to share your > opinions on IT & business topics through brief surveys-and earn cash > http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > ```