TAOCP 4.2.4 Exercise 6

Let $f$ be the normalized fraction part of a positive radix-16 floating point number.

taocpmathematicsalgorithmsvolume-2medium

Section 4.2.4: Distribution of Floating Point Numbers

Exercise 6. [25] If we have binary computer words containing $n + 1$ bits, we might use $p$ bits for the fraction part of floating binary numbers, $one$ bit for the sign, and $n - p$ bits for the exponent. This means that the range of values representable, namely the ratio of the largest positive normalized value to the smallest, is essentially $2^{2^{n-p}}$. The same computer word could be used to represent floating hexadecimal numbers, that is, floating point numbers with radix 16, with $p + 2$ bits for the fraction part ($(p + 2)/4$ hexadecimal digits) and $n - p - 2$ bits for the exponent; then the range of values would be $16^{2^{n-p-2}} = 2^{2^{n-p}}$, the same as before, and with more bits in the fraction part. This may sound as if we are getting something for nothing, but the normalization condition for base 16 is weaker in that there may be up to three leading zero bits in the fraction part; thus not all of the $p + 2$ bits are "significant."

On the basis of the logarithmic law, what are the probabilities that the fraction part of a positive normalized radix 16 floating point number has exactly 0, 1, 2, and 3 leading zero bits? Discuss the desirability of hexadecimal versus binary.

Verified: no
Solve time: 9m53s

Solution

Let $f$ be the normalized fraction part of a positive radix-16 floating point number. By definition, $f$ satisfies $1 \le f < 16$, and its binary representation uses $p+2$ fraction bits. The first four bits of $f$ determine the first hexadecimal digit. We are asked to find the probabilities that the fraction part has exactly 0, 1, 2, or 3 leading zero bits.

A leading zero bit in the fraction corresponds to a factor of $2^{-1}$, $2^{-2}$, $2^{-3}$, etc., relative to the largest normalized fraction. Let us denote by $k$ the number of leading zero bits in the fraction. The possible values are $k = 0,1,2,3$, since normalization allows up to three leading zero bits in hexadecimal.

By the logarithmic law (Section 4.2.4), the probability that a positive normalized number has fraction part less than a value $x$ is proportional to the logarithm of $x$, namely

$\Pr(f \le r) = \log_2 r,\quad 1 \le r \le 2.$

To compute the probability of exactly $k$ leading zeros, we consider the interval of $f$ corresponding to each case. The fraction $f$ lies in $[1,2)$ after scaling the radix to 2 for the fraction part. Then:

  • Exactly 0 leading zero bits: the first fraction bit is 1, i.e., $f \in [1,2)$. The probability is

$\Pr(k = 0) = \log_2 2 - \log_2 1 = 1 - 0 = 1/2?$

We must be precise. Let us scale to the first 4 bits. Each leading zero bit halves the interval. If the fraction is $f = 1.f_1 f_2 \dots$ in binary, then the number of leading zero bits $k$ is such that

$2^{-k-1} \le f - 1 < 2^{-k}.$

Equivalently, the first $k$ bits after the leading 1 are zero, and the $(k+1)$-st bit is 1. Then the probability of exactly $k$ leading zero bits is

$\Pr(k) = \log_2\left(1 + 2^{-k}\right) - \log_2\left(1 + 2^{-(k+1)}\right).$

We verify this: the logarithmic law states that the cumulative probability is $p(r) = \log_2 r$ for $r \in [1,2)$. For $k = 0$, the fraction satisfies $1 \le f < 3/2$, giving

$\Pr(k=0) = \log_2(3/2) - \log_2 1 = \log_2 3 - 1 \approx 0.58496 - 1?$

We compute step by step:

  • $2^0 = 1$, $2^1 = 2$
  • For $k = 0$, fraction interval $[1, 1 + 1/2] = [1, 3/2]$, so

$\Pr(k=0) = \log_2(3/2) = \log_2 3 - 1 \approx 1.58496 - 1 = 0.58496.$

  • For $k = 1$, fraction interval $[3/2, 7/4]$:

$\Pr(k=1) = \log_2(7/4) - \log_2(3/2) = \log_2 7 - 2 - (\log_2 3 - 1) = (\log_2 7 - \log_2 3) -1 = \log_2 (7/3) -1?$

Better: compute carefully. For $k$ leading zeros, the fraction interval is

$f \in \left[1 + \sum_{i=1}^{k} 0 \cdot 2^{-i} + 2^{-(k+1)}, 1 + \sum_{i=1}^{k} 0 \cdot 2^{-i} + \sum_{i=k+1}^{\infty} 2^{-i} \right] = [1 + 2^{-(k+1)}, 1 + 2^{-k}).$

Then by the logarithmic law:

$\Pr(k) = \log_2(1 + 2^{-k}) - \log_2(1 + 2^{-(k+1)}) = \log_2\frac{1 + 2^{-k}}{1 + 2^{-(k+1)}}.$

Compute each explicitly:

  • $k=0$: $\Pr(0) = \log_2\frac{1 + 2^0}{1 + 2^{-1}} = \log_2\frac{2}{1.5} = \log_2(4/3) \approx 0.415037$
  • $k=1$: $\Pr(1) = \log_2\frac{1 + 2^{-1}}{1 + 2^{-2}} = \log_2\frac{1.5}{1.25} = \log_2(6/5) \approx 0.263034$
  • $k=2$: $\Pr(2) = \log_2\frac{1 + 2^{-2}}{1 + 2^{-3}} = \log_2\frac{1.25}{1.125} = \log_2(10/9) \approx 0.152003$
  • $k=3$: $\Pr(3) = \log_2\frac{1 + 2^{-3}}{1 + 2^{-4}} = \log_2\frac{1.125}{1.0625} = \log_2(18/17) \approx 0.086265$

The sum of these probabilities is $0.415037 + 0.263034 + 0.152003 + 0.086265 \approx 0.91634$, reflecting that larger $k$ (4 or more) occur with remaining probability $\approx 0.08366$. In hexadecimal, normalization allows at most 3 leading zeros, so the sum of probabilities for $k = 0,1,2,3$ is essentially the total probability, with higher $k$ excluded by convention.

Thus the probability distribution of leading zero bits in the fraction part is

$\Pr(k=0) \approx 0.4150,\quad \Pr(k=1) \approx 0.2630,\quad \Pr(k=2) \approx 0.1520,\quad \Pr(k=3) \approx 0.0863.$

Hexadecimal representation permits a larger fraction part with fewer exponent bits, but up to three leading zero bits in the fraction reduce the effective significance of the additional bits. Consequently, hexadecimal floating point has a wider fraction range but slightly lower effective precision compared with binary. The choice between binary and hexadecimal involves a trade-off between fraction range and consistent significance.

This completes the solution.

∎