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

[Thatcher U. <tu...@tu...>]

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, rob...@pl...
<rob...@pl...> 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 <rob...@pl...>
> 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
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_id=6188
>
>