#include <stdlib.h>
#include <cmath>
#include <iostream>
using namespace std;
int rangeRandomAlg1 (int min, int max)
{
static const double s_invRandMax = 1.0/((double)RAND_MAX + 1.0);
return min + (int)(((double)(max + 1 - min))*rand()*s_invRandMax);
}
int rangeRandomAlg2 (int min, int max)
{
int n = max - min + 1;
int remainder = RAND_MAX % n;
int x, output;
do
{
x = rand();
output = x % n;
} while (x > RAND_MAX - remainder);
return min + output;
}
int main ()
{
static const int s_numBuckets = 10; // the number of "buckets"
static const int s_numBalls = 100; // the number of "balls"
int buckets[s_numBuckets];
double idealProbPerBucket = 1.0/s_numBuckets;
double maxDevFromIdealProb;
// Testing algorithm 1
cout << "Testing with floating-point mapping:" << endl;
for (int i = 0; i < s_numBuckets; i++)
{
buckets[i] = 0;
}
srand(0);
for (int i = 0; i < s_numBalls; i++)
{
buckets[rangeRandomAlg1(0, s_numBuckets - 1)]++;
}
maxDevFromIdealProb = -1.0;
for (int i = 0; i < s_numBuckets; i++)
{
double prob = ((double)buckets[i])/s_numBalls;
cout << "Probability for bucket #" << i << ": " << prob << endl;
double devFromIdealProb = fabs(prob - idealProbPerBucket);
if ( devFromIdealProb > maxDevFromIdealProb )
{
maxDevFromIdealProb = devFromIdealProb;
}
}
cout << ">>> Maximum deviation from the ideal probability: " << maxDevFromIdealProb << endl;
cout << endl;
// Testing algorithm 2
cout << "Testing with Java's algorithm:" << endl;
for (int i = 0; i < s_numBuckets; i++)
{
buckets[i] = 0;
}
srand(0);
for (int i = 0; i < s_numBalls; i++)
{
buckets[rangeRandomAlg2(0, s_numBuckets - 1)]++;
}
maxDevFromIdealProb = -1.0;
for (int i = 0; i < s_numBuckets; i++)
{
double prob = ((double)buckets[i])/s_numBalls;
cout << "Probability for bucket #" << i << ": " << prob << endl;
double devFromIdealProb = fabs(prob - idealProbPerBucket);
if ( devFromIdealProb > maxDevFromIdealProb )
{
maxDevFromIdealProb = devFromIdealProb;
}
}
cout << ">>> Maximum deviation from the ideal probability: " << maxDevFromIdealProb << endl;
return 0;
}