Given function
rand7
returns random integer in interval[0, 6]
. Your task is to implement functionrand5
which should return random integer in interval[0, 4]
using functionrand7
.
This is a question from my book. So, this is how I solved it (the algorithm is written in C):
int rand5(void){
return (int)(rand7() * 4. / 6. + .5);
}
Basically, I just scaled the interval to [0, 4]
. The + .5
part is to properly round to nearest integer (not just to truncate decimals). However, this is not correct solution.
Solution in my book is very weird to me. This is how they did it:
int rand5(void){
int a;
while((a = rand7()) > 4);
return a;
}
The book says that the algorithm I came up with works only when interval is significantly large (so the probability will not change a lot). For smaller intervals (like this one) there is no other solution.
Well, it sounds pretty weird that there is no other solution. What is the time complexity of this algorithm? For my algorithm, time complexity is O(r)
where r
is time complexity of rand7
. But what is the complexity of their algorithm?
The complexity should be O(r * n)
where n
is, according to the definition of the time complexity, the largest possible number of loop iterations. But what is the largest possible number of iterations? We know nothing about function rand7
and the way it is implemented, so the largest possible number of iterations is infinity. So, the complexity of this algorithm is O(infinity)
which doesn't make any sense.
Of course, if rand7
if properly implemented, it will for sure return at lest one time number in interval [0, 4]
. But, theoretically, it can return any number of consecutive numbers which belong in interval [5, 6]
. Is then complexity indeterminate?
Also, how is that possible that "there is no other solution"? To generalize, is there any algorithm which can give an integer random number (with equal probability for all numbers) from interval [0, k]
for given number k
using only rand2
(for example), such that the algorithm should work in finite time complexity?
Edit
Ok, if I need to summarize this, the question is as title says, what is the complexity of this algorithm?
rand7
produces a uniform distribution, it will take seven calls torand7
to get five numbers in the range [0..4]. $\endgroup$ – Jim Mischel Jun 9 '17 at 4:24