• Status: Solved
• Priority: Medium
• Security: Public
• Views: 415

# random number

how to generate a random number from 1 to 2486813? The upper limit is larger than RAND_MAX!!!
0
ansi_c
• 4
• 3
• 3
• +4
2 Solutions

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

Commented:
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

Commented:
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

Commented:
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

Commented:
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

Commented:
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

Commented:
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 Commented:
griessh, I do not understand the above link :(
0

Commented:
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

Commented:

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

Commented:
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

Commented:
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

Commented:
>>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

Commented:
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

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

Commented:
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
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.