Solved

random number

Posted on 2004-10-22
406 Views
Last Modified: 2010-04-15
how to generate a random number from 1 to 2486813? The upper limit is larger than RAND_MAX!!!
0
Question by:ansi_c
    16 Comments
     
    LVL 11

    Expert Comment

    by:cjjclifford
    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

    by:cjjclifford
    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

    by:cjjclifford
    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

    by:van_dy
    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

    by:avizit
    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

    by:van_dy
    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 12

    Expert Comment

    by:griessh
    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

    by:ansi_c
    griessh, I do not understand the above link :(
    0
     
    LVL 12

    Expert Comment

    by:griessh
    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

    by:HendrikTYR
    Your in luck:

    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

    by:HendrikTYR
    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

    by:HendrikTYR
    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

    by:avizit
    >>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

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

    by:avizit
    Thanks for taking the pains to explain .. I can see your point now :)
    0
     
    LVL 12

    Expert Comment

    by:stefan73
    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

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone. Privacy Policy Terms of Use

    Featured Post

    IT, Stop Being Called Into Every Meeting

    Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

    Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
    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…
    The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
    Video by: Grant
    The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.

    875 members asked questions and received personalized solutions in the past 7 days.

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

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    11 Experts available now in Live!

    Get 1:1 Help Now