Screenshot instructions:
Windows
Mac
Red Hat Linux
Ubuntu
Click URL instructions:
Rightclick on ad, choose "Copy Link", then paste here →
(This may not be possible with some types of ads)
From: Stephen Waits <steve@wa...>  20070228 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 
From: <robin_green@pl...>  20070227 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 <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^199371 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.hiroshimau.ac.jp/~mmat/MT/SFMT/index.html http://www.math.sci.hiroshimau.ac.jp/~mmat/MT/VERSIONS/CLANG/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"? > 
From: Jon Watte <hplus@mi...>  20070227 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^199371 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 startup (the cost of seeding) vs successive numbers? Cheers, / h+ 
From: <robin_green@pl...>  20070302 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^199371 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 startup (the cost of seeding) vs > successive numbers? > 
From: Jon Watte <hplus@mi...>  20070303 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 startup costs are not great, as you reseed (and thus restartup) too often. Cheers, / h+ 
From: <robin_green@pl...>  20070303 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 <robin_green@...> To: Game Development Algorithms If you are going to reseed all the time, why not go with a hashing or quasirandom function instead of a random series generator? You'll get the "random" values you need and with perfect reproducibility. One family of quasirandom 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 
From: Jonathan B. <jon@nu...>  20070303 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 nonrandom 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 startup costs are not > great, as you reseed (and thus restartup) 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 surveysand earn cash > http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > 
From: Stephen Waits <steve@wa...>  20070228 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 
From: Thatcher Ulrich <tu@tu...>  20070228 12:57:20

Did you look at Marsaglia's complementarymultiplywithcarry? 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@... <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 <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^199371 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.hiroshimau.ac.jp/~mmat/MT/SFMT/index.html > http://www.math.sci.hiroshimau.ac.jp/~mmat/MT/VERSIONS/CLANG/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 surveysand earn cash > http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > 
Sign up for the SourceForge newsletter:
No, thanks