Pages: [1]
  Print  
Author Topic: Better random numbers?  (Read 24844 times)
The Geez
Nub


Cakes 0
Posts: 13


« on: September 12, 2011, 03:07:35 PM »

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);


Logged
7
Member


Cakes 7
Posts: 278


Is 7 up?


« Reply #1 on: September 12, 2011, 04:47:55 PM »

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)));
Logged

I'm on the ten most wanted list, I've got it dead in the groove.
My face is on every wanted poster in town, for the way I move.
VortexHU
Lesser Nub


Cakes 3
Posts: 138



« Reply #2 on: September 12, 2011, 04:51:35 PM »

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/
Logged

— VortexHU —
The Geez
Nub


Cakes 0
Posts: 13


« Reply #3 on: September 12, 2011, 04:58:50 PM »

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.

« Last Edit: September 12, 2011, 05:22:55 PM by The Geez » Logged
The Geez
Nub


Cakes 0
Posts: 13


« Reply #4 on: September 12, 2011, 05:06:20 PM »

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
Logged
7
Member


Cakes 7
Posts: 278


Is 7 up?


« Reply #5 on: September 12, 2011, 05:23:23 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));
Logged

I'm on the ten most wanted list, I've got it dead in the groove.
My face is on every wanted poster in town, for the way I move.
The Geez
Nub


Cakes 0
Posts: 13


« Reply #6 on: September 12, 2011, 05:36:01 PM »

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.
Logged
7
Member


Cakes 7
Posts: 278


Is 7 up?


« Reply #7 on: September 12, 2011, 05:54:20 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. Wink 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?
« Last Edit: September 12, 2011, 06:08:54 PM by 7 » Logged

I'm on the ten most wanted list, I've got it dead in the groove.
My face is on every wanted poster in town, for the way I move.
The Geez
Nub


Cakes 0
Posts: 13


« Reply #8 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.
Logged
7
Member


Cakes 7
Posts: 278


Is 7 up?


« Reply #9 on: September 12, 2011, 06:11:35 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, ccool 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;
}
« Last Edit: September 12, 2011, 06:35:47 PM by 7 » Logged

I'm on the ten most wanted list, I've got it dead in the groove.
My face is on every wanted poster in town, for the way I move.
The Geez
Nub


Cakes 0
Posts: 13


« Reply #10 on: September 12, 2011, 07:14:44 PM »

Thanks, I will try that!   Smiley
Logged
sago007
Posts a lot
*

Cakes 62
Posts: 1664


Open Arena Developer


WWW
« Reply #11 on: September 13, 2011, 11:22:31 AM »

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

There are nothing offending in my posts.
7
Member


Cakes 7
Posts: 278


Is 7 up?


« Reply #12 on: September 13, 2011, 01:08:57 PM »

Well, you can do better, but its not easy.  The ioquake3 pseudorandom number generator is the "stolen" old VAX MTH$RANDOM 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 algorithm generally is a much better choice (but much more expensive in CPU time).
Logged

I'm on the ten most wanted list, I've got it dead in the groove.
My face is on every wanted poster in town, for the way I move.
grey matter
Member


Cakes 8
Posts: 381

>9k


« Reply #13 on: November 14, 2011, 02:54:53 PM »

Take a look at qnoiz 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.
Logged

This space is for rent.
Cacatoes
Banned for leasing own account
Posts a lot
*

Cakes 73
Posts: 1427


also banned for baiting another to violate rules


« Reply #14 on: November 14, 2011, 03:28:03 PM »

In which part of the game could we see effects from this ? Spawn points ?
Logged

Todo: Walk the cat.
grey matter
Member


Cakes 8
Posts: 381

>9k


« Reply #15 on: November 14, 2011, 03:38:20 PM »

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

This space is for rent.
Pages: [1]
  Print  
 
Jump to: