If RAND_MAX is 32767, and your range is 20000, and using modulus you don''t find that 16000 occurs twice as frequently as 17000, then your program has a bug in it. It''s that simple.
[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost ]
Generating a range of random integers
quote:Original post by ekenslow
If we were talking a crypto application I wouldn''t argue this at all, but for a game situation, particularly in a case where you need numbers in a small range such as 0-100, modulo is fine and faster than scaling by a factor of 2.5 on my machine.
That''s certainly your decision to make. Ever played Diablo 2? For months, the best kind of weapon for a certain class (exceptional lance) would never appear in the game. Other instances have appeared over the past where certain monsters always dropped certain items, etc. Wanna take bets that it was careless implementation of the random number generator? 10,000 users playing your game for hours on end _will_ uncover any minute mistake, especially in random number generation.
quote:
Again, my assumption is that speed is key, as for a game application.
If you''ve profiled your game and found that the random number generator is a significant bottleneck, I will concede that point as well.
quote:
Also again, if the exact distribution is that important you should probably be using a better RNG than CRT rand() anyway.
See, here''s where these "rand isn''t good enough" posts get frustrating for me. (I know this isn''t a "rand isn''t good enough" post, but it''s been cross-linked with one.) When you go about proving that rand _DOES_ generate a perfectly uniform output, and that aliasing the output _WILL_ skew your probability density, people say you''re being too nitpicky. Chaps my hide.
quote:Original post by scaught
Another thing to consider (besides just distribution) is the pattern (for lack of a better word) in which the numbers come out - for example, a random number generator is inherently faulty if each number generated is greater than the last until it wraps around some point, no matter how ''random'' the numbers it actually generates are (example, 1, 3, 4, 10, 11, 16, 18...).
What you''re talking about is the joint distribution between samples, or whether samples are independent from each other. One of the ways to evaluate this is the autocorrelation of a sequence, which is a plot of power verses lag. Assuming you have a sequence of N samples, lag 0 is the sum of the product of every sample:
x(0)*x(0) + x(1)*x(1) + ... + x(N)*x(N)
Lag 1 is the sum of all samples that are 1 unit apart:
x(0)*x(1) + x(1)*x(2) + ... + x(N-1)*x(N)
Lag 2 is the sum of all samples that are 2 units apart:
x(0)*x(2) + x(1)*x(3) + ... + x(N-2)*x(N)
etc., etc.
A random sequence of any zero-mean distribution should have a near-zero autocorrelation with a single spike at lag 0 (being the variance of the random process). (You could use this to evaluate rand since it has a known range by plotting the autocorrelation of (rand() - RAND_MAX/2), which would make it a zero-mean process.) A perfect Pseudo-random number generator would have peaks at lags corresponding to the sequence''s period (2^32 in rand ()''s case). I haven''t looked at rand''s autocorrelation, but I''m just mentioning it for those who haven''t heard.
In the case of the not-so-random function you mention, the autocorrelation would have been an increasing function with each lag--decidedly non-random.
quote:Original post by ekenslow
in a case where you need numbers in a small range such as 0-100, modulo is fine and faster than scaling by a factor of 2.5 on my machine.
Since when is modulo faster?
(1) rand()%100 : uses div, very slow
(2) rand()*100/(RAND_MAX+1) : uses mul and bitshifting, both quite fast operations
I did some tests too. I.e. running through a huge loop that uses rand() on each iteration, with either method (1) or (2)
I compiled on MSVC 6.0 with full optimizations, computer is Athlon 700 MHz.
(1) time elapsed: 7,3 seconds
(2) time elapsed: 2,0 seconds
So the modulo method is 3,6 times slower than the scaling method.
And if you do an inline function like
inline int rnd(int a) { return rand()*a/(RAND_MAX+1); } it shouldn't be too awkward to use either (and it is still as fast).
Edited by - civguy on February 22, 2002 8:01:25 AM
I''ve been using a version of the Mersenne Twister that I''ve wrapped up into a C++ class. I present it here as an alternative to rand(). I have been able to generate 10,000,000 random numbers in a range between 1 and 25 in about 0.28 seconds. That''s plenty fast and the distribution is completely satisfactory.
I''ve removed the comments from the original implementor as they
were very lengthy and you can find info for the MT anywhere on the web
Here''s the code;
My contribution to the code was to wrap it up into a C++ class and add D##() functions to the interface.
Give it a try...
Dave "Dak Lozar" Loeser
here''s a test of the generator
Dave "Dak Lozar" Loeser
I''ve removed the comments from the original implementor as they
were very lengthy and you can find info for the MT anywhere on the web
Here''s the code;
// RANDOM.H - The interface for CRandomMT#if !defined(RANDOM_GENERATOR_INCLUDED)#define RANDOM_GENERATOR_INCLUDED#if _MSC_VER > 1000#pragma once#endif // _MSC_VER > 1000#include <Windows.h>#include <math.h>//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%// uint32 must be an unsigned integer type capable of holding at least 32// bits; exactly 32 should be fastest, but 64 is better on an Alpha with// GCC at -O3 optimization so try your options and see what''s best for you//typedef unsigned long uint32;const int N = 624; // I replaced the #defines for these with const valuesconst int M = 397;const int K = 0x9908B0DFU;#define hiBit(u) ((u) & 0x80000000U) // mask all but highest bit of u#define loBit(u) ((u) & 0x00000001U) // mask all but lowest bit of u#define loBits(u) ((u) & 0x7FFFFFFFU) // mask the highest bit of u#define mixBits(u, v) (hiBit(u)|loBits(v)) // move hi bit of u to hi bit of vclass CRandomMT{ uint32 state[N+1]; // state vector + 1 extra to not violate ANSI C uint32 *next; // next random value is computed from here int left; // can *next++ this many times before reloading public: CRandomMT(); ~CRandomMT(){}; void SeedMT(uint32 seed); int RandomMax(int max); int RandomRange(int lo, int hi); int RollDice(int face, int number_of_dice); int D6(int die_count) { return RollDice(6,die_count); } int D8(int die_count) { return RollDice(8,die_count); } int D10(int die_count) { return RollDice(10,die_count); } int D12(int die_count) { return RollDice(12,die_count); } int D20(int die_count) { return RollDice(20,die_count); } int D25(int die_count) { return RollDice(25,die_count); } inline uint32 RandomMT(void);private: uint32 ReloadMT(void);};#endif //RANDOM_GENERATOR_INCLUDED #include "Random.h"CRandomMT::CRandomMT(){ left = -1; SeedMT(4357U);}void CRandomMT::SeedMT(uint32 seed) { register uint32 x = (seed | 1U) & 0xFFFFFFFFU, *s = state; register int j; for(left=0, *s++=x, j=N; --j; *s++ = (x*=69069U) & 0xFFFFFFFFU); }uint32 CRandomMT::ReloadMT(void) { register uint32 *p0=state, *p2=state+2, *pM=state+M, s0, s1; register int j; if(left < -1) SeedMT(4357U); left=N-1, next=state+1; for(s0=state[0], s1=state[1], j=N-M+1; --j; s0=s1, s1=*p2++) *p0++ = *pM++ ^ (mixBits(s0, s1) >> 1) ^ (loBit(s1) ? K : 0U); for(pM=state, j=M; --j; s0=s1, s1=*p2++) *p0++ = *pM++ ^ (mixBits(s0, s1) >> 1) ^ (loBit(s1) ? K : 0U); s1=state[0], *p0 = *pM ^ (mixBits(s0, s1) >> 1) ^ (loBit(s1) ? K : 0U); s1 ^= (s1 >> 11); s1 ^= (s1 << 7) & 0x9D2C5680U; s1 ^= (s1 << 15) & 0xEFC60000U; return(s1 ^ (s1 >> 18)); }inline uint32 CRandomMT::RandomMT(void) { uint32 y; if(--left < 0) return(ReloadMT()); y = *next++; y ^= (y >> 11); y ^= (y << 7) & 0x9D2C5680U; y ^= (y << 15) & 0xEFC60000U; return(y ^ (y >> 18)); }int CRandomMT::RandomMax(int max){ return((RandomMT()%max));}int CRandomMT::RandomRange(int lo, int hi){ // This is a recursive function int num = abs(RandomMT()); int mod = (hi - lo + 1) + lo; int rv = (num % mod); if(rv == 0) { rv = RandomRange(lo,hi); } return(rv);}int CRandomMT::RollDice(int face, int number_of_dice){ int roll = 0; for(int loop=0; loop < number_of_dice; loop++) { roll += (RandomRange(1,face)); } return roll;} My contribution to the code was to wrap it up into a C++ class and add D##() functions to the interface.
Give it a try...
Dave "Dak Lozar" Loeser
here''s a test of the generator
#include "Random.h"#define NUMBEROFROLLS 100000int main(int argc, char* argv[]){ CRandomMT mt; printf("Generating %ld random numbers...\n",NUMBEROFROLLS*10); DWORD start = GetTickCount(); for(int j=0; j<NUMBEROFROLLS; j++) { mt.D25(1); mt.D25(1); mt.D25(1); mt.D25(1); mt.D25(1); mt.D25(1); mt.D25(1); mt.D25(1); mt.D25(1); mt.D25(1); mt.D25(1); //printf(" %lu%s", (unsigned long) mt.D25(1), (j%7)==6 ? "\n" : " "); } DWORD end = GetTickCount(); printf("%d random numbers generated in %f seconds\n",NUMBEROFROLLS*10,(double)(end-start)/1000); return 0;} Dave "Dak Lozar" Loeser
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
