Random Numbers Generation

alcoholic · #1 27-Jan-2006, 08:25

Till now i have been generating random numbers like this

CPP / C++ / C Code:

#include <cstdlib> 
#include <ctime> 
#include <iostream> 

using namespace std; 

int main() 
{ 
srand((unsigned)time(0)); 
int random_integer; 
for(int index=0; index<20; index++){ 
random_integer = (rand()%10)+1; 
cout << random_integer << endl; 
} 
}

I came across a tutorial which talks about a better method than this and which claims to overcome the problem in the above method. It goes like this.

CPP / C++ / C Code:

#include <iostream> 
#include <ctime> 
#include <cstdlib> 

using namespace std; 

int main() 
{ 
srand((unsigned)time(0)); 
int random_integer; 
int lowest=1, highest=10; 
int range=(highest-lowest)+1; 
for(int index=0; index<20; index++){ 
random_integer = lowest+int(range*rand()/(RAND_MAX + 1.0)); 
cout << random_integer << endl; 
} 
}

I couldn't really understand it properly and didn't understand the problem in the previous method

davekw7x · #2 27-Jan-2006, 10:26

Quote:

Originally Posted by alcoholic

Till now i have been generating random numbers like this

.
.
.
I came across a tutorial which talks about a better method than this and which claims to overcome the problem in the above method. It goes like this.
.
.
.
I couldn't really understand it properly and didn't understand the problem in the previous method

I see two questions:

1. What the heck do these things do? Do they do the same thing? (That's really only one question, so far, right?)

2. Assuming that they are supposed to do the same thing, why would someone recommend one method over the other. Why not just use the "best" method.

The first question requires a little explanation, but the results are easy enough to understand.

The second question is much more fun, since there is no guaranteed "right" answer. Even though I claim that there is no "right" answer, I can try to give a little insight as to why one might be preferred over the other by some people.

The C Standard Library function rand() is designed to generate numbers that "appear" to be from a uniformly distributed set of integers in the range 0 to RAND_MAX, where RAND_MAX is defined in <stdlib.h> (or in some header that is included when you use stdlib.h in your program).

Now, according to the C standard, RAND_MAX is allowed to be implementation-dependent. That is, different compilers can have different values for RAND_MAX. For example, current versions of GNU gcc have the following line in <stdlib.h>

CPP / C++ / C Code:

#define  RAND_MAX  2147483647

In Borland bcc32 version 5.5, i see the following:

CPP / C++ / C Code:

#define  RAND_MAX  0x7fffu

(That is a decimal value of 32767. Microsoft Visual C++ version 6 gives the same value.)

The first method you use doesn't depend on RAND_MAX; it merely takes whatever value that rand() returns (zero to RAND_MAX) and performs modulo arithmetic. So (any integer) % 10 will give a result from 0 to 9 (there are ten possible values: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9). If you add 1 to the modulo result, you get a number has a value from 1 to 10. You can do this for any reasonable integer range for which you want "random" values. It's simple, easy and efficient. You should be able to see how you could modify this to give integers in any other range (use "range" for the modulus operation and add the minimum value).

The second method takes the value from rand() and performs floating point division: it divides the return value by (RAND_MAX + 1.0). That means that the result is a number that is greater than or equal to 0.0 and less than 1.0. Then it multiplies by the range and adds the minimum value.

Multiplying by the range gives a value that is greater than or equal to 0.0 and less than "range". Finally, adding the lower limit of the range gives a number that is greater than or equal to "lower limit" and less than "lower limit" + "range".

Since range is "upper limit" - "lower limit" + 1, the result is a floating point number that is greater than or equal to "lower limit" and less than "upper limit"+1. For your second example, the (floating point) result is converted to an integer by simple assignment, which truncates the fractional part. The end result is an integer that is greater than or equal to "lower limit" and less than or equal to "upper limit".

Plug in 1 for "lower limit" and 10 for "upper limit", and you see that your second example will give values from 1 to 10. (As did your first example.)

Now, we get to the good stuff:

The function rand() for most computers (and almost certainly any that you can get your hands on) is not a random number generator. It gives results according to some mathematical algorithm. The goal is to give a set of numbers that are "close enough" to what you would get from a real random number generator so as to make statistical calculations meaningful.

Notice that, just because a function returns an integer in the range 1 to 10, that doesn't mean that successive calls to that function give a set of numbers that is uniformly distributed from 1 to 10. The first method uses the lower bits of the number that rand() gives us (that is what modulo arithmetic does--- it throws away the upper bits). The second method uses the upper bits of the returned value (that is what division does: it throws away the lower bits).

Why do some people recommend that we use the method of your second example instead of the first? Well some statistical analysts noticed that the actual rand() function supplied as part of C libraries typically didn't give results whose lower bits were very uniformly distributed, but the upper bits were much better. That means that the modulo arithmetic didn't give as good results, for their purposes, as the only slightly more complicated method of your example number 2. Note that this may or may not be true, and in fact both may be suitable, or both may be unsuitable.

When using "random" numbers to test a statistical hypothesis, conscientious researchers must always make sure that their "random" numbers don't have some statistical anomalies that distort the results.

Now, really serious statistical analyists would hardly trust anyone to supply a random number generator, and they typically "roll their own", based on more sophisticated mathematical methods than rand() that comes with their C library. They find one (or build one) that has whatever statistical properties that they need. Typical standard library functions are designed as a compromise between statistical robustness and computational efficiency. If your needs are not met by the simple one, then you use a more complex one.

Really, really serious statistical analysts sometimes use some external hardware interface or device that generates random numbers based on some physical phenomenon, rather than a mathematical algorithm.

Or, as John von Neumann put it:

"Anyone who considers arithmetical methods of producing random
numbers is, of course, in a state of sin. "
(Quote from Donald Knuth's "The Art of Computer Programming",
Vol 2, Chapter 3)

Regards,

Dave

alcoholic · #3 27-Jan-2006, 20:34

Awesome Effort. I have never seen more descriptive reply than this
Thanks a lot

kobi_hikri · #4 28-Jan-2006, 01:33

Quote:

Originally Posted by alcoholic

Awesome Effort. I have never seen more descriptive reply than this

Dave is like that

I didn't know about the fact that modulo is throwing away the upper bits, though when thinking about it, is suddenly sounds obvious ...
With division, I had to look into deeper into the code, but it does look logical.

A real delight, reading your posts, Dave.

Alcoholic (can I address you with your real name ? ):
rand() can be very useful, even for complicated tasks. It all depends on what you need (as Dave said). When I need something to demonstrate or test a function with various values, it does the job.
If you are doing an academic research, then you will be asked to prove the theorem behind your pseudo-random numbers. In this case, I would advise you not to use rand(), but look for proved theorems (that are not controversial).

Here is an example of a good presentation of pseudo-random generator :
Presentation of pseudo-random generator

Kobi.

sERAC · #5 28-Jan-2006, 11:53

Taking an example from the program above, I’d like to clarify a question I’ve been having.

CPP / C++ / C Code:

#include <iostream> 
#include <ctime> 
#include <cstdlib> 
using namespace std; 

int main() 
{ 
srand((unsigned)time(0)); 
int rn; 
int lowest=1, highest=100; 
int range=(highest-lowest)+1; 
for(int index=0; index<20; index++){ 
rn=lowest+int(range*rand()/(RAND_MAX + 1.0)); 
} 
if (rn<50)
	{
        cout<<”A random number is under 50”;
        cout<<"("<<rn<<")";
        }

So, with this program, it should supply a random number always different when run, right? Only 1, so I’d have to copy lines 8-14 again if I wanted a different random number?

Btw, I’m trying to get a “random” number from 1-100.

I’d appreciate any help.

kobi_hikri · #6 28-Jan-2006, 12:53

Quote:

Originally Posted by sERAC

Taking an example from the program above, I’d like to clarify a question I’ve been having.

...

So, with this program, it should supply a random number always different when run, right? Only 1, so I’d have to copy lines 8-14 again if I wanted a different random number?

Btw, I’m trying to get a “random” number from 1-100.

Well, not necessarily. That is the meaning of "random", you could get the same or another number. The distribution of the numbers over large numbers of calling the rand() function, is supposed to behave almost like "real" random number generator.
About generating extra numbers - all you have to do is place the line

CPP / C++ / C Code:

rn=lowest+int(range*rand()/(RAND_MAX + 1.0));

whenever you want another "random" number and it will be calculated and stored in rn.

About generating numbers between X and Y : read about the usage of the rand() function here : rand or read carefully through Dave's explanation, Three posts ago.

Best regards,
Kobi.

davekw7x · #7 28-Jan-2006, 13:32

Quote:

Originally Posted by sERAC

Taking an example from the program above, I’d like to clarify a question I’ve been having.

c++

Code:


  rn=lowest+int(range*rand()/(RAND_MAX + 1.0));

This may work with some compilers and not with others. What ones does it (maybe) work with? Compilers where RAND_MAX is much smaller than the maximum integer (Borland, Microsoft VC++ 6). What ones does it (maybe) not work with? Compilers where RAND_MAX is larger (g++ for example).

Heres the scoop: Look at my previous post that shows RAND_MAX for gcc:

Its value is actually the largest signed (32-bit) integer. That means that for some values returned from rand(), you will get integer overflow when you multiply by anything greater than 1. Try it:

CPP / C++ / C Code:

#include <stdio.h>
#include <stdlib.h>

int main()
{

  int i;
  int r;

  for (i = 1; i < 10; i++) {
    r = i * RAND_MAX;
    printf("   %d * RAND_MAX = %ld\n", i, r);
  }
  return 0;
}

With Borland, here is my output:

Code:

   1 * RAND_MAX = 32767
   2 * RAND_MAX = 65534
   3 * RAND_MAX = 98301
   4 * RAND_MAX = 131068
   5 * RAND_MAX = 163835
   6 * RAND_MAX = 196602
   7 * RAND_MAX = 229369
   8 * RAND_MAX = 262136
   9 * RAND_MAX = 294903

With gcc, here is what I got:

Code:

   1 * RAND_MAX = 2147483647
   2 * RAND_MAX = -2
   3 * RAND_MAX = 2147483645
   4 * RAND_MAX = -4
   5 * RAND_MAX = 2147483643
   6 * RAND_MAX = -6
   7 * RAND_MAX = 2147483641
   8 * RAND_MAX = -8
   9 * RAND_MAX = 2147483639

So, you can see that it is possible to get meaningless output from the previous method. (I didn't bother to debug the method; I just tried to explain what it is trying to do.)

So how can the expression for rn give meaningless results in some cases?

Note that the order of mathematical operations in an expression is not defined in the C (or C++ language). So, if the first thing that is done is to multiply the value returned by rand() by "range", then the resulting integer overflow completely bolluxes up the result. If it just happens that the first thing is that the (floating point) division by (RAND_MAX + 1.0) and the next thing is to multiply by one or the other terms, then all of the math would be done with floating point operations and all would be OK.

How can we fix it? Simply by forcing all arithmetic to be done with floating point arithmetic.

Change the above example to:

CPP / C++ / C Code:

#include <stdio.h>
#include <stdlib.h>

int main()
{

  int i;
  double f;

  for (i = 1; i < 10; i++) {
    f = i * (double)RAND_MAX;
    printf("   %d * RAND_MAX = %.0f\n", i, f);

  }
  return 0;
}

Now, with gcc I get:

Code:

   1 * RAND_MAX = 2147483647
   2 * RAND_MAX = 4294967294
   3 * RAND_MAX = 6442450941
   4 * RAND_MAX = 8589934588
   5 * RAND_MAX = 10737418235
   6 * RAND_MAX = 12884901882
   7 * RAND_MAX = 15032385529
   8 * RAND_MAX = 17179869176
   9 * RAND_MAX = 19327352823

So, you could change the expression in your random number program to something like:

CPP / C++ / C Code:

    rn = lowest + (range * (double)rand()/(RAND_MAX + 1.0));

or some such thing. Then you have an expression that never has an integer overflow, since no integer arithmetic is performed anywhere in the expression. This works with Borland, Microsoft and GNU compilers, so it would be the one that I might recommend. (And, by the way, this may be the reason that some prefer using the modulus operator as in the first example of the original post --- you don't have to deal with these issues. The first method is perfectly suitable for some applications.)

Anyhow, once you have something that works (and I believe that this one does), then you make it a part of your personal repository of "useful things to do in C", and you don't have to worry about it again --- until someone asks you to explain it, of course.

Now that we have a random number generator that works, let's look at the program:

Quote:

Originally Posted by sERAC

So, with this program, it should supply a random number always different when run, right?

You have this:

CPP / C++ / C Code:

    srand(time(0));

This line "seeds" rand() with the current CPU clock time (The number of seconds since Jan 1, 1970 for computers running Windows, for example). That means that every time that you run the program (assuming that a second has elapsed since the previous run) the sequence of numbers obtained from successive calls to rand() will be different. So you don't have to change anything in your program in order to get a different random sequence for every run.

If you didn't call srand() in your program, you would get exactly the same sequence every time. I mention this because this is sometimes useful for debugging a program where you want the same sequence every time.

Now, for the program itself. I reformatted it somewhat more to my liking, but didn't change anything other than the statement that I described above:

CPP / C++ / C Code:

#include <iostream> 
#include <ctime> 
#include <cstdlib> 
using namespace std; 

int main() 
{ 

    int rn; 
    int lowest  = 1;
    int highest = 100; 
    int range   = (highest - lowest) + 1; 

    srand((unsigned)time(0)); 

    for(int index = 0; index < 20; index++){ 
        rn = lowest + range * (double)rand() / (RAND_MAX + 1.0); 
    } 

    if (rn < 50) {
        cout << "A random number is under 50";
        cout << " (" << rn << ")";
    }
    return 0;
}

When I ran the program, sometimes I got the printout statement, and sometimes not. Is that what you had in mind? You are calling the rand() function 20 times and testing the last value.

A slightly more interesting program might be to count the number of times the value is under 50 and the times that is over 50 and the number of times that is equal to 50, but you didn't actually state what you wanted to accomplish.

(And I think your output is a little misleading, since some of the results might have been more than 50 and some less, but you are actually only looking at the last one.)

Regards,

Dave

sERAC · #8 28-Jan-2006, 17:01

Thanks, the way you formatted it makes things a lot clearer. You guys are smart.

I recently downloaded Dev-c++, it's interface kind of reminds me of xcode. I don't know if you've had experience with this program before, but for some reason it'll compile fine but it messes up when trying to run... When I click "run" a black box pops up but then instantaneously dissapears... what to do?

davekw7x · #9 28-Jan-2006, 17:34

Quote:

Originally Posted by sERAC

Thanks, the way you formatted it makes things a lot clearer. You guys are smart.

I recently downloaded Dev-c++, it's interface kind of reminds me of xcode. I don't know if you've had experience with this program before, but for some reason it'll compile fine but it messes up when trying to run... When I click "run" a black box pops up but then instantaneously dissapears... what to do?

I usually run command line programs from the command line rather than from an IDE. (I'm just funny that way.)

A lot of people here use Dev-C++ with excellent results. Running and debugging from an IDE can be a Good Thing for lots of people, but, in the case of Dev-C++ you have to put something in the program to prevent what you are seeing.

Just before the program exits (returns from main) you can put "getchar()", maybe preceded by a prompt for the user to "Press [Enter]" to exit the program. See footnote. (Note that if you have been using, say, scanf() to read integers from the user console, you might have a little bit of work to clear out anything remaining in the input buffer. I usually use fgets() for user input, so I don't have to worry about such things.)

Waltp has posted some suggestions for this Frequently Asked Question:

Pausing a Program

I just wish Walt were not so wishy-washy about discouraging the use of system("PAUSE"), which is what the sample and wizard-generated programs from Dev-C++ usually have. There are good reasons not to use this, and Walt really needs to be more assertive about his true feelings.

Regards,

Dave

Footnote: Telling the user to "Press [Enter] to exit the program" seems kind of silly, but it's no sillier than Microsoft's instruction on how to shut down your machine: "Click on the 'Start' button to shut down your computer."

WaltP · #10 28-Jan-2006, 20:17

Quote:

Originally Posted by davekw7x

I just wish Walt were not so wishy-washy about discouraging the use of system("PAUSE"), which is what the sample and wizard-generated programs from Dev-C++ usually have. There are good reasons not to use this, and Walt really needs to be more assertive about his true feelings.

I'll try. I just don't like ruffling feathers.

Quote:

Originally Posted by davekw7x

Footnote: Telling the user to "Press [Enter] to exit the program" seems kind of silly, but it's no sillier than Microsoft's instruction on how to shut down your machine: "Click on the 'Start' button to shut down your computer."

I suppose you could say:
"Re-label the [Enter] key to [Exit] then press it to quit this program... I'll wait.
Don't forget to use dry-erase pen so you can fix the key after I'm gone..."

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
random number generation issues	Jonnyz007	C++ Forum	8	27-Oct-2005 19:13
Generating random numbers	nkhambal	C Programming Language	5	26-Apr-2005 06:49
Linear Search	eccoflame	C Programming Language	3	19-Apr-2005 08:36
Poker game and random numbers...	markersniffer21	C++ Forum	2	06-Nov-2004 08:43
Help with random numbers	da_bomb50	MySQL / PHP Forum	3	04-Aug-2004 19:34

Random Numbers Generation

Re: Random Numbers Generation

Re: Random Numbers Generation

Re: Random Numbers Generation

Re: Random Numbers Generation

Re: Random Numbers Generation

Re: Random Numbers Generation

Re: Random Numbers Generation

Re: Random Numbers Generation

Re: Random Numbers Generation