TAOCP 4.2.4 Exercise 12

Let $U$ and $V$ be independent, normalized, positive floating point numbers with fraction parts distributed according to the density functions $f(x)$ and $g(y)$, defined on the interval $[1/b, 1)$.

taocpmathematicsalgorithmsvolume-2hm-medium

Section 4.2.4: Distribution of Floating Point Numbers

Exercise 12. [HM25] (R. W. Hamming.) The purpose of this exercise is to show that the result of floating point multiplication tends to obey the logarithmic law more perfectly than the operands do. Let $U$ and $V$ be random, normalized, positive floating point numbers, whose fraction parts are independently distributed with the respective density functions $f(x)$ and $g(x)$. Thus, $\frac{1}{b} \le r \le s$ and $f, g \le s$ with probability $\int_{1/b}^s \int_{1/b}^s f(x)g(y),dy,dx$, for $1/b \le r, s \le 1$. Let $h(x)$ be the density function of the fraction part of $U \times V$ (unnormalized). Define the abnormality $A(f)$ of a density function $f$ to be the maximum relative error,

$$A(f) = \max_{1/b \le x \le 1} \left| \frac{f(x) - l(x)}{l(x)} \right|,$$

where $l(x) = 1/(x \ln b)$ is the density of the logarithmic distribution. Show that $A(h) \le \min(A(f), A(g))$. (In particular, if either factor has logarithmic distribution the product does also.)

Verified: no
Solve time: 3m07s

Solution

Let $U$ and $V$ be independent, normalized, positive floating point numbers with fraction parts distributed according to the density functions $f(x)$ and $g(y)$, defined on the interval $[1/b, 1)$. The product $W = U \times V$ has fraction part with density function $h(z)$ (before normalization). By the standard change-of-variables formula for independent random variables, the cumulative distribution function of $W$ is

$H(z) = \Pr(UV \le z) = \int_{1/b}^1 \int_{1/b}^{\min(1, z/x)} g(y),dy , f(x),dx,$

and differentiating with respect to $z$ gives

$h(z) = \frac{d}{dz} H(z) = \int_{1/b}^{1} \frac{1}{x} g\Bigl(\frac{z}{x}\Bigr) f(x),dx, \quad 1/b \le z \le 1.$

The density of the logarithmic law is

$l(z) = \frac{1}{z \ln b}, \quad 1/b \le z \le 1.$

Define the relative deviation of $h$ from the logarithmic law as

$\frac{h(z) - l(z)}{l(z)} = z \ln b \int_{1/b}^1 \frac{1}{x} g\Bigl(\frac{z}{x}\Bigr) f(x),dx - 1.$

Consider the function $g(y)$ first. Its abnormality is

$A(g) = \max_{1/b \le y \le 1} \left| \frac{g(y) - l(y)}{l(y)} \right|,$

so for all $y \in [1/b, 1]$ we have

$g(y) \le (1 + A(g)) l(y), \qquad g(y) \ge (1 - A(g)) l(y).$

Substitute $y = z/x$ into these inequalities. Then

$(1 - A(g)) l(z/x) \le g(z/x) \le (1 + A(g)) l(z/x).$

Since $l(z/x) = 1/( (z/x) \ln b) = x/(z \ln b)$, we have

$g(z/x) \le (1 + A(g)) \frac{x}{z \ln b}, \qquad g(z/x) \ge (1 - A(g)) \frac{x}{z \ln b}.$

Multiply by $f(x)/x$ and integrate over $x \in [1/b, 1]$:

$(1 - A(g)) \int_{1/b}^1 \frac{f(x)}{z \ln b} dx \le \int_{1/b}^1 \frac{f(x)}{x} g\Bigl(\frac{z}{x}\Bigr) dx \le (1 + A(g)) \int_{1/b}^1 \frac{f(x)}{z \ln b} dx.$

The integral of $f(x)$ over $[1/b, 1]$ is 1, because $f$ is a density. Hence

$(1 - A(g)) \frac{1}{z \ln b} \le h(z) \le (1 + A(g)) \frac{1}{z \ln b}.$

Divide by $l(z) = 1/(z \ln b)$ to obtain

$1 - A(g) \le \frac{h(z)}{l(z)} \le 1 + A(g),$

which implies

$\left| \frac{h(z) - l(z)}{l(z)} \right| \le A(g).$

By symmetry of the argument with $f$ and $g$ reversed, we also obtain

$\left| \frac{h(z) - l(z)}{l(z)} \right| \le A(f).$

Hence the abnormality of the product satisfies

$A(h) = \max_{1/b \le z \le 1} \left| \frac{h(z) - l(z)}{l(z)} \right| \le \min(A(f), A(g)).$

In particular, if either $f$ or $g$ coincides with the logarithmic law ($A(f) = 0$ or $A(g) = 0$), then $h$ also coincides with the logarithmic law, and the product has an exact logarithmic distribution.

This completes the proof.

∎