rand() chooses the same number after several trials

Discussion in 'C++' started by kkirtac, Aug 29, 2007.

  1. kkirtac

    kkirtac Guest

    Hello, i m using the standard rand() function to generate several
    random numbers. Even if i seed the generator before the loop
    "srand( (unsigned)time( NULL ) );" , it usually selects a previously
    selected number in the process, after 6-7 iterations, i want the
    sequence to be unique..should i consider some further modifications in
    the code to achieve my goal maybe ? here is the piece of code..

    vector<int> rands ;
    int rnd ; //random number
    srand( (unsigned)time( NULL ) );
    int range_max = 165, range_min = 0 ;
    for( int i = 0; i < 15 ; i++ )
    {
    rnd = (double)rand() / (RAND_MAX + 1) * (range_max-1 -range_min) +
    range_min;
    rands.push_back(rnd);
    }

    it usually chooses a previously selected random number after 7-8
    iterations, not all the time but usually..

    Regards,
    kkirtac, Aug 29, 2007
    #1
    1. Advertising

  2. kkirtac

    Guest

    On 29 Aug., 11:50, kkirtac <> wrote:
    > Hello, i m using the standard rand() function to generate several
    > random numbers. Even if i seed the generator before the loop
    > "srand( (unsigned)time( NULL ) );" , it usually selects a previously
    > selected number in the process, after 6-7 iterations, i want the
    > sequence to be unique..should i consider some further modifications in
    > the code to achieve my goal maybe ? here is the piece of code..
    >
    > vector<int> rands ;
    > int rnd ; //random number
    > srand( (unsigned)time( NULL ) );
    > int range_max = 165, range_min = 0 ;
    > for( int i = 0; i < 15 ; i++ )
    > {
    > rnd = (double)rand() / (RAND_MAX + 1) * (range_max-1 -range_min) +
    > range_min;
    > rands.push_back(rnd);
    >
    > }
    >
    > it usually chooses a previously selected random number after 7-8
    > iterations, not all the time but usually..
    >
    > Regards,


    nomatter what you do it will allways be psudo random. By using complex
    math and stuff you can it seem like it isnt, but it is. there are
    other options though. Ive heard of people experimenting with geneating
    random numbers by the help of the soundcard static and simular, but
    really i dont think that is a god option. Allso there are devices that
    you can plug into your computer which generates truly random number.
    My favorite so far is: http://random.irb.hr/
    however it relys on you having got a internet conenction.
    , Aug 29, 2007
    #2
    1. Advertising

  3. Abdo Haji-Ali wrote:
    > "kkirtac" <> wrote in message
    >> rnd = (double)rand() / (RAND_MAX + 1) * (range_max-1 -range_min) +
    >> range_min;

    > Why not use:
    > rnd = range_min + rand() % rang_max;
    > instead? I think it's much clearer and you gain some performance by omitting
    > the extra multiplication, don't know why some use the style you're using
    > though.


    Because the lower bits of a PRNG are often much less random than the higher
    bits. See the comp.lang.c FAQ, question 13.16:
    http://c-faq.com/lib/randrange.html

    The OP's code is better quality under such conditions.

    --
    Philip Potter pgp <at> doc.ic.ac.uk
    Philip Potter, Aug 29, 2007
    #3
  4. kkirtac wrote:
    > Hello, i m using the standard rand() function to generate several
    > random numbers. Even if i seed the generator before the loop
    > "srand( (unsigned)time( NULL ) );" , it usually selects a previously
    > selected number in the process, after 6-7 iterations, i want the
    > sequence to be unique..should i consider some further modifications in
    > the code to achieve my goal maybe ? here is the piece of code..
    >
    > vector<int> rands ;
    > int rnd ; //random number
    > srand( (unsigned)time( NULL ) );
    > int range_max = 165, range_min = 0 ;
    > for( int i = 0; i < 15 ; i++ )
    > {
    > rnd = (double)rand() / (RAND_MAX + 1) * (range_max-1 -range_min) +
    > range_min;
    > rands.push_back(rnd);
    > }
    >
    > it usually chooses a previously selected random number after 7-8
    > iterations, not all the time but usually..


    Even with a perfect random number generator, this may well happen, due to a
    thing called the "birthday paradox":
    http://en.wikipedia.org/wiki/Birthday_paradox

    This states (in terms applicable here) that given 23 numbers randomly chosen
    from the range [1,365] it is more likely than not that they will be nonunique.
    IOW, given 23 random people, it is more likely than not that two share a birthday.

    In your case, given a perfect rand() the probability that 8 numbers will be
    unique in the range [1,165] is 80.1%. That's more likely than not, but about 1
    time in 5 you'll have collisions.

    You should modify your code to prevent collisions entirely if you wish to avoid
    them entirely. This is comp.lang.c FAQ question 13.19; see http://c-faq.com/ for
    details.

    Phil

    --
    Philip Potter pgp <at> doc.ic.ac.uk
    Philip Potter, Aug 29, 2007
    #4
  5. "kkirtac" <> wrote in message
    news:...
    > Hello, i m using the standard rand() function to generate several
    > random numbers. Even if i seed the generator before the loop
    > "srand( (unsigned)time( NULL ) );" , it usually selects a previously
    > selected number in the process, after 6-7 iterations, i want the
    > sequence to be unique..should i consider some further modifications in
    > the code to achieve my goal maybe ?

    Yes... rand() generate pseudorandom numbers, but it doesn't guarantee those
    numbers to be unique.
    Consider when generating a random number between 0 and 1 (i.e. only 0 or 1),
    it wouldn't be so random then if I got a 0 then 1 then 0 then 1
    (alternatively)
    You need to check that you didn't push the generated number in 'rands'
    before; if that's the case you should generate another random number and
    pray it will be different :)
    Or you could search the internet for a better "shuffling" algorithm.

    > rnd = (double)rand() / (RAND_MAX + 1) * (range_max-1 -range_min) +
    > range_min;

    Why not use:
    rnd = range_min + rand() % rang_max;
    instead? I think it's much clearer and you gain some performance by omitting
    the extra multiplication, don't know why some use the style you're using
    though.

    Hope that helps,
    --
    Abdo Haji-Ali
    Programmer
    In|Framez
    Abdo Haji-Ali, Aug 29, 2007
    #5
  6. kkirtac

    Daniel T. Guest

    kkirtac <> wrote:

    > Hello, i m using the standard rand() function to generate several
    > random numbers. Even if i seed the generator before the loop
    > "srand( (unsigned)time( NULL ) );" , it usually selects a previously
    > selected number in the process, after 6-7 iterations, i want the
    > sequence to be unique..should i consider some further modifications in
    > the code to achieve my goal maybe ? here is the piece of code..
    >
    > vector<int> rands ;
    > int rnd ; //random number
    > srand( (unsigned)time( NULL ) );
    > int range_max = 165, range_min = 0 ;
    > for( int i = 0; i < 15 ; i++ )
    > {
    > rnd = (double)rand() / (RAND_MAX + 1) * (range_max-1 -range_min) +
    > range_min;


    Why the (RAND_MAX + 1)? On my system that is equal to INT_MIN. Why
    (range_max - 1 - range_min)? That doesn't seem right either.

    > rands.push_back(rnd);
    > }


    You should do your multiplies first, otherwise you loose precession. Try
    this instead:

    rnd = (double)rand() * (range_max - range_min) / RAND_MAX + range_min;

    > it usually chooses a previously selected random number after 7-8
    > iterations, not all the time but usually..
    Daniel T., Aug 29, 2007
    #6
  7. Daniel T. wrote:
    > kkirtac <> wrote:
    >
    >> Hello, i m using the standard rand() function to generate several
    >> random numbers. Even if i seed the generator before the loop
    >> "srand( (unsigned)time( NULL ) );" , it usually selects a previously
    >> selected number in the process, after 6-7 iterations, i want the
    >> sequence to be unique..should i consider some further modifications in
    >> the code to achieve my goal maybe ? here is the piece of code..
    >>
    >> vector<int> rands ;
    >> int rnd ; //random number
    >> srand( (unsigned)time( NULL ) );
    >> int range_max = 165, range_min = 0 ;
    >> for( int i = 0; i < 15 ; i++ )
    >> {
    >> rnd = (double)rand() / (RAND_MAX + 1) * (range_max-1 -range_min) +
    >> range_min;

    >
    > Why the (RAND_MAX + 1)? On my system that is equal to INT_MIN. Why


    Ooh, nice catch, I didn't spot that.

    > (range_max - 1 - range_min)? That doesn't seem right either.


    I think the OP maybe meant (range_max + 1 - range_min), because this is the
    number of values in the range [range_min,range_max] including both endpoints.

    >> rands.push_back(rnd);
    >> }

    >
    > You should do your multiplies first, otherwise you loose precession. Try
    > this instead:
    >
    > rnd = (double)rand() * (range_max - range_min) / RAND_MAX + range_min;


    For integers, divides lose precision while multiplies retain perfect accuracy.
    For floats, they both lose about the same precision and order doesn't matter. If
    you're using floating point the right line is probably:

    rnd = (double)rand() / ((double)RAND_MAX + 1) * (range_max - range_min + 1) +
    range_min;

    But someone will probably see a bug in my code too, even though I'm just copying
    from the clc FAQ.

    --
    Philip Potter pgp <at> doc.ic.ac.uk
    Philip Potter, Aug 29, 2007
    #7
  8. kkirtac

    Pete Becker Guest

    On 2007-08-29 07:18:06 -0400, "Abdo Haji-Ali"
    <_use_com_instead> said:

    > "kkirtac" <> wrote in message
    > news:...
    >> Hello, i m using the standard rand() function to generate several
    >> random numbers. Even if i seed the generator before the loop
    >> "srand( (unsigned)time( NULL ) );" , it usually selects a previously
    >> selected number in the process, after 6-7 iterations, i want the
    >> sequence to be unique..should i consider some further modifications in
    >> the code to achieve my goal maybe ?

    > Yes... rand() generate pseudorandom numbers, but it doesn't guarantee those
    > numbers to be unique.


    And if the numbers were guaranteed to be unique, they would not be random.

    --
    Pete
    Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
    Standard C++ Library Extensions: a Tutorial and Reference
    (www.petebecker.com/tr1book)
    Pete Becker, Aug 29, 2007
    #8
  9. "Philip Potter" <> wrote in message
    news:fb3jd2$2qm$...
    > Abdo Haji-Ali wrote:
    >> "kkirtac" <> wrote in message
    >>> rnd = (double)rand() / (RAND_MAX + 1) * (range_max-1 -range_min) +
    >>> range_min;

    >> Why not use:
    >> rnd = range_min + rand() % rang_max;
    >> instead? I think it's much clearer and you gain some performance by
    >> omitting the extra multiplication, don't know why some use the style
    >> you're using though.

    >
    > Because the lower bits of a PRNG are often much less random than the
    > higher bits. See the comp.lang.c FAQ, question 13.16:
    > http://c-faq.com/lib/randrange.html
    >
    > The OP's code is better quality under such conditions.

    The more you know :)
    Thanks a lot for the tip.

    --
    Abdo Haji-Ali
    Programmer
    In|Framez
    Abdo Haji-Ali, Aug 29, 2007
    #9
  10. kkirtac

    Pete Becker Guest

    On 2007-08-29 05:50:39 -0400, kkirtac <> said:

    > Hello, i m using the standard rand() function to generate several
    > random numbers. Even if i seed the generator before the loop
    > "srand( (unsigned)time( NULL ) );" , it usually selects a previously
    > selected number in the process, after 6-7 iterations, i want the
    > sequence to be unique..should i consider some further modifications in
    > the code to achieve my goal maybe ? here is the piece of code..
    >


    Yes, that's how random numbers work. If you never got a duplicate value
    until all the values in the range had been returned, the values would
    not be random. (That's why casino operators get so upset with card
    counters) To generate a sequence of unique values, look at the
    algorithm std::random_shuffle.

    --
    Pete
    Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
    Standard C++ Library Extensions: a Tutorial and Reference
    (www.petebecker.com/tr1book)
    Pete Becker, Aug 29, 2007
    #10
  11. kkirtac

    BobR Guest

    kkirtac <> wrote in message...
    > Hello, i m using the standard rand() function to generate several
    > random numbers. Even if i seed the generator before the loop
    > "srand( (unsigned)time( NULL ) );" , it usually selects a previously
    > selected number in the process, after 6-7 iterations, i want the
    > sequence to be unique..should i consider some further modifications in
    > the code to achieve my goal maybe ? here is the piece of code..
    >
    > vector<int> rands ;


    If you want 'unique', try a std::set:

    std::set<int> rands ; // #include <set>

    while( 15 > rands.size() ){
    rands.insert( ( int( std::rand() ) % 165 ) );
    } // while()

    > int rnd ; file://random number
    > srand( (unsigned)time( NULL ) );
    > int range_max = 165, range_min = 0 ;
    > for( int i = 0; i < 15 ; i++ ){
    > rnd = (double)rand() / (RAND_MAX + 1) * (range_max-1 -range_min) +
    > range_min;
    > rands.push_back(rnd);
    > }
    >
    > it usually chooses a previously selected random number after 7-8
    > iterations, not all the time but usually..
    > Regards,


    --
    Bob R
    POVrookie
    BobR, Aug 30, 2007
    #11
  12. kkirtac

    Jerry Coffin Guest

    In article <-
    sjc.supernews.net>, says...

    [ ... ]

    > You should do your multiplies first, otherwise you loose precession. Try
    > this instead:
    >
    > rnd = (double)rand() * (range_max - range_min) / RAND_MAX + range_min;


    This still has a problem: it produces skewed output (some values occur
    more often than others) unless the range evenly divides the range of the
    original generator. Many generators use a prime number as their range,
    in which case this can never happen, so the result is always skewed.

    You can avoid this (and floating point math as well) pretty easily:

    #include <stdlib.h>

    int rand_lim(int limit) {
    int divisor = RAND_MAX/(limit+1);
    int retval;

    do {
    retval = rand() / divisor;
    } while (retval > limit);

    return retval;
    }

    int rand_lim(int lower, int upper) {
    int range = abs(upper-lower);

    return rand_lim(range) + lower;
    }

    --
    Later,
    Jerry.

    The universe is a figment of its own imagination.
    Jerry Coffin, Aug 30, 2007
    #12
  13. kkirtac

    kkirtac Guest

    Hmm, thanks for all sugestions, so i change the topic a little, what
    kind of implementation would you suggest for building a perfectly
    unique sequence. For instance, i will choose a random element from a
    sequence, and save it and then maybe delete it from the original
    sequence to prevent drawing it again in the next selection..but just
    deleting it wont help i think..if i delete, say "3" from the original
    sequence, the size will decrease by 1, but how can i tell the compiler
    not to draw "3" again ?

    Regards,
    kkirtac, Aug 30, 2007
    #13
  14. On 2007-08-30 15:32, kkirtac wrote:
    > Hmm, thanks for all sugestions, so i change the topic a little, what
    > kind of implementation would you suggest for building a perfectly
    > unique sequence. For instance, i will choose a random element from a
    > sequence, and save it and then maybe delete it from the original
    > sequence to prevent drawing it again in the next selection..but just
    > deleting it wont help i think..if i delete, say "3" from the original
    > sequence, the size will decrease by 1, but how can i tell the compiler
    > not to draw "3" again ?


    Save each number you've drawn already in a separate container and check
    if it's in the container when you draw a new number. If it is just draw
    a new number until you get a unique one.

    --
    Erik Wikström
    =?ISO-8859-1?Q?Erik_Wikstr=F6m?=, Aug 30, 2007
    #14
  15. kkirtac

    osmium Guest

    "kkirtac" writes:

    > Hmm, thanks for all sugestions, so i change the topic a little, what
    > kind of implementation would you suggest for building a perfectly
    > unique sequence. For instance, i will choose a random element from a
    > sequence, and save it and then maybe delete it from the original
    > sequence to prevent drawing it again in the next selection..but just
    > deleting it wont help i think..if i delete, say "3" from the original
    > sequence, the size will decrease by 1, but how can i tell the compiler
    > not to draw "3" again ?


    I think there are only two ways, and the best way depends on how many
    numbers you expect to want, call it n. If n is smallish, say a few hundred,
    use shuffle which has been mentioned. If n is larger, keep track of what
    has already been used and if it is a repeat, throw it away and keep drawing
    numbers until you find an acceptable number..
    osmium, Aug 30, 2007
    #15
  16. kkirtac

    kkirtac Guest

    > Save each number you've drawn already in a separate container and check
    > if it's in the container when you draw a new number. If it is just draw
    > a new number until you get a unique one.
    >
    > --
    > Erik Wikström


    Thank you very much Erik for the nice idea,

    > I think there are only two ways, and the best way depends on how many
    > numbers you expect to want, call it n. If n is smallish, say a few hundred,
    > use shuffle which has been mentioned. If n is larger, keep track of what
    > has already been used and if it is a repeat, throw it away and keep drawing
    > numbers until you find an acceptable number..


    and yes, i use both shuffle and Erik's algorithm, thank you too
    osmium .
    kkirtac, Aug 30, 2007
    #16
  17. kkirtac

    Torrey Hills Guest

    On Aug 29, 5:07 am, "Abdo Haji-Ali"
    <_use_com_instead> wrote:
    > "Philip Potter" <> wrote in message
    >
    > news:fb3jd2$2qm$...> Abdo Haji-Ali wrote:
    > >> "kkirtac" <> wrote in message
    > >>> rnd = (double)rand() / (RAND_MAX + 1) * (range_max-1 -range_min) +
    > >>> range_min;
    > >> Why not use:
    > >> rnd = range_min + rand() % rang_max;
    > >> instead? I think it's much clearer and you gain some performance by
    > >> omitting the extra multiplication, don't know why some use the style
    > >> you're using though.

    >
    > > Because the lower bits of a PRNG are often much less random than the
    > > higher bits. See the comp.lang.c FAQ, question 13.16:
    > >http://c-faq.com/lib/randrange.html

    >
    > > The OP's code is better quality under such conditions.

    >
    > The more you know :)
    > Thanks a lot for the tip.
    >
    > --
    > Abdo Haji-Ali
    > Programmer
    > In|Framez


    Great discussions.

    Ken


    Opportunities are never lost. The other fellow takes those you miss.


    | Torrey Hills Technologies, LLC |
    | www.threerollmill.com |
    | www.torreyhillstech.com |
    Torrey Hills, Aug 30, 2007
    #17
  18. kkirtac

    Jorgen Grahn Guest

    On Wed, 29 Aug 2007 11:56:34 +0100, Philip Potter <> wrote:

    > Because the lower bits of a PRNG are often much less random than the higher
    > bits. See the comp.lang.c FAQ, question 13.16:
    > http://c-faq.com/lib/randrange.html


    Some people argue that this is no longer true, though. There was a
    discussion in an around Message-ID: <> back
    in 2003, for example.

    I haven't seen an inventory of rand() in current C libraries, of
    course.

    /Jorgen

    --
    // Jorgen Grahn <grahn@ Ph'nglui mglw'nafh Cthulhu
    \X/ snipabacken.dyndns.org> R'lyeh wgah'nagl fhtagn!
    Jorgen Grahn, Aug 30, 2007
    #18
  19. kkirtac

    Jerry Coffin Guest

    In article <>,
    says...
    > "kkirtac" writes:
    >
    > > Hmm, thanks for all sugestions, so i change the topic a little, what
    > > kind of implementation would you suggest for building a perfectly
    > > unique sequence. For instance, i will choose a random element from a
    > > sequence, and save it and then maybe delete it from the original
    > > sequence to prevent drawing it again in the next selection..but just
    > > deleting it wont help i think..if i delete, say "3" from the original
    > > sequence, the size will decrease by 1, but how can i tell the compiler
    > > not to draw "3" again ?

    >
    > I think there are only two ways, and the best way depends on how many
    > numbers you expect to want, call it n. If n is smallish, say a few hundred,
    > use shuffle which has been mentioned. If n is larger, keep track of what
    > has already been used and if it is a repeat, throw it away and keep drawing
    > numbers until you find an acceptable number..


    There is at least one more designed by Robert Floyd. It's covered quite
    nicely in "A Sample of Brilliance", an old "Programming Pearls" column.
    It's reprinted as column 13 in "More Programming Pearls", but Jon
    Bentley, ISBN 0-201-11889-0.

    --
    Later,
    Jerry.

    The universe is a figment of its own imagination.
    Jerry Coffin, Sep 2, 2007
    #19
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. =?Utf-8?B?UmljayBMdWJhbm92aWM=?=

    Running Multiple Versions of an ASP.NET app chooses wrong default

    =?Utf-8?B?UmljayBMdWJhbm92aWM=?=, Aug 9, 2005, in forum: ASP .Net
    Replies:
    0
    Views:
    301
    =?Utf-8?B?UmljayBMdWJhbm92aWM=?=
    Aug 9, 2005
  2. chooser
    Replies:
    0
    Views:
    354
    chooser
    Jun 28, 2006
  3. Mr Seth T

    activex troubles and trials

    Mr Seth T, Jun 26, 2007, in forum: ASP .Net
    Replies:
    0
    Views:
    327
    Mr Seth T
    Jun 26, 2007
  4. 7stud --

    rand() v. rand(0.1) ?

    7stud --, Sep 15, 2007, in forum: Ruby
    Replies:
    6
    Views:
    232
    Morton Goldberg
    Sep 16, 2007
  5. Roedy Green
    Replies:
    11
    Views:
    500
    Gene Wirchenko
    Dec 13, 2012
Loading...

Share This Page