• Advertisement

Archived

This topic is now archived and is closed to further replies.

fast random numbers

This topic is 6521 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I use the modulus operator alot (almost every frame) to generate random numbers, e.g.: // 0 to n-1 srand((unsigned)time(NULL)); num = rand() % n; And I was wondering if there was a faster way to do random numbers without using the modulus? I know you can substitute % with & (n-1) for powers of two, but I need something that can do any number. Rasta

Share this post


Link to post
Share on other sites
Advertisement
Are you calling srand() every frame? You should only call it ONCE during the entire game. If you call it every frame, your numbers won't "look" as random as they should if you only called it once. Calling it every frame will probably make your game much slower.

I don't think ther's any need to optimize the modulus operator, it's pretty fast

/. Muzzafarath

Edited by - Muzzafarath on 4/14/00 2:35:50 AM

Share this post


Link to post
Share on other sites
Yeah, srand() should be called just once per game (I''m surprised at how many people make this mistake... is it badly documented?) and modulus is only significantly slow when you''re doing it once per pixel, or per vertex, or whatever. There are hardly any functions in the C/C++ libraries where calling it once per frame would make any significant difference. qsort(), perhaps. Don''t worry about optimisation until you know where the bottleneck is!

Share this post


Link to post
Share on other sites
A faster and better PRNG is the Mersenne Twister. Search for that on Google.com or your favorite search engine.

As for using something faster than the modulus operator, I wouldn''t bother worrying about that. If your program is running slow, it''s probably not the modulus.

---- --- -- -
Blue programmer needs food badly. Blue programmer is about to die!

Share this post


Link to post
Share on other sites
There is another problem with the modulo however. If you take a random number between 0 and RAND_MAX then you will not get an even distribution if you do modulo N unless RAND_MAX modulo N equals 1. And that is very often not the case. I could go into detail why this is but I''d have to think for that and I''m pretty tired right now . If somebody really wants to know then reply and I''ll reply with the why.

So if you want an even distribution of numbers between 0 and N then this is the best (and only) way:

(rand() / RAND_MAX) * N;

This might be slower but it''s the only way . (Unless ofcourse RANDMAX modulo N equals 1 ofcourse)

Oh and you do indeed only need to call srand only once.

Jaap Suter

Share this post


Link to post
Share on other sites
in order to get a random number quickly you could AND the number with a 2 to the power of something-1...e.g.

if you want to do

randnum = rand()%256; // since 256 = 2^8

you ccan use the following instead, which is a hell of a lot faster

randnum = rand()&255;

get the idea?

now, you cant always use this optimization, but when possible, use it...

Good Luck!

..-=ViKtOr=-..

Share this post


Link to post
Share on other sites
quote:
Original post by s9801758

There is another problem with the modulo however. If you take a random number between 0 and RAND_MAX then you will not get an even distribution if you do modulo N unless RAND_MAX modulo N equals 1. And that is very often not the case. I could go into detail why this is but I''d have to think for that and I''m pretty tired right now . If somebody really wants to know then reply and I''ll reply with the why.

So if you want an even distribution of numbers between 0 and N then this is the best (and only) way:

(rand() / RAND_MAX) * N;

This might be slower but it''s the only way . (Unless ofcourse RANDMAX modulo N equals 1 ofcourse)

Oh and you do indeed only need to call srand only once.



Don''t take this as a flame, it''s not. But there are three things I can correct:

First, you are right about modulo not creating a even distribution. The only time you will get an even distribution is if RANDMAX % N == (N-1). Not 1. But you were right; if this is not the case, then lower numbers have a slightly higher probability of occurring.

Second, (rand() / RAND_MAX) * N is probably going to give you zero, always. Why? Because both rand() and RAND_MAX are unsigned int, and rand() will not be larger than RAND_MAX. Integer division like this will always generate zero, so you need something like this:

int value = (rand() / float(RAND_MAX)) * N;

Third, this doesn''t solve the problem of uneven distribution. The problem is mapping M items in your domain to N items in the range. When N does not divide into M evenly, then your results are weighted to one side. Dividing by RAND_MAX then multiplying by N is deceptive. Looks like it should solve the problem, but you''re still mapping M items to N items. The difference is that rather than having the low items of your range slightly more frequent, those more frequent items are scattered across the range.

Only method I''ve ever thought to use to fix this is by using an if...else statement and reject certain items from the domain such that M is evenly divisible by N. But there might be better ways that this.


---- --- -- -
Blue programmer needs food badly. Blue programmer is about to die!

Share this post


Link to post
Share on other sites
quote:
Original post by Gladiator
if you want to do

randnum = rand()%256; // since 256 = 2^8

you ccan use the following instead, which is a hell of a lot faster

randnum = rand()&255;




Actually, if you have a modern compiler (and probably even with plenty of non-modern compilers), you don''t gain anything by doing this. In fact, the compiler will be smart enough to do exactly this on its own.

You are usually better off writing your code so that it is readable, understandable, and logical rather than trying to come up with little tricks. Odds are that the compiler knows all those tricks, and trying to implement them yourself might actually make things worse (the compiler knows many more optimizations that you do, and by trying to do its work, you may "confuse" it).




---- --- -- -
Blue programmer needs food badly. Blue programmer is about to die!

Share this post


Link to post
Share on other sites
I like to clarify what's going on for those who are confused. You're basically are trying to get a random number between 0 and 10 for example. We can get value 10 only when the random number becomes 32,768 or is equal to RAND_MAX. Since in our equation we have (rand()/RAND_MAX) * 10 = (32,768/RAND_MAX) * 10 = 10. Let's find a random number that will give us a 1.

So (x/32,768) * 10 = 1 or x/32,768 = 1/10 or
x = 32,768 * 0.1 that's equal to 3276.8 or 3276 in computer terms So you'll be getting zeros and ones for all random numbers that fall between 0 and 3,276. Then you'll be getting values between a 1 and 2 for all random numbers that fall between 3,276 and (3,276 * 2) and so on and so on...

I don't know how trully random numbers you'll be getting but consider this: If you seed the random number generator once per game with the time value ticking since 1970, the generator could/will return the same sequence of random numbers after couple of hundred frames have passed. I mean you could be getting: 1, 44, 55, 66 then after a while this sequence would repeat, but if you reseed the generator after few frames with a random value(perhaps with the last one obtained) this sequence would never repeat during the game play. If anyone knows more please let me know.

Jerry

Edited by - JD on 4/14/00 9:31:45 PM

Edited by - JD on 4/14/00 9:35:31 PM

Edited by - JD on 4/14/00 11:47:27 PM

Share this post


Link to post
Share on other sites
Dude, are you kidding me? The processor is capable of performing 250 million operations per second, and u''re worried about the modulus? You need to perform thousands of operations to draw, thousands for AI, etc, etc, which adds up to millions per frame. Modulus is probably not more then 5 operations. I don''t know how the distribution will go, but if u''re looking for optimizations, don''t bother trying to oprimize this. It''s not even remotely worth ur time.

Share this post


Link to post
Share on other sites
Ok, I made a little test program that uses (rand()%99)+1 to make a random number between 1 and 100, loops it a couple of million times and then calculates the average... it's VERY close to 50... (wich it should be) so i dont understand whats wrong w/ using the mod...

heres the source:


#include
#include


int main()
{
time_t t;
int i,j;
unsigned long temp=0;
float final[10], abs_final;


srand((unsigned int) (time(&t)));
clrscr();
for(i=0; i<10; i++)
{
for(j=0; j<10000000; j++)
temp+=(rand()%99)+1;
final =(float)temp/10000000;
printf("%d. %f\n",i,final);
temp=0;
}

abs_final= (final[0]+final[1]+
final[2]+final[3]+
final[4]+final[5]+
final[6]+final[7]+
final[8]+final[9])/10;

printf("\n\nAbsoulte final number iiiiis.... %f\n",abs_final);
printf("(btw. your computer has just completed 100000000 rand calls...)\n");
}


plz. compile it and try it urselfs!
(select 'edit message' to get the src w/ all chars...)



========================
Game project(s):
www.fiend.cjb.net

Edited by - JonatanHedborg on 4/16/00 5:53:02 PM

Share this post


Link to post
Share on other sites
quote:
Original post by mossmoss

[quote] Original post by Gladiator
if you want to do

randnum = rand()%256; // since 256 = 2^8

you ccan use the following instead, which is a hell of a lot faster

randnum = rand()&255;




Actually, if you have a modern compiler (and probably even with plenty of non-modern compilers), you don''t gain anything by doing this. In fact, the compiler will be smart enough to do exactly this on its own.

You are usually better off writing your code so that it is readable, understandable, and logical rather than trying to come up with little tricks. Odds are that the compiler knows all those tricks, and trying to implement them yourself might actually make things worse (the compiler knows many more optimizations that you do, and by trying to do its work, you may "confuse" it).




---- --- -- -
Blue programmer needs food badly. Blue programmer is about to die!


Not so!!

You should never trust the compiler. You''ll be better off implementing it yourself, then thinking that the compiler will parse it correcly and everything... If you don''t know how toprogram well, you''ll be beter off staying with simpe instructions not optimizing anything until you''re good enough to understand your own code, and all the little tiddy bits out there that make your code run faster. The fact, is that a compiler can NEVER be compared to the human brain, and you''ll be always better of writing the exact code that you want to be executed.. that''s why there''s assemly and all those optimizing tricks...

btw, kill , please stop!!, i would guess you have never written a single game in your life and don''t know how things work. You might be happy with your 5 FPS pong game, but other people might not be...

..-=ViKtOr=-..

Share this post


Link to post
Share on other sites
Gladiator''s right in this case (though still has a lot to learn about tact, and probably isn''t right for the right reasons) assuming we''re talking about the rand() function declared in ANSI C.

rand() % 256 won''t be optimized to rand() & 255 because the ANSI C declaration of rand has it returning a signed int, and % 256 and & 255 have different results when performed on negative numbers. (-4 % 256 = -4, -4 & 255 = 252)
However, if rand() is cast to unsigned int, then the compiler will optimize to & 255. i.e. ((unsigned int)rand()) % 256.

But quite frankly this is the matter of about 2 clock cycles per rand() call. Given that a rand() is an expensive operation (unless you are using a completely moronic generator) is it really worth obfuscating your code with bit operators? Especially in this case, where a simple cast will clear things up.

And further more I''d like to add saying that you should never trust the compiler is much like saying that your time is worth nothing. Even if the compiler can''t optimize as well as the human brain, it still performs it''s optimizations on several orders of magnitude fater than a human can.

Share this post


Link to post
Share on other sites
quote:
Original post by JonatanHedborg

Ok, I made a little test program that uses (rand()%99)+1 to make a random number between 1 and 100, loops it a couple of million times and then calculates the average... it''s VERY close to 50... (wich it should be) so i dont understand whats wrong w/ using the mod...


In practice, the ''bias'' is so small as to be hardly noticeable. I think people are arguing the technicality here Imagine that rand() returned an unsigned char, 0 to 255. Therefore, if you used rand()%100 you''d have more ways of getting a number from 0 to 55 (eg 10, 110, 210 would all return 10) than 56-99 (only 60 and 160 could return 60 - there is no 260 between 0 and 255). So if it was a char, you could have as much as a 50% bias on a simple percentage towards lower numbers. Now, since rand() uses an int (usually 32 bits) then rand()%100 is hardly ever going to look wrong. It''s when your desired random-number range starts approaching the maximum range that can be returned from rand() that you should be concerned about bias. (eg. rand() % (MAX_INT/2.5) would be very badly weighted towards lower numbers.)

Share this post


Link to post
Share on other sites
Everyone,

I apologize for my post that previously occupied this space. It was inappropriate for these forums, and I should have used better judgement before posting.

---- --- -- -
Blue programmer needs food badly. Blue programmer is about to die!

Edited by - mossmoss on 4/17/00 10:06:06 AM

Share this post


Link to post
Share on other sites
SiCrane, Im sure ur right, why dont u try it? i posted the (very simple) code...

========================
Game project(s):
www.fiend.cjb.net

Share this post


Link to post
Share on other sites
quote:
Original post by Kylotan
In practice, the ''bias'' is so small as to be hardly noticeable. I think people are arguing the technicality here Imagine that rand() returned an unsigned char, 0 to 255. Therefore, if you used rand()%100 you''d have more ways of getting a number from 0 to 55 (eg 10, 110, 210 would all return 10) than 56-99 (only 60 and 160 could return 60 - there is no 260 between 0 and 255). So if it was a char, you could have as much as a 50% bias on a simple percentage towards lower numbers. Now, since rand() uses an int (usually 32 bits) then rand()%100 is hardly ever going to look wrong. It''s when your desired random-number range starts approaching the maximum range that can be returned from rand() that you should be concerned about bias. (eg. rand() % (MAX_INT/2.5) would be very badly weighted towards lower numbers.)



I agree, Kylotan, and should have suggested as such in my earlier postings.

One area, though, where even this little bias may make a difference is in some Monte Carlo methods, where you may generate several million random numbers. I was hit by this problem in school where my final results were off by a slight bit (although I may have been using 16-bit numbers, which would increase the bias slightly).



---- --- -- -
Blue programmer needs food badly. Blue programmer is about to die!

Share this post


Link to post
Share on other sites
this is what i''d do for a number from 1 to 10:
int n = 10 * (double)rand() / RAND_MAX + 1;

As far as I can tell it works great. If you''re doing encryption or something you might wanna do more research, but for any game application i can think of, it works peachy. kill''s right, worry about your drawing code. I''m making a cute little asteroids game in DDraw. I was getting 75fps. I added a page and a half of collision detection and resolution code, and all of the physics code, to be processed every frame. It called plenty of trig functions and used mod several times every pass. After that, I was getting about 74.4 fps.

-J

Share this post


Link to post
Share on other sites
quote:
Original post by JonatanHedborg
SiCrane, Im sure ur right, why dont u try it? i posted the (very simple) code...


Huh, I''m not quite sure I understand the context of your post. I was simply refering to the & 255 vs % 256 optimization. Your code seems to be with regards to the mod bias.

(Btw, shouldn''t you be modding against 100, not 99? Just a thought.)

Share this post


Link to post
Share on other sites

  • Advertisement