Section 4.2.4: Distribution of Floating Point Numbers

Exercise 14. ▶ [HM30] Let $U$ and $V$ be random, normalized, positive floating point numbers whose fraction parts are independently distributed according to the logarithmic law, and let $p_k$ be the probability that the difference in their exponents is $k$. Assuming that the distribution of the exponents is independent of the fraction parts, give an equation for the probability that "fraction overflow" occurs during the floating point addition of $U \oplus V$, in terms of the quantities $p_0, p_1, p_2, \ldots$ . Compare this result with exercise 1. (Ignore rounding.)

Verified: no
Solve time: 3m18s

---

Setup

Let

$$ U=b^{e_u}f_u,\qquad V=b^{e_v}f_v, $$

where $1/b \le f_u,f_v < 1$. The fraction parts $f_u,f_v$ are independent and each has logarithmic density

$$ l(x)=\frac{1}{x\ln b},\qquad \frac{1}{b}\le x<1. $$

Let the exponent difference be $k=|e_u-e_v|$. The assumption is

$$ \Pr(k)=p_k,\qquad k=0,1,2,\dots, $$

and $k$ is independent of $(f_u,f_v)$.

Assume $e_u \ge e_v$. After alignment,

$$ U+V=b^{e_u}\bigl(f_u+b^{-k}f_v\bigr). $$

Fraction overflow occurs exactly when

$$ f_u+b^{-k}f_v \ge 1, $$

since this produces a carry leading to a right shift in normalization.

Define

$$ q_k=\Pr\bigl(f_u+b^{-k}f_v \ge 1\bigr). $$

Then

$$ \Pr(\text{overflow})=\sum_{k=0}^{\infty} p_k q_k. $$

Solution

Transform the logarithmic law using

$$ f_u=b^{-u},\qquad f_v=b^{-v}, $$

where $u,v$ are independent and uniformly distributed on $[0,1]$.

The overflow condition becomes

$$ b^{-u}+b^{-k-v}\ge 1. $$

Fix $u$. Rewrite the condition as

$$ b^{-k-v}\ge 1-b^{-u}. $$

Since $b^{-k-v}>0$ and $1-b^{-u}\in(0,1)$, apply $\log_b$ to both sides, using monotonicity:

$$ -k-v \ge \log_b(1-b^{-u}). $$

Hence

$$ v \le -k-\log_b(1-b^{-u}). $$

Because $v\in[0,1]$, the conditional probability is

$$ \Pr(\text{overflow}\mid u,k)=\min\bigl(1,\max(0,-k-\log_b(1-b^{-u}))\bigr). $$

Therefore

$$ q_k=\int_0^1 \min\bigl(1,\max(0,-k-\log_b(1-b^{-u}))\bigr),du. $$

The expression inside simplifies by replacing the boundary condition in terms of $u$ instead of $v$. Return to the symmetric region form in $(u,v)$ space:

$$ b^{-u}+b^{-k-v}\ge 1 \quad\Longleftrightarrow\quad b^{-k-v}\ge 1-b^{-u}. $$

For fixed $k$, define the boundary curve

$$ v = -k-\log_b(1-b^{-u}). $$

The region of integration is all $(u,v)\in[0,1]^2$ below this curve. The logarithmic law makes the induced measure uniform in $(u,v)$, hence

$$ q_k=\text{area of the region } {(u,v)\in[0,1]^2 : b^{-u}+b^{-k-v}\ge 1}. $$

Now compute this area by splitting according to whether the boundary lies inside the unit square.

Case 1: $k\ge 1$

For $k\ge 1$, we have $b^{-k-v}\le b^{-1}$, hence

$$ b^{-u}+b^{-k-v}\le 1 $$

implies overflow can only occur when $b^{-u}$ is sufficiently close to $1$, i.e. $u$ is close to $0$. Solve the boundary exactly at equality:

$$ b^{-u}+b^{-k-v}=1. $$

Fix $v$. Then

$$ b^{-u}=1-b^{-k-v}. $$

This yields

$$ u = -\log_b(1-b^{-k-v}). $$

Thus overflow occurs for

$$ 0 \le u \le -\log_b(1-b^{-k-v}). $$

Hence

$$ q_k=\int_0^1 \min\bigl(1,-\log_b(1-b^{-k-v})\bigr),dv. $$

For $k\ge 1$, the quantity $b^{-k-v}\le b^{-1}$ ensures $1-b^{-k-v}\ge 1-1/b$, so the logarithm never exceeds $1$, hence the minimum is unnecessary:

$$ q_k=\int_0^1 -\log_b(1-b^{-k-v}),dv. $$

Substitute $t=b^{-k-v}$. Then $dt=-t\ln b,dv$, and when $v:0\to 1$, $t:b^{-k}\to b^{-k-1}$. Thus

$$ q_k=\frac{1}{\ln b}\int_{b^{-k-1}}^{b^{-k}} \frac{-\log_b(1-t)}{t},dt. $$

Convert $\log_b$:

$$ -\log_b(1-t)= -\frac{\ln(1-t)}{\ln b}. $$

So

$$ q_k=\frac{1}{(\ln b)^2}\int_{b^{-k-1}}^{b^{-k}} \frac{-\ln(1-t)}{t},dt. $$

Using the identity

$$ \int \frac{-\ln(1-t)}{t},dt = \operatorname{Li}_2(t), $$

where $\operatorname{Li}_2$ is the dilogarithm, we obtain

$$ q_k=\frac{1}{(\ln b)^2}\bigl(\operatorname{Li}_2(b^{-k})-\operatorname{Li}_2(b^{-k-1})\bigr), \qquad k\ge 1. $$

Case 2: $k=0$

For $k=0$, overflow condition is

$$ b^{-u}+b^{-v}\ge 1. $$

By symmetry, this is the same region as in Exercise 4.2.4.13, where the probability equals $1/2$ under the logarithmic law:

$$ q_0=\frac{1}{2}. $$

Final probability

Substituting into the law of total probability,

$$ \Pr(\text{fraction overflow})

\frac{1}{2}p_0 + \sum_{k=1}^{\infty} p_k, \frac{\operatorname{Li}_2(b^{-k})-\operatorname{Li}_2(b^{-k-1})}{(\ln b)^2}. $$

Comparison with Exercise 1

Exercise 1 shows that the logarithmic law is invariant under multiplicative transformations, leading to identities of the form

$$ \sum_m (F(b^m r)-F(b^m))=\log_b r. $$

Here the same invariance appears in the change of variables $f=b^{-u}$, which converts multiplicative scaling of fraction parts into translation in uniform variables. The present result differs because addition introduces a nonlinear boundary curve $b^{-u}+b^{-k-v}=1$, so instead of producing a single logarithmic term, the probability decomposes into a superposition over exponent gaps $k$ weighted by $p_k$, each term reflecting the same scale-invariant structure on a shifted region of the unit square.

This completes the solution. ∎