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

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

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!

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!

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

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=-..

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!

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!

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

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.