Prelude's Random Numbers Corner

This is a discussion on Prelude's Random Numbers Corner within the C++ Programming forums, part of the General Programming Boards category; As a starter I have no formal instruction in programming, my background is mathematics. While doing some browsing on the ...

  1. #1
    Registered User
    Join Date
    Nov 2004
    Posts
    2

    Question Prelude's Random Numbers Corner

    As a starter I have no formal instruction in programming, my background is mathematics. While doing some browsing on the subject of generating x distinct random ints from 0 to y (with y>=x of course) I took a look in the FAQ and in Prelude's Corner about the subject. In the Prelude's Corner entry the second to last example (the part included here) really confuses me.
    Code:
    int nrand ( int n )
    {
      int r;
      int bucket_size = RAND_MAX / n;
    
      if ( n <= 0 || n > RAND_MAX )
        return 0;
      do {
        r = std::rand() / bucket_size;
      } while ( r >= n );
    
      return r;
    }
    This (correct me if I'm wrong) generates a random int between 0 and n-1. Prelude states that the idea is to split the range of random function into buckets of equal size (Is this actually equal or just as near equal as is possible without adding extra code to worry about a few small values? by extreme example if RAND_MAX happened to be 2,would the one bucket be of length 1 and the other of length 2 to split the values 0,1,2 as evenly as possible?). Am I missing something when I think the following implementation of the nrand function is just as good but shorter and without the need for a loop:
    Code:
    int nrand (int n)
    {
      if ( n <= 0 || n > RAND_MAX )
        return 0;
      
      return (int)(((double)std::rand() * n) / ((double)RAND_MAX +1));
    }
    ---
    Thraen

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >This (correct me if I'm wrong) generates a random int between 0 and n-1.
    For the most part, yes. Though it's not exactly great code (written in haste and has a few bugs) and I should rewrite it. It's on my list of things to do.

    >Is this actually equal or just as near equal as is possible
    It's about as equal as it gets considering that it's impossible to divide an uneven set of numbers into an even number of buckets, such as when RAND_MAX isn't an exact multiple of n.

    >Am I missing something
    Yes. The problem with your suggestion is probability. If the value of n begins to near RAND_MAX then the probability of certain values appearing more often than others increases. The bucket trick avoids this situation and you have a much more uniform set of pseudo-random numbers.
    My best code is written with the delete key.

  3. #3
    Registered User
    Join Date
    Nov 2004
    Posts
    2
    Thanks for your additional explanation Prelude, I now understand what was confusing me.

    ---
    Thraen

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. questions....so many questions about random numbers....
    By face_master in forum C++ Programming
    Replies: 2
    Last Post: 07-30-2009, 08:47 AM
  2. random numbers
    By mesmer in forum C Programming
    Replies: 4
    Last Post: 10-24-2008, 01:22 PM
  3. Generating a sequence of numbers in a random order
    By mirbogat in forum C Programming
    Replies: 15
    Last Post: 08-12-2008, 02:01 PM
  4. random numbers limit
    By HAssan in forum C Programming
    Replies: 9
    Last Post: 12-06-2005, 06:51 PM
  5. Generating 100k to 1 million unique random numbers
    By Ariod in forum C Programming
    Replies: 4
    Last Post: 08-26-2005, 12:59 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21