   Mersenne Twister != Faster Than rand() (or so my test says)
  I''m by no means an uber programmer and I was reading up on random number generators and some said that rand() isn''t too hot.  So I looked around and found the Mersenne Twister.  It claims to be 4x faster than rand() and I mean, how slow can rand() really be?In no way do I say this isn''t true, but in my little demo, it sure isn''t =PUsing a completely unmodified version (source below), I get roughly 10x slower randomization with Mersenne Twister than I do rand().  Thats a pretty big difference.Heres the source for what I''m using:   #include <windows.h>#include <stdio.h>/* Period parameters */  #define N 624#define M 397#define MATRIX_A 0x9908b0dfUL   /* constant vector a */#define UPPER_MASK 0x80000000UL /* most significant w-r bits */#define LOWER_MASK 0x7fffffffUL /* least significant r bits */static unsigned long mt[N]; /* the array for the state vector  */static int mti=N+1; /* mti==N+1 means mt[N] is not initialized *//* initializes mt[N] with a seed */void init_genrand(unsigned long s){    mt[0]= s & 0xffffffffUL;    for (mti=1; mti<N; mti++) {   mt[mti] =(1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti);    /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */   /* In the previous versions, MSBs of the seed affect   */   /* only MSBs of the array mt[].    */   /* 2002/01/09 modified by Makoto Matsumoto   */   mt[mti] &= 0xffffffffUL;   /* for >32 bit machines */    }}/* initialize by an array with array-length *//* init_key is the array for initializing keys *//* key_length is its length *//*unsigned long init_key[], key_length;void init_by_array(init_key, key_length){    int i, j, k;    init_genrand(19650218UL);    i=1; j=0;    k = (N>key_length ? N : key_length);    for (; k; k--) {   mt = (mt ^ ((mt[i-1] ^ (mt[i-1] &gt;&gt; 30)) * 1664525UL))+ init_key[j] + j; // non linear   mt &= 0xffffffffUL; // for WORDSIZE &gt; 32 machines   i++; j++;   if (i&gt;=N) { mt[0] = mt[N-1]; i=1; }   if (j&gt;=key_length) j=0;    }    for (k=N-1; k; k–) {   mt = (mt ^ ((mt[i-1] ^ (mt[i-1] &gt;&gt; 30)) * 1566083941UL))- i; // non linear   mt &= 0xffffffffUL; // for WORDSIZE &gt; 32 machines   i++;   if (i&gt;=N) { mt[0] = mt[N-1]; i=1; }    }    mt[0] = 0x80000000UL; // MSB is 1; assuring non-zero initial array}*/</font><font color=gray>/* generates a random number on [0,0xffffffff]-interval */</font><font color=blue>unsigned</font> <font color=blue>long</font> genrand_int32(<font color=blue>void</font>){    <font color=blue>unsigned</font> <font color=blue>long</font> y;    <font color=blue>static</font> <font color=blue>unsigned</font> <font color=blue>long</font> mag01[<font color=purple>2</font>]={0x0UL, MATRIX_A};    <font color=gray>/* mag01[x] = x * MATRIX_A  for x=0,1 */</font>    <font color=blue>if</font> (mti &gt;= N) { <font color=gray>/* generate N words at one time */</font>   <font color=blue>int</font> kk;   <font color=blue>if</font> (mti == N+1)   <font color=gray>/* if init_genrand() has not been called, */</font>  init_genrand(5489UL); <font color=gray>/* a default initial seed is used */</font>   <font color=blue>for</font> (kk=0;kk&lt;N-M;kk++) {  y = (mt[<font color=purple>kk</font>]&UPPER_MASK)|(mt[<font color=purple>kk+1</font>]&LOWER_MASK);  mt[<font color=purple>kk</font>] = mt[<font color=purple>kk+M</font>] ^ (y &gt;&gt; 1) ^ mag01[<font color=purple>y & 0x1UL</font>];   }   <font color=blue>for</font> (;kk&lt;N-1;kk++) {  y = (mt[<font color=purple>kk</font>]&UPPER_MASK)|(mt[<font color=purple>kk+1</font>]&LOWER_MASK);  mt[<font color=purple>kk</font>] = mt[<font color=purple>kk+(M-N)</font>] ^ (y &gt;&gt; 1) ^ mag01[<font color=purple>y & 0x1UL</font>];   }   y = (mt[<font color=purple>N-1</font>]&UPPER_MASK)|(mt[<font color=purple>0</font>]&LOWER_MASK);   mt[<font color=purple>N-1</font>] = mt[<font color=purple>M-1</font>] ^ (y &gt;&gt; 1) ^ mag01[<font color=purple>y & 0x1UL</font>];   mti = 0;    } y = mt[<font color=purple>mti++</font>];    <font color=gray>/* Tempering */</font>    y ^= (y &gt;&gt; 11);    y ^= (y &lt;&lt; 7) & 0x9d2c5680UL;    y ^= (y &lt;&lt; 15) & 0xefc60000UL;    y ^= (y &gt;&gt; 18);    <font color=blue>return</font> y;}<font color=gray>/* generates a random number on [0,0x7fffffff]-interval */</font><font color=blue>long</font> genrand_int31(<font color=blue>void</font>){    <font color=blue>return</font> (<font color=blue>long</font>)(genrand_int32()&gt;&gt;1);}<font color=gray>/* generates a random number on [0,1]-real-interval */</font><font color=blue>double</font> genrand_real1(<font color=blue>void</font>){    <font color=blue>return</font> genrand_int32()*(1.0/4294967295.0);<font color=gray>/* divided by 2^32-1 */</font> }<font color=gray>/* generates a random number on [0,1)-real-interval */</font><font color=blue>double</font> genrand_real2(<font color=blue>void</font>){    <font color=blue>return</font> genrand_int32()*(1.0/4294967296.0);<font color=gray><font color=gray>/* divided by 2^32 */</font></font>}<font color=gray>/* generates a random number on (0,1)-real-interval */</font><font color=blue>double</font> genrand_real3(<font color=blue>void</font>){    <font color=blue>return</font> (((<font color=blue>double</font>)genrand_int32()) + 0.5)*(1.0/4294967296.0);<font color=gray><font color=gray>/* divided by 2^32 */</font></font>}<font color=gray>/* generates a random number on [0,1) with 53-bit resolution*/</font><font color=blue>double</font> genrand_res53(<font color=blue>void</font>) {<font color=blue>unsigned</font> <font color=blue>long</font> a=genrand_int32()&gt;&gt;5, b=genrand_int32()&gt;&gt;6;<font color=blue>return</font>(a*67108864.0+b)*(1.0/9007199254740992.0); } <font color=gray>/* These real versions are due to Isaku Wada, 2002/01/09 added */</font><font color=blue>int</font> main(<font color=blue>void</font>){const <font color=blue>int</font> iTestCount = 10000000;DWORD StartTime = 0;<font color=blue>unsigned</font> <font color=blue>int</font> iCounter = 0;<font color=blue>unsigned</font> <font color=blue>int</font> iValue = 0;<font color=gray>// Seed Before Test (pretty irrelevant to the test)</font>init_genrand(6); <font color=gray><font color=gray>// Uncomment To Switch</font></font>//srand(6); <font color=gray><font color=gray>// Uncomment To Switch</font></font><font color=gray>// Go Go Go!</font>StartTime = GetTickCount();<font color=blue>for</font>(iCounter = 0; iCounter &lt; iTestCount; iCounter++)iValue = genrand_int32(); <font color=gray><font color=gray>// Uncomment To Switch</font></font>//iValue = rand(); <font color=gray><font color=gray>// Uncomment To Switch</font></font>printf(<font color=darkred>"End Time: %d\n"</font>, GetTickCount() - StartTime);    <font color=blue>return</font> 0;}</font></pre><!–ENDSCRIPT–>I''m sure the test is horribly flawed, but I get roughly 2000ms with 10 million tests using Mersenne, and about 300ms with 10 million tests using rand().So whats the deal?  I thought this thing was supposed to be blazing fast.   
  Mersenne Twister claims to be 4 times faster than a particular implementation of rand. You''re evidently not using that one. ;  More importantly, speed is not the critical issue. Spread is. ;  rand()''s max number is often 2^16 and it''s period may be as short as 2^16! Whereas MT''s max number is often 2^32 and it''s period (for MT19937) is 2^19937 - 1. Slight difference..But I don''t know why they would claim it''s 4x faster than rand(). That''s a totally meaningless assertion because it entirely depends on the rand() implementation used.. I could have a rand() likeunsigned int x;unsigned int rand() { return ++x; }void srand(unsigned int seed) { x = seed; }  And I bet it would be a bit faster than any mersenne twister (AFAIK the standard doesn''t say what kind of random numbers rand() has to provide).But anyway, MT is good if you need good random numbers..See herehttp://www.boost.org/libs/random/index.htmlfor a comparison between random number generators (and implementations for them) ;  A favorite of mine is:init:a = 1140671485c = 12820163seed = anything but 0gen next number:seed = (seed * a + c) BitwiseAnd 0FFFFFFh..it has a period of 2^24-1 and produces 24-bit values..it was recomended by knuth..its insanely fastWhat more do you need?- Rockoon;quote:Original post by Anonymous Poster  A favorite of mine is:init:a = 1140671485c = 12820163seed = anything but 0gen next number:seed = (seed * a + c) BitwiseAnd 0FFFFFFh..it has a period of 2^24-1 and produces 24-bit values..it was recomended by knuth..its insanely fastWhat more do you need?- Rockoon It never changes...;  rand kind of sucks for a lot of things IMO. For instance, it''s lower bits aren''t as random as it''s upper bits. So, once I was doing something like this:random = rand() & 1;and I was getting a results like:00010000010000000010000000010000001Kind of sucked for something you want to have happen 50% of the time.MT works great though. ;quote:Original post by Beer Hunter  Mersenne Twister claims to be 4 times faster than a particular implementation of rand. You''re evidently not using that one.   That should be:One specific implementation of Mersenne Twister happened to be, on one occasion, faster than the specific implementation of rand on that computer. You''re not using the one which is claimed to be 4x as fast, that''s somewhere else on the MT page.  ;  I think the fastest random function you could have is a shift generator that operates at the natural word size of the machine, which might be what your rand()'s implementation just might be.My particular favorite is this generator... I found athttp://remus.rutgers.edu/~rhoads/Code/code.htmlmade a little bit of modification, but meh.static double seed =   91648253;static double max  = 2147483647;static double a    =    1389796;double random (){   seed *= a;   seed -= (int)(seed/max) * max;   return seed;}void rand_seed (int init){  if (init != 0) {seed = init;   } else {seed = 91648253;   }}  Its a fairly standard  Mn = Mn-1 * a + c (mod r) type generator, (Linear Congruential) but it doesn't have the (+ c) and I think it's period is (2^31)-1, since 2147483647 is a mersenne prime, but I never tested it myself.For picking lotto ticket numbers, go with the Twister.  For randomizing events and enemy behavior in a game, a LGC rand like the one I put up is great. And for software intermitency on microprocessors, use a linear shift generator.   [edited by - inmate2993 on February 18, 2004 9:57:39 PM];  A 10x slowdown with MT makes sense. It''s doing a heck of a lot more computations than rand() does. FYI here is the VC++ 6 implementation of rand()int __cdecl rand (   void   ){#ifdef _MT   _ptiddata ptd = _getptd();   return( ((ptd->_holdrand = ptd->_holdrand * 214013L  + 2531011L) >> 16) & 0x7fff );#else  /* _MT */   return(((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7fff);#endif  /* _MT */}  So as you see, there is really nothing going on except 1 add, 1 multiply, 1 shift. As opposed to Mersenne Twister which does a heck of a lot more computing. btw the _MT means multi-threaded not mersenne twister 