Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
Solved

# random number

Posted on 2004-10-22
Medium Priority
414 Views
how to generate a random number from 1 to 2486813? The upper limit is larger than RAND_MAX!!!
0
Question by:ansi_c
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 4
• 3
• 3
• +4

LVL 11

Expert Comment

ID: 12380562
generate 2 (or more) random numbers (different seeds for each generator) and multiply them together, modulo 2486813 (into a long presumably)
0

LVL 11

Expert Comment

ID: 12380714
very simple example...

#include <stdlib.h>
#include <time.h>

#define RANDMAX 2486813
int main(void)
{
int i;
srand( time(NULL) );
for( i = 0; i != 100; i++ ) {
printf( "%ld\n", 1 + labs( rand() * rand() ) % RANDMAX );
}
return 0;
}

Note, I've no idea mathematicallly how random this really is... Also, there is only a single seed here....

Cheers,
C.
0

LVL 11

Expert Comment

ID: 12380857
humm, random distrubution is not very even with my sample code (quick test code follows, with results from when I ran it...)
If you are not too worried about even distributions it could be ok....

#include <stdlib.h>
#include <time.h>

#define RANDMAX 50
#define SAMPLES 10000000L
int main(void)
{
int std_results[RANDMAX] = {0};
int new_results[RANDMAX] = {0};
long i;
srand( time(NULL) );
for( i = 0; i != SAMPLES; i++ ) {
std_results[ rand() % RANDMAX] ++;
}
srand( time(NULL) );
for( i = 0; i != SAMPLES; i++ ) {
new_results[ labs( rand() * rand() ) % RANDMAX] ++;
}
printf( "rand()\n=======\n" );
for( i = 0; i != RANDMAX; i++ ) {
if( i % 10 == 0 ) {
printf( "\n" );
}
printf( "%ld\t", std_results[i] );
}
printf( "\n" );

printf( "\n" );

printf( "labs(rand() * rand())\n=======\n" );
for( i = 0; i != RANDMAX; i++ ) {
if( i % 10 == 0 ) {
printf( "\n" );
}
printf( "%ld\t", new_results[i] );
}
printf( "\n" );

return 0;
}

rand()
=======

199695  200001  200157  199065  199687  200089  200221  199950  200179  199747
199598  200018  200017  199684  199600  199243  199923  200455  200452  199364
199779  200006  200377  199906  199774  200153  200653  199484  199922  199838
200599  200186  200883  200790  199484  199704  199590  199916  199536  199914
200819  200695  199932  200321  200149  201112  200059  198987  199724  200563

labs(rand() * rand())
=======

300335  99942   299526  100474  300575  100083  299913  100231  299961  99684
300474  100067  299532  99869   299297  99760   299001  100113  300459  100005
300162  99833   299639  100059  299931  99803   300587  99883   299684  99802
300746  100166  299591  99899   299300  99948   300127  100341  299923  100280
299380  99796   298777  100628  300009  100114  300534  99891   301139  100727
0

LVL 5

Expert Comment

ID: 12380874
consider:

0-------------sqrt(RAND_MAX)---------------sqrt(RMAX)------RAND_MAX------------------------RMAX     <--number line

assuming that rand()/srand() will generate randomly in [1, RAND_MAX], and the case in which sqrt(RMAX) is
fairly close to RAND_MAX,  the probabilty graph for the generated numbers can be shown to be biased towards higher values. It would be a better idea to use linear scaling in this situation.

like printf("%ld\n", rand() * (RMAX / (RAND_MAX + 1.0)));
0

LVL 11

Assisted Solution

avizit earned 80 total points
ID: 12380982
I dont think  multiplying two random numbers is a good idea ..

say you can generate random number from 0 to 4 and you want random numbers from 0-16
when you multiply two random numbers of 0-4

you get only the following values

0,1,2,3,4, 6,8, 9,12,16 ..i.e you tend to miss soem numbers like in this example 13, 15 etc etc

In your case I wonder if following is of any help ..

split 2486813   iinto two numbers as  2486813 = 2486 * 1000 + 813

and find one random number from 0-2468  and call it R1 and another
random number between 0-813 and call it R2
and you have the final random number as   R1 * 1000 + R2

commenst from other experts are welcome

0

LVL 5

Expert Comment

ID: 12381050
avizit: yea, but then what you are suggesting is just linear scaling with a different formula.
It should give better results than the multiplying algo
0

LVL 11

Expert Comment

ID: 12381374
Hi ansi_c,

Build your generator or use one of the 'big' ones (as shown at http://www.agner.org/random/randomc.htm)

======
Werner
0

Author Comment

ID: 12383133
griessh, I do not understand the above link :(
0

LVL 11

Expert Comment

ID: 12383625
The site's primary focus is the quality of random generators. But at the same time it has libraries with random generators that create higher resolution random numbers.
My advice would be to use one of the high res libraries for your number problem instead of a build-in RNG.

=====
Werner
0

LVL 3

Expert Comment

ID: 12390109

Your number 2486813 is not prime and I have found you two nice factors:
371 * 6703 = 2486813

So you can now safely split your range into 371 equal parts.

Therefor:  Take a random number from 1 to 371 and multiply it by a random number from 1 to 6703

That WILL be 100% random with each value from 1 to 2486813 having EXACTLY the same chance of popping up.

Regards
Hendrik
0

LVL 3

Expert Comment

ID: 12390123
Sorry, making mistakes again...

r1 = random number from 1 to 371
r2 = random number from 1 to 6703
result = (r1 - 1) * 6703 + r2

THAT will give all of them a fair chance
0

LVL 3

Expert Comment

ID: 12390678
avizit,

Using your formula a number with that ends with ...814 to ...999 is impossible to come up, like 21999 or 213819

It will work if you let R2 go from 0 - 999 and then disregard anything greater than 2486813 in your final answer
0

LVL 11

Expert Comment

ID: 12391098
>>Using your formula a number with that ends with ...814 to ...999 is impossible to come up, like 21999 or 213819

thanks for pointing that out you are right ...My solution is incorrect ..stupid of me not to have noticed :(

But I wonder what you suggest is going to be okay too

>>>It will work if you let R2 go from 0 - 999 and then disregard anything greater than 2486813 in your final answer

cos that way you are disregarding the randomness of R1 , i.e you disregard R1 if R1 is 2486 and R2 >  814 , so you generate
either R1 or R2 or both again .. and hence the randomness is somewhat gone especially so if you have to discard lots of numbers in a row

>>Therefor:  Take a random number from 1 to 371 and multiply it by a random number from 1 to 6703

I suspect even this may not work
say you have to generfate between 0-21 and you split it into 3 * 7
and you generate two random numbers 0-3 and 0-7 .. no way you are going to come up with the numbers 19, 17 13 etc

0

LVL 3

Accepted Solution

HendrikTYR earned 120 total points
ID: 12393107
Hi avizit,

Yes it will work:
If you want random numbers from 1 to 5 and have a normal die, you may throw it and whenever a 6 come up, just disregard it and throw again.  The fact that your process allows a number out of the range you are looking for (like 6) to come up from time to time does not influence in any way whatsoever the probability of any of the numbers you are looking for to be selected as the answer. ie, the fact that the die has six sides does not make the chance to get a "2" larger than the chance to get a "4". IT would be completely wrong to try and map the 6 to some number in the range!

Now, just use a bigger die, and disregard more of its "unwanted" sides.  By selecting R1 randomly from randomly from 0 - 2486 and R2 randomly from 0 - 999, the following formula:
RESULT = (R1 * 1000) + R2
will give you RANDOM numbers 0 - 2486999 with equal probability.
R1 = 0 and R2 = 0 will yield RES = 0  (our minimum value)
and R1 = 2486 and R2 = 999 will yield 2486999 (our maximum value)
since we are looking for numbers 1 to 2486813, just disregard the complete try when RESULT == 0 or RESULT > 2486813

Please note my second post on the 371 and 6703 solution (the first one was done in a hurry and I made a mistake):
the solution is:
r1 = random number from 1 to 371
r2 = random number from 1 to 6703
result = (r1 - 1) * 6703 + r2

ie, for minimum result = (1-1)*6703+1 = 1
maximum result = (371-1)*6703+6703 = 2486813

All the numbers have exactly the same chance of being selected:
we divide our numbers into 371 dice, each with 6703 sides
we then select one die from the 371 dice (you agree everybody still have an equal chance)
now we roll our die and whichever number is facing up (on our 6703 side die) is our winner.

for 1-21 you would take r1 from 1-3 and r2 from 1-7 then
result = (r1-1)*7 + r2

for 0-21 (this means 22 possibilities) you could use 1-2 and 1-11
with result = (r1-1) * 11 + r2 - 1
or you may take 4 dice (normal 6 sided) and go the "disregard" route.
label the first die's sides 0-5
the next 6-11
then 12-17
and the last 18,19,20,21,X,X
pick one of the four randomly and throw it
if an "X" pops up, START again

whew...
0

LVL 11

Expert Comment

ID: 12393528
Thanks for taking the pains to explain .. I can see your point now :)
0

LVL 12

Expert Comment

ID: 12401561
Hi ansi_c,
Check if you have the 48bit random functions. From the man page:

#include <stdlib.h>

long lrand48(void);

Functions lrand48() and nrand48() return  non-negative  long
integers uniformly distributed over the interval [0, 2**31].

Those ones are by far better than old rand(). rand()'s resolution is highly implementation-dependent, which can lead to nasty results when porting your source.

I strongly discourage using cascaded rand() calls, such as:

rand() ^ (rand() << 15)

The internal resolution (random seed size) of rand() is too small to get good results this way. If you can live with low-quality random numbers, it's fine. Otherwise, don't use rand().

Cheers!

Stefan
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn hoâ€¦
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address.Â This address might be address of another variable/address of devices/address of fuâ€¦
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.
###### Suggested Courses
Course of the Month9 days, 23 hours left to enroll