uniform-random

/* Very rudimentary test of randomness */
void testRandom(randFunc rF, int a, int b)
{
    if (rF == NULL) return;

    float   *dist;
    dist = malloc(sizeof(float) * (b-a+1));

    int num = b-a+1;
    for (int i=0; i<num; i++) dist[i] = 0.0;

    for (int i=0; i<TRIALS; i++) {
        int res = uniformRandom1(a, b);
        dist[res-a]++;
    }

    /* Each number must have equal distribution */
    for (int i=0; i<num; i++) {
        printf("%d = %f\n", i+a, dist[i]/TRIALS);
    }
}

int main(int argc, char *argv[])
{
    if (argc !=3) {
        printf("Invalid args: ./main a b");
        return 1;
    }

    srand(time(NULL));

    int a = atoi(argv[1]);
    int b = atoi(argv[2]);

    if (b == a) return 1;

    testRandom(uniformRandom2, a, b);

    printf("\n");

    return 1;
}

Here's the missing portion of code not pasted above.

#define TRIALS 10000
typedef int (*randFunc)(int, int);

int rand0or1()
{
return rand()%2;
}

/* EPI's solution*/
int uniformRandom2(int a, int b)
{
int res = 0;
int num = b-a+1;

for(int i=0; (1<<i) < num; i++) {
    res |= rand0or1();
    res <<= 1;
}
res += a;

return res;

}

I tried this with a simple shell command on Java, did not see a problem, will contact @thl to see what's up with C++

[adnanaziz@dev9847.prn1 ~/tmp] java Test 1 10 | grep random | sort | uniq -c
100 random result = 1
101 random result = 10
115 random result = 2
106 random result = 3
96 random result = 4
83 random result = 5
82 random result = 6
107 random result = 7
105 random result = 8
105 random result = 9

this is not our solution, we have a check for the resulting number lying in num

YOUR CODE:

int uniformRandom2(int a, int b)
{
int res = 0;
int num = b-a+1;

for(int i=0; (1<<i) < num; i++) {
res |= rand0or1();
res <<= 1;
}
res += a;

return res;
}

OUR CODE:

int UniformRandom(int lower_bound, int upper_bound) {
int number_of_outcomes = upper_bound - lower_bound + 1, result;
do {
result = 0;
for (int i = 0; (1 << i) < number_of_outcomes; ++i) {
// ZeroOneRandom() is the provided random number generator.
result = (result << 1) | ZeroOneRandom();
}
} while (result >= number_of_outcomes);
return result + lower_bound;
}