Bug in rand()
There is a bug in the implementation of rand() for Visual C++ 10 (probably others) and it does not generate random numbers! There are two problems, the small size of the result (32767 max, hence there should be too many duplications after calling it many times) and it simply does not generate random numbers when tested using Chi-Squared. Supposedly, the lower bits are less random in many implementations -- in this case, the middle bits are less random! Try rand()/100 % 2 and check the results!
Here is the program (and, it does call srand() which is NOT required for generating random numbers, just for providing a "random" seed!
/*
Chi Squared (from http://c2.com/cgi/wiki?ChiSquared)
A simple statistical test that can be useful for testing the
randomness of a distribution:
Generate a uniform distribution d[0..r] using the (suspected)
PseudoRandomNumberGenerator you want to test and doing N runs.
N should be greater than say 10*r.
The average fill in each slot in d is f = N/r
ChiSquared = Sum[0<=i<r](((d[i]-f)^2)/f)
If ChiSquared is within 2*Squareroot(r) of r 90% of the time,
the generator passed this test.
Note that being within these limits 95% of the time if just as bad
as only being within them 85% of the time. This test is necessary
but not sufficient - it is easy to construct distributions that
pass the test and are obviously not random. (For example, mod r
of each of the numbers from 1 to N.)
-- JanLarsen
*/
#include <iostream>
#include <ctime>
#include <cmath>
using namespace std;
// function prototype
int myRand();
int main() {
const int R = 6; // number of "buckets." 6 simulates a die; 2 a coin flip;
// 12 with sum of two "rolls" for dice [would require
//changing the expected frequency!]; etc.
long long d[R] = {0}; // following the above, d will be the "buckets"
// for counting random values
long long n = 0; // number of trials. Should be bigger than 10 * r.
float f = 0.0; // this will be the computed expected frequency for each
//d[i] and will be (<float> N )/ R
float chiSquared = 0.0;
cout << "Enter the number of trials: ";
cin >> n;
// see if n is big enough
if(n < (10 * R)) {
cout << "The number of trials should be at least" << 10 * R
<< " for statistical validity." << endl;
return -1;
}
f = (float) n /R; // expected frequency value
srand(static_cast<int>(time(0))); // randomize the randomizer.....
for(long long trials = 0; trials < n; trials++) {
d[rand()/100 % R]++; // middle digits are actually worse! Try with myRand() for good results
// supposedly, the low digits of some
// random number generators are not very random!
// Also test with "digits" closer to middle of
// number by dividing rand() by powers of r (or of 10?).
}
// compute the Chi-Squared value for the test.
float diff[R] = {0.0};
for(int i = 0; i < R; i++) {
diff[i] = d[i] - f;
chiSquared += (diff[i] * diff[i]) / f; // or diff ** 2 would work, too!
}
// report results
cout << endl << endl <<
"The actual and expected distributions for each die value" << endl;
cout << "Die Value Difference" << endl;
for(int i = 0; i < R; i++) {
cout << i + 1 << " " << diff[i] << endl;
}
cout << endl;
cout << "Chi-Squared for this distribution is : " << chiSquared << endl;
cout << "This should be between " << (R - (2.0 * sqrt((float) R))) <<
" and " << (R + (2.0 * sqrt((float) R)));
if( chiSquared > (R - (2.0 * sqrt((float) R))) &&
chiSquared < (R + (2.0 * sqrt((float) R))) ) { // test for significance
cout << " and is significant; i.e., passed the test.";
} else {
cout << " and is not significant!!!!";
}
cout << endl;
return 0;
}
// Since rand() is obviously not a very good random number generator for large numbers,
// I looked at http://en.wikipedia.org/wiki/Linear_congruential_generator
long long randValue = (static_cast<int>(time(0)) & 0X7FFFFFFF) | 0X01;
// insures a 32-bit value that is odd
// 2741 could be an initial seed (which happens to be the 400th prime number)
// this could be initialized with time() * 2 + 1 to generate an
// odd-valued starting point.
int myRand() {
randValue = ((1103515245 * randValue) + 12345) & 0X7FFFFFFF; // glibc values from above
return static_cast<int>(randValue);
}
Here is the program (and, it does call srand() which is NOT required for generating random numbers, just for providing a "random" seed!
/*
Chi Squared (from http://c2.com/cgi/wiki?ChiSquared)
A simple statistical test that can be useful for testing the
randomness of a distribution:
Generate a uniform distribution d[0..r] using the (suspected)
PseudoRandomNumberGenerator you want to test and doing N runs.
N should be greater than say 10*r.
The average fill in each slot in d is f = N/r
ChiSquared = Sum[0<=i<r](((d[i]-f)^2)/f)
If ChiSquared is within 2*Squareroot(r) of r 90% of the time,
the generator passed this test.
Note that being within these limits 95% of the time if just as bad
as only being within them 85% of the time. This test is necessary
but not sufficient - it is easy to construct distributions that
pass the test and are obviously not random. (For example, mod r
of each of the numbers from 1 to N.)
-- JanLarsen
*/
#include <iostream>
#include <ctime>
#include <cmath>
using namespace std;
// function prototype
int myRand();
int main() {
const int R = 6; // number of "buckets." 6 simulates a die; 2 a coin flip;
// 12 with sum of two "rolls" for dice [would require
//changing the expected frequency!]; etc.
long long d[R] = {0}; // following the above, d will be the "buckets"
// for counting random values
long long n = 0; // number of trials. Should be bigger than 10 * r.
float f = 0.0; // this will be the computed expected frequency for each
//d[i] and will be (<float> N )/ R
float chiSquared = 0.0;
cout << "Enter the number of trials: ";
cin >> n;
// see if n is big enough
if(n < (10 * R)) {
cout << "The number of trials should be at least" << 10 * R
<< " for statistical validity." << endl;
return -1;
}
f = (float) n /R; // expected frequency value
srand(static_cast<int>(time(0))); // randomize the randomizer.....
for(long long trials = 0; trials < n; trials++) {
d[rand()/100 % R]++; // middle digits are actually worse! Try with myRand() for good results
// supposedly, the low digits of some
// random number generators are not very random!
// Also test with "digits" closer to middle of
// number by dividing rand() by powers of r (or of 10?).
}
// compute the Chi-Squared value for the test.
float diff[R] = {0.0};
for(int i = 0; i < R; i++) {
diff[i] = d[i] - f;
chiSquared += (diff[i] * diff[i]) / f; // or diff ** 2 would work, too!
}
// report results
cout << endl << endl <<
"The actual and expected distributions for each die value" << endl;
cout << "Die Value Difference" << endl;
for(int i = 0; i < R; i++) {
cout << i + 1 << " " << diff[i] << endl;
}
cout << endl;
cout << "Chi-Squared for this distribution is : " << chiSquared << endl;
cout << "This should be between " << (R - (2.0 * sqrt((float) R))) <<
" and " << (R + (2.0 * sqrt((float) R)));
if( chiSquared > (R - (2.0 * sqrt((float) R))) &&
chiSquared < (R + (2.0 * sqrt((float) R))) ) { // test for significance
cout << " and is significant; i.e., passed the test.";
} else {
cout << " and is not significant!!!!";
}
cout << endl;
return 0;
}
// Since rand() is obviously not a very good random number generator for large numbers,
// I looked at http://en.wikipedia.org/wiki/Linear_congruential_generator
long long randValue = (static_cast<int>(time(0)) & 0X7FFFFFFF) | 0X01;
// insures a 32-bit value that is odd
// 2741 could be an initial seed (which happens to be the 400th prime number)
// this could be initialized with time() * 2 + 1 to generate an
// odd-valued starting point.
int myRand() {
randValue = ((1103515245 * randValue) + 12345) & 0X7FFFFFFF; // glibc values from above
return static_cast<int>(randValue);
}
Last edited on
You have to seed it. It's not a bug, rand() doesn't give random numbers by itself, you need to pair it with srand().
Last edited on
rand() isn't random, it's psuedo-random. IIRC most of them use a linear congruential generator.
For much better results and without need to call srand() use rand_s() in windows:
http://msdn.microsoft.com/en-us/library/sxtz2fa8%28v=vs.100%29.aspx
http://msdn.microsoft.com/en-us/library/sxtz2fa8%28v=vs.100%29.aspx
sorry im wrong i was not aware that visual studios made a compiler until i installed code::blocks. and in case someone asks, i have two ides cause i like code::blocks better but i need visual studios for webkit
I edited the original posting to include a "small" program that illustrates the problem. As to the comments:
1. You do not need to call srand() to get (pseudorandom) numbers -- that is only useful to get a new set of random numbers each time you call. I do call srand() in any case!
2. It is not the compiler but the library unless the compiler is smart enough to "compile" rand() dynamically!
3. Yes, it is pseudorandom -- that does not mean that whatever it produces does not appear to be random!
4. Yes, code::blocks should be better (will have to test it, too). It at least produces a 32-bit (pseudo) random number. Why VC++ limits itself to 16 bits is beyond me.
1. You do not need to call srand() to get (pseudorandom) numbers -- that is only useful to get a new set of random numbers each time you call. I do call srand() in any case!
2. It is not the compiler but the library unless the compiler is smart enough to "compile" rand() dynamically!
3. Yes, it is pseudorandom -- that does not mean that whatever it produces does not appear to be random!
4. Yes, code::blocks should be better (will have to test it, too). It at least produces a 32-bit (pseudo) random number. Why VC++ limits itself to 16 bits is beyond me.
just try srand(time(0)); thats is what i have used for gcc and mingw(?) and it always works
It is well-known that the PRG in rand is pretty bad in most (all?) implementations. The documentation often indicates that it is not to be used when you need decent randomness.
closed account (z05DSL3A)
Everyone knows that rand() is not very good ... but a bug? I would guess that for it to be classed as a bug it would have to fail it's spec and I don't recall anything in that that has any specifics about quality.
Since you have "Visual C++ 10", you can ignore rand() (as already suggested) and use the boost/TR1/C++11 random number generators, now in the header <random>
http://msdn.microsoft.com/en-us/library/bb982398(v=vs.100).aspx
http://www.cplusplus.com/reference/std/random/
http://en.cppreference.com/w/cpp/numeric/random
http://msdn.microsoft.com/en-us/library/bb982398(v=vs.100).aspx
http://www.cplusplus.com/reference/std/random/
http://en.cppreference.com/w/cpp/numeric/random
Last edited on
@ResidentBiscuit
Looks like you can using HTTP GET request. http://www.random.org/clients/http/
Looks like you can using HTTP GET request. http://www.random.org/clients/http/
Oh snap, I totally didn't see that page before. I just did some research watching wireshark while generating some numbers to see how it handled it.
What about using the entire range of the generated rand() value, rather than just taking a few low-order digits?
Generates a value from 0 to R.
int rnd = (double) R * (double) rand() / (double) RAND_MAX;Generates a value from 0 to R.
Actually, this is even worse. Since one only generates 32767 possible values between 0 and 1.0, you will be missing virtually all of the possible numbers. I don't remember the specs for floats, but I think it has 21 bits of accuracy, hence you are missing some 2^5 possible values. For doubles, it is far worse since you are missing something like 2^24 possible values.
Topic archived. No new replies allowed.