# Exercise 5.1.2

$\star$ Describe an implementation of the procedure

`RANDOM(a,b)`

that only makes calls to`RANDOM(0,1)`

. What is the expected running time of your procedure as a function of $a$ and $b$?

Let $n = b - a$. The algorithm is as follows:

- We find the smallest integer $c$ such that $2^c \ge n$ ($c = \lceil \ln{n} \rceil$)
- We call
`RANDOM(0, 1)`

$c$ times to and get a $c$-digit binary number $r$ - If $r > n$ we go back to the previous step
- Otherwise we return $a + r$

This produces a uniformly random number in that range. However, there is a
possibility to have to repeat step 2. There is $p = n/2^c$ chance of not having
to repeat step two. The geometric distribution suggests that on average it
takes $1/p$ trials before we get such a number, that is $2^c/n$ trials. Since
we perform $c$ calls to `RANDOM(0, 1)`

on each trial, the expected running time
is

$$ \O\bigg(\frac{2^c}{n} c\bigg) = \O\bigg(\frac{\ln(b-a)2^{\ln(b-a)}}{b-a}\bigg) = \O(\ln(b-a)) $$