Created
February 6, 2017 14:15
-
-
Save umbs/5b1557b585d2ed068d7169554db1e62d to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* 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; | |
} |
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;
}
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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