Solved

Posted on 2004-10-22

how to generate a random number from 1 to 2486813? The upper limit is larger than RAND_MAX!!!

16 Comments

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

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-------------sqrt(RAND_MA

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

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

It should give better results than the multiplying algo

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

======

Werner

My advice would be to use one of the high res libraries for your number problem instead of a build-in RNG.

=====

Werner

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

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

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

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

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

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

By clicking you are agreeing to Experts Exchange's Terms of Use.

Title | # Comments | Views | Activity |
---|---|---|---|

Details to do the search | 56 | 128 | |

Concatenate two strings Last and First Name | 10 | 48 | |

How to convert utf32 to utf16 using C++ on Ubuntu Linux 15.10 with the gcc c++11 compiler. | 4 | 90 | |

Detect CR LF to each line | 12 | 99 |

Join the community of 500,000 technology professionals and ask your questions.

Connect with top rated Experts

**11** Experts available now in Live!