Is my random number generator failing?

[keanedawg]

So I'm using the classical srand() and rand() functions to generate random numbers to perform a stress test. But when I look at my output, I feel as though the numbers really aren't so random.

#include <iostream>
#include <vector>
#include <time.h> // debugging

using std::vector;
using std::cin;
using std::cout;

int MaxPairwiseProduct(const vector<int>& numbers) {
	int result = 0;
	int n = numbers.size();
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			if (numbers[i] * numbers[j] > result) {
				result = numbers[i] * numbers[j];
			}
		}
	}
	return result;
}

int main() {
	srand(time(NULL)); // debugging
	while (true) { // debugging
	    


		int n;
		//cin >> n;
		n = rand() % 200000 + 2; // debugging
		vector<int> numbers(n);
		for (int i = 0; i < n; ++i) {
			//cin >> numbers[i];
			numbers[i] = rand() % 100000;
		}

		int result = MaxPairwiseProduct(numbers);
		cout << result << "\n";
	} // debugging

	char wait;
	cin >> wait;
	return 0;
}

So, here's what's happening, I'm using a lousy algorithm to calculate the maximum product (AKA the greatest product between 2 numbers) in a vector of size N. So if I have a vector of 2, 5, 13, and 8. The max product would be 13 * 8 since those multiply to create the highest possible value.

So, my sizes can get pretty large (I mean, I consider 200000 to be pretty large). And you definitely notice the difference in different sizes. So some calculations take a few minutes and others take a few seconds. That indicates that there is some randomness in the sizes. HOWEVER, look at the results of all my different products.

It would probably be best if I pipe but I'm on visual studio and I'm lazy

1073446930
1073577990
1072922670
1073610755

And as you can see, all these max Multiplying values are very very similar. In fact, they are so similar I suspect it's not really random. Or maybe not. Maybe this is a normal distribution with large groups of numbers? I suspect my random numbers are not so random.

So sorry for the long explanations. Essentially I'm asking why my output doesn't seem very random. All the numbers are quite similar in value.

[Zhuge]

Have you tried outputting at least the two numbers you are multiplying? Or perhaps just the results of each call? That should make it very clear if you are not getting random-looking data generated.

[keanedawg]

Good idea. I'll try that.

[cire]

std::cout << "Max value returned by rand: " << RAND_MAX << '\n' ;

On VC++, for instance, this value is the minimum required by the standard which is pretty close to the square root of the values you're getting.

Btw, better algorithm:

#include <algorithm>
#include <vector>
#include <time.h> // debugging

using std::vector;
using std::cin;
using std::cout;

int main() {
    srand(time(NULL)); // debugging

    vector<int> numbers;
    numbers.reserve(200000 + 2);

    for (auto i = 0u; i < 10; ++i )
    {
        int n;
        //cin >> n;
        n = rand() % 200000 + 2; // debugging
        numbers.resize(n);
        for (auto& num : numbers) num = rand() % 100000;
        sort(numbers.begin(), numbers.end());
        
        auto sz = numbers.size();
        std::cout << numbers[sz - 1] << " * " << numbers[sz - 2] << " = " << numbers[sz - 1] * numbers[sz - 2] << '\n';
    } // debugging
}