random number tutorial

This is a discussion on random number tutorial within the C++ Programming forums, part of the General Programming Boards category; I was reading the tutorial located here: http://faq.cprogramming.com/cgi-bin/...&id=1073086407 and there appear to be some errors. Here is the relevant part: ...

  1. #1
    Registered User
    Join Date
    Apr 2003
    Posts
    2,662

    random number tutorial

    I was reading the tutorial located here:

    http://faq.cprogramming.com/cgi-bin/...&id=1073086407

    and there appear to be some errors. Here is the relevant part:
    Code:
    #include <iostream>
    #include <cstdlib>
    #include <ctime>
    
    int main()
    {
      std::srand ( (unsigned int)std::time ( 0 ) );
      std::cout<< std::rand() / ( RAND_MAX / 10 + 1 ) <<std::endl;
      std::cout<< (int)( (double)std::rand() / ( RAND_MAX + 1 ) * 10 ) <<std::endl;
    
      return 0;
    }
    This code shows two methods to use the high order bits of rand() by calculating the high value of the range with RAND_MAX and then dividing the call to rand() by the result. The point where 1 is added to RAND_MAX is important to note, this forces the range of random numbers to be 1 through 10 instead of 0 through 9.
    Removing the std:: specifiers, the random number code for the first method is:

    rand() / (RANDMAX / 10 + 1)

    Let's suppose RANDMAX is 500. If rand() returns 1, then the result is:

    1 / (500 / 10 + 1) = 1/51

    which because of integer arithmetic produces 0. As a consequence, if rand() returns any number less than 51, the answer is 0, and it creates the mapping:

    0 - 50 ---> 0

    If rand() returns 51, then the result is 1. Due to integer arithmetic, the result will continue to be 1 until the numerator reaches 102, giving this mapping:

    0 - 50 -----> 0
    51 - 101 --> 1

    If you continue figuring out the ranges, you will come up with this:

    0 - 50 -----> 0
    51 - 101 --> 1
    102 - 152 -> 2
    153 - 203 -> 3
    204 - 254 -> 4
    ..
    ..
    ..
    459 - 500 -> 9

    First of all, you can see that the numbers produced are 0-9, not 1-10 as the tutorial seems to imply. In addition, all the ranges of numbers contain 51 numbers except the range 459 - 500, which contains only 42 numbers. That means the number 9 is less likely to be produced by the calculation, which means the calculation will not produce random numbers between 0 and 9.

    The second method seems to suffer from similar problems. If RAND_MAX is equal to 500 and rand() returns 1, then the calculation produces:

    1.0 / 501 * 10 = .02

    and when you cast that to an int, you get 0.

    The ranges are a little better, but the first range has 51 numbers, while the other ranges have 50 numbers. That makes it more likely the number 0 will be produced over any other number.

    0 - 50 -----> 0
    51 - 100 --> 1
    101 - 150 -> 2
    151 - 200 -> 3
    201 - 250 -> 4
    ..
    ..
    ..
    451 - 500 -> 9

    Also, when I test out the code, I get the same number everytime, which must mean the seed is the same everytime I run the code. Why doesn't that work?
    Last edited by 7stud; 07-26-2005 at 12:46 PM.

  2. #2
    FOX
    Join Date
    May 2005
    Posts
    188
    I already made a thread about this a few weeks ago: Prelude's random numbers tutorial

  3. #3
    Registered User
    Join Date
    Apr 2003
    Posts
    2,662
    Thanks. That's just sloppy work. I've written much more complicated tutorials, and I've always checked them over several times before posting them, and then I go through the tutorials step by step after posting them to make sure they produce the proper results.

    It's a shame no one on cboard double checks submitted tutorials or bothers to post corrections--it just wastes everyone's time.

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >That's just sloppy work.
    I appreciate that you deigned to post assumed problems with my tutorial on the forum and call my work sloppy without even bothering to contact me directly to report the error yourself. If you had done so, I could have told you that the one legitimate problem you mentioned is known, has been reported, and nobody with access has corrected it yet.

    >you can see that the numbers produced are 0-9, not 1-10 as the tutorial seems to imply
    Yes. This is a known error. However, nobody seems to be updating the FAQ entries, so it remains despite my sending corrections. Since you've written "much more complicated tutorials", you should be well aware that errors happen, even if you are very careful about eliminating them.

    Your first complaint is valid (even though everyone already knows about it), but your second complaint is just silly. The fact that the ranges are not evenly distributed is a natural result of fitting a pseudorandom sequence into a smaller range. This is a well known issue (born of shrinking a uniform range so that it is smaller, and thus, no longer uniform) that is typically improved by dropping the numbers through buckets until you find one that you like:
    Code:
    do
      r = rand();
    while ( r >= LIMIT );
    This guarantees that the (supposedly) uniform distribution of the full range is preserved. So it seems like you've gone to great lengths to bash my tutorial when the problem is with pseudorandom numbers and common practice in general. Thanks.

    >I get the same number everytime, which must mean the seed is
    >the same everytime I run the code
    Yes, it must, mustn't it? Well no, not really. The seed can be different, but if it's not sufficiently different to pull you out of the shrunken range, you'll get the same number for the first call to rand every time. For example, on one of my implementations, in the range [0,9), I can use a seed from 0 all the way to 992 before the first result of rand changes from 0 to 1. You'll see a similar effect by just printing the result of rand and not adjusting the range at all. The first call to rand will give you increasing numbers localized to a small area because the seed is changing only by small amounts in a predictable direction.

    You'll notice that the seed is changing, but only if you actually print it, or call rand multiple times, or don't shrink the range and pay attention to the resulting values. This is an issue with the progressive nature of using the system time as a random seed, and is yet another reason why I believe that this common practice (using time() directly in srand) is foolhardy. A far superior method is to take a hash of the system time instead:
    Code:
    unsigned time_seed()
    {
      time_t now = time ( 0 );
      unsigned char *p = (unsigned char *)&now;
      unsigned seed = 0;
      size_t i;
    
      for ( i = 0; i < sizeof now; i++ )
        seed = seed * ( UCHAR_MAX + 2U ) + p[i];
    
      return seed;
    }
    
    srand ( time_seed() );
    If you want to look for errors in something current, try here. I always appreciate bug reports, and with my own site I can quickly fix the errors that are found, unlike the FAQ on this site, where I don't have write access. Anyway, in my defense, that particular tutorial was written in haste, then updated in haste. I ended up rewriting it completely for my website because, looking back at it, nothing could be reused to my satisfaction.
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. rapid random number generation problem
    By Newton in forum C Programming
    Replies: 17
    Last Post: 09-19-2008, 02:08 PM
  2. Random number in range generation.
    By hebali in forum C Programming
    Replies: 19
    Last Post: 03-04-2008, 09:46 AM
  3. adding a number to a number
    By bigmac(rexdale) in forum C Programming
    Replies: 11
    Last Post: 10-24-2007, 12:56 PM
  4. How exactly does the random number generator work?
    By Finchie_88 in forum C++ Programming
    Replies: 6
    Last Post: 08-24-2007, 12:46 AM
  5. How do I restart a random number sequence.
    By jeffski in forum C Programming
    Replies: 6
    Last Post: 05-29-2003, 02:40 PM

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