# A small question about generating random variable with geometric distribution

I was reading Professor Knuth's Volume 2 (page 136) about generating a geometrically distributed random variable $$N$$ (with $$p$$ as the probability of success). Basically, the idea is to generate a uniformly distributed random variable $$U$$ in $$[0,1]$$. Then, we can apply a simple formula $$N = \left\lceil\frac{\ln(U)}{\ln(1-p)}\right\rceil$$.

Additionally, Professor Knuth mentions a special case when $$p=1/2$$. Then, the aforementioned formula transforms into $$N = \left\lceil -\log_2 U \right\rceil$$. And then he states that N is simply "one more than the number of leading zero bits in the binary representation of $$U$$. I'm confused by the last statement since I tried different interpretations of this statement and nothing gives the correct result:

1. Let's interpret the statement as it is. We consider the binary representation of real number $$U$$. On modern machines, this is either float or double. If we take float, then we have 1 bit for sign and then 8 bits for exponent. If we consider $$U=0.25$$ and $$U=0.5$$, we will see that the first 8 bits of their corresponding binary representations are $$7d$$ and $$7e$$, respectively. Binary representation have the same number of leading zeros, although $$\log_2(1/0.25) \not= \log_2(1/0.5)$$.

2. Let's assume that Knuth means binary representation of $$\left\lceil 1/U \right \rceil$$. Then, $$\left\lceil \log_2 \left\lceil 1/U \right \rceil \right \rceil$$ is exactly what we need. But $$\left\lceil \log_2(x) \right \rceil = 32 - \mathrm{nlz}(x-1)$$ for 32-bit integer, where $$\mathrm{nlz}$$ is the number of leading zeros. So this is again not what is originally proposed by the author.

Maybe you understand what was meant by Professor Knuth? Could you please explain it? Thanks in advance!

• If $$1/2 \leq U < 1$$ then $$\lceil -\log_2 U \rceil = 1$$.
• If $$1/4 \leq U < 1/2$$ then $$\lceil -\log_2 U \rceil = 2$$.
• If $$1/8 \leq U < 1/4$$ then $$\lceil -\log_2 U \rceil = 3$$.
• $$1/2 \le U < 1$$ if the binary expansion of $$U$$ starts $$0.1$$.
• $$1/4 \le U < 1/2$$ if the binary expansion of $$U$$ starts $$0.01$$.
• $$1/8 \le U < 1/4$$ if the binary expansion of $$U$$ starts $$0.001$$.