Print Page - Better random numbers?

Currently I am employing the following method of returning a random number between a range, but i dont believe this is the best way to do it, anyone have any other ways of doing this?

int a, b, c, d;

a = rand() % 40 + 10;
b = rand() % 40 + 10;
c = rand() % 45 + 25;
d = rand() % -10 + (-20);

Quote from: man 3 rand

NOTES
The versions of rand() and srand() in the Linux C Library use the same
random number generator as random(3) and srandom(3), so the lower-order
bits should be as random as the higher-order bits. However, on older
rand() implementations, and on current implementations on different
systems, the lower-order bits are much less random than the higher-
order bits. Do not use this function in applications intended to be
portable when good randomness is needed. (Use random(3) instead.)

If you insist on using high-order bits and not random(), you'll have to use floating point arithmetic:

Quote from: Numerical Recipes in C: The Art of Scientific Computing

If you want to generate a random integer between 1 and 10, you should always do it by using high-order bits, as in

j = 1 + (int) (10.0 * (rand() / (RAND_MAX + 1.0)));

what is the issue that you see with your approach? top google results use it. if the problem is that you're not getting floating-point numbers, see 7's reply.

http://www.safercode.com/blog/2009/12/08/random-number-between-two-integers.html
http://www.dreamincode.net/forums/topic/65642-random-number-between-2-ints/

Quote from: man 3 rand

If you insist on using high-order bits and not random(), you'll have to use floating point arithmetic:

Quote from: Numerical Recipes in C: The Art of Scientific Computing

If you want to generate a random integer between 1 and 10, you should always do it by using high-order bits, as in

j = 1 + (int) (10.0 * (rand() / (RAND_MAX + 1.0)));

Yes, I found something along the lines of this as well.. Just wondering if Q3 had any special built-in functions for this. From this information, I have derived the following, and it works very well:

a = 1 + (int) (40.0 * (rand() / (32768 + 10.0)));
b = 1 + (int) (40.0 * (rand() / (32768 + 10.0)));
c = 1 + (int) (45.0 * (rand() / (32768 + 25.0)));
d = 1 + (int) (-10.0 * (rand() / (32768 + -20.0)));

Instead of using RAND_MAX, I just plugged in the 32768 myself.

Thanks!

UPDATE: This does not seem to work accurately, here's a file of the generated results.

Ultimately, I think this is the best way to do it, but I havent figured out how to do this in Q3.. I need to call time into it somehow.

http://www.linuxquestions.org/questions/programming-9/random-number-in-c-linux-760390/#post3712743 (http://www.linuxquestions.org/questions/programming-9/random-number-in-c-linux-760390/#post3712743)

Quote from: The Geez on September 12, 2011, 04:58:50 PM

I have derived the following, and it works very well:

a = 1 + (int) (40.0 * (rand() / (32768 + 10.0)));
b = 1 + (int) (40.0 * (rand() / (32768 + 10.0)));
c = 1 + (int) (45.0 * (rand() / (32768 + 25.0)));
d = 1 + (int) (-10.0 * (rand() / (32768 + -20.0)));

Instead of using RAND_MAX, I just plugged in the 32768 myself.

Does this really what you want? Also, RAND_MAX is usually 32767.

The 1.0 in the (rand() / (RAND_MAX + 1.0)) expression is a constant, this expression produces a good standard random number in the range [0..1> (a fraction from 0 to 0.999...), the (RAND_MAX + 1.0) part of this expression serves to a) convert into a float and b) guarantee that the result of the division is always < 1.

So I think what you really want is:

Code:

a = 10 + (int) (40.0 * (rand() / 32768.0));		
b = 10 + (int) (40.0 * (rand() / 32768.0));
c = 25 + (int) (45.0 * (rand() / 32768.0));
d = -20 + (int) (-10.0 * (rand() / 32768.0));

Quote

So I think what you really want is:

Code:

a = 10 + (int) (40.0 * (rand() / 32768.0));		
b = 10 + (int) (40.0 * (rand() / 32768.0));
c = 25 + (int) (45.0 * (rand() / 32768.0));
d = -20 + (int) (-10.0 * (rand() / 32768.0));

Produces the following results:
A:47, B:40, C:25, D:-20
A:27, B:32, C:51, D:-24
A:37, B:34, C:48, D:-29
A:20, B:34, C:31, D:-21
A:20, B:42, C:38, D:-28
A:21, B:46, C:40, D:-27
A:27, B:15, C:29, D:-26
A:20, B:17, C:67, D:-20
A:46, B:22, C:55, D:-29
A:48, B:18, C:55, D:-27

Strange, but still not completely accurate
And thanks for the heads up on the RAND_MAX, I assumed 32768.. my bad.. but the results are still slightly inaccurate.

Quote from: The Geez on September 12, 2011, 05:36:01 PM

Strange, but still not completely accurate
And thanks for the heads up on the RAND_MAX, I assumed 32768.. my bad.. but the results are still slightly inaccurate.

Well, I didn't exactly give a heads up, I wrote usually. ;) More so because when you sometimes get numbers greater than the maximum you're expecting for A,B,or C, or numbers smaller than the minimum for D, this can only mean that the real RAND_MAX must be greater than 32767. What are you coding in? Quake lcc?

Edit:
On second thought: I can't see what's wrong with your results: A and B should be in range [10..49], C in range [25..69] and D in range [-29..-20] and they all are if I'm not completely blind, so I guess you really wanted other ranges?

Quote from: The Geez on September 12, 2011, 06:02:48 PM

Quote

What are you coding in? Quake lcc?

I am just using gedit, and compiling with make in linux? Whats Quake lcc? lol

Forgive my ignorance, I'm still figuring a lot of stuff out.

No problem, just write what ranges (minimum and maximum numbers) you really want for A, B, C and D and I'll try to help.

Edit:
Perhaps you want something like this?:

Code:

#include <stdlib.h>		/* Pull in rand() and RAND_MAX */
#include <stdio.h>		/* Pull in printf() */

int my_rand( int min, int max )
{
	return min + (int) ((max - min + 1) * (rand() / (RAND_MAX + 1.0)));
}

int main( void )
{
	int	c;
	for ( c = 0; c < 1000; ++c ) {
		printf( "A:%2d B:%2d C:%2d D:%3d\n",
				my_rand( 10, 40 ),
				my_rand( 10, 40 ),
				my_rand( 25, 65 ),
				my_rand( -30, -20 )
			);
	}
	return 0;
}

You cannot improve on the default rand in ioquake3. It is implemented like this:

Code:

int		rand( void ) {
	randSeed = (69069 * randSeed + 1);
	return randSeed & 0x7fff;
}

I don't know how much better you can make it if you are limited to 16 bit integers.

The C reference rand implementation is a lot bigger:

Code:

int rand(void)
{
  randSeed = randSeed * 1103515245 +12345;
  return (unsigned int)(randSeed/65536) % 32768;
}

Just remember that changing a variable or a attempting to make it better usually makes it a lot worse. Changing any constant is likely to make the function very predictable.

One can attempt to use alternative constants but one must remember to analyze the result for patterns. There are a lot of statistical work that needs to be done to test a random-function.

Well, you can do better, but its not easy. The ioquake3 pseudorandom number generator is the "stolen" old VAX MTH$RANDOM linear congruential generator (http://en.wikipedia.org/wiki/Linear_congruential_generator).

These LCG's (algorithms of type seed = BigPrime * seed + SmallPrime (% (MediumPrime + 1))) have some bad properties like high serial correlation (if you have a few random numbers, you can predict the next one), small period (the generated sequences repeat after relatively few numbers, specially if you isolate low-order bits) and bad distribution (not all numbers in the range 0..MediumPrime get generated).

If you need random numbers for serious work, a Mersenne twister (http://en.wikipedia.org/wiki/Mersenne_twister) algorithm generally is a much better choice (but much more expensive in CPU time).

Take a look at qnoiz (http://icculus.org/~phaethon/q3/nbrng/nbrng.html) for Quake3 QVM. It allows to create better random numbers by using non-deterministic data such as human player input etc.

I haven't tested this, but it looks quite promising.

The code is meant to be used in the game module, so yes, spawnpoint logic could benefit from it. Be aware that the current code selects e.g. a random furthest spawnpoint and thereby limits the number of choices anyways.

I can not really think of a place in game code where you would badly need better random numbers. The engine itself already uses /dev/urandom and such.

OpenArena Message Boards

id Tech 3 => cgame/game/ui => Topic started by: The Geez on September 12, 2011, 03:07:35 PM