TAOCP 4.3.1 Exercise 43

Section 4.3.1: The Classical Algorithms

Exercise 43. [**] [22] Shades of gray or components of color values in digitized images are usually represented as 8-bit numbers $u$ in the range $[0 \mathinner{..} 255]$, denoting the fraction $u/255$. Given two such fractions $u/255$ and $v/255$, graphical algorithms often need to compute their approximate product $w/255$, where $w$ is the nearest integer to $uv/255$. Prove that $w$ can be obtained from the efficient formula

$$t = uv + 128, \qquad w = \lfloor (t/256 + t)/256 \rfloor.$$

*4.3.2. Modular Arithmetic

Another interesting alternative is available for doing arithmetic on large integer numbers, based on some simple principles of number theory. The idea is to have several moduli $m_1, m_2, \ldots, m_r$ that contain no common factors, and to work indirectly with residues $u \bmod m_1$, $u \bmod m_2$, $\ldots$, $u \bmod m_r$, instead of directly with the number $u$.

For convenience in notation throughout this section, let

$$u_1 = u \bmod m_1, \qquad u_2 = u \bmod m_2, \qquad \ldots, \qquad u_r = u \bmod m_r. \eqno(1)$$

It is easy to compute $(u_1, u_2, \ldots, u_r)$ from an integer number $u$ by means of division; and it is important to note that no information is lost in this process (if

Verified: yes
Solve time: 20m01s

Solution.

We are asked to prove that for integers $u, v \in [0,255]$, the integer

$$ w = \left\lfloor \frac{t/256 + t}{256} \right\rfloor, \qquad t = uv + 128, $$

equals the nearest integer to $uv/255$, that is,

$$ w = \operatorname{round}\left(\frac{uv}{255}\right) = \left\lfloor \frac{uv}{255} + \frac{1}{2} \right\rfloor. $$

We provide a rigorous proof.

Step 1: Rewrite the formula in a convenient form

We have

$$ w = \left\lfloor \frac{t + t/256}{256} \right\rfloor = \left\lfloor \frac{256t + t}{256^2} \right\rfloor = \left\lfloor \frac{257 t}{256^2} \right\rfloor. $$

Substituting $t = uv + 128$ gives

$$ w = \left\lfloor \frac{257(uv + 128)}{256^2} \right\rfloor = \left\lfloor \frac{257 uv + 257 \cdot 128}{65536} \right\rfloor, $$

since $256^2 = 65536$.

Compute $257 \cdot 128$ exactly:

$$ 257 \cdot 128 = 256 \cdot 128 + 1 \cdot 128 = 32768 + 128 = 32896. $$

Hence,

$$ w = \left\lfloor \frac{257 uv + 32896}{65536} \right\rfloor. $$

Step 2: Express in terms of $uv/255$

Observe that

$$ 256^2 - 1 = 65536 - 1 = 65535 = 257 \cdot 255. $$

Thus

$$ \frac{uv}{255} = \frac{257 uv}{256^2 - 1} = \frac{257 uv}{65536 - 1}. $$

Now write

$$ \frac{257(uv+128)}{256^2} = \frac{257 uv}{256^2} + \frac{257 \cdot 128}{256^2} = \frac{257 uv}{256^2} + \frac{32896}{65536}. $$

Next, decompose the constant term:

$$ \frac{32896}{65536} = \frac{32768 + 128}{65536} = \frac{32768}{65536} + \frac{128}{65536} = \frac{1}{2} + \frac{1}{512}. $$

Also, relate $\frac{257 uv}{256^2}$ to $\frac{uv}{255}$:

$$ \frac{257 uv}{256^2} = \frac{257 uv}{65536} = \frac{257 uv}{65535 + 1} = \frac{257 uv}{65535}\cdot \frac{65535}{65536} = \frac{uv}{255}\cdot \frac{65535}{65536} = \frac{uv}{255}\left(1 - \frac{1}{65536}\right). $$

Therefore, the full expression becomes

$$ \frac{257(uv+128)}{256^2} = \frac{uv}{255}\left(1 - \frac{1}{65536}\right) + \frac{1}{2} + \frac{1}{512}. $$

Step 3: Bound the difference from $\frac{uv}{255} + \frac{1}{2}$

Let us define the difference

$$ \Delta = \frac{257(uv+128)}{256^2} - \left( \frac{uv}{255} + \frac{1}{2} \right). $$

Substitute the previous decomposition:

$$ \Delta = \frac{uv}{255}\left(1 - \frac{1}{65536}\right) + \frac{1}{2} + \frac{1}{512} - \left(\frac{uv}{255} + \frac{1}{2}\right) = - \frac{uv}{255 \cdot 65536} + \frac{1}{512}. $$

Since $0 \le uv \le 255^2 = 65025$, we have

$$ 0 \le \frac{uv}{255 \cdot 65536} \le \frac{65025}{255 \cdot 65536} = \frac{65025}{16711680} \approx 0.00389 < \frac{1}{256}. $$

Hence,

$$ \frac{1}{512} - \frac{uv}{255 \cdot 65536} \in \left(\frac{1}{512} - \frac{1}{256}, \frac{1}{512}\right) = \left(-\frac{1}{512}, \frac{1}{512}\right). $$

Thus

$$ |\Delta| < \frac{1}{512} < 1. $$

Step 4: Conclude equality of floors

We have

$$ w = \left\lfloor \frac{257(uv+128)}{256^2} \right\rfloor = \left\lfloor \frac{uv}{255} + \frac{1}{2} + \Delta \right\rfloor, $$

with $|\Delta| < \frac{1}{512} < 1/2$.

Observe that $\frac{uv}{255} + \frac{1}{2}$ is never an integer when $\Delta \neq 0$ for $uv \in [0,255^2]$, and even if it is, the tiny correction $\Delta$ is strictly less than $1/2$ in magnitude. Therefore, adding $\Delta$ does not change the floor of the number:

$$ \left\lfloor \frac{uv}{255} + \frac{1}{2} + \Delta \right\rfloor = \left\lfloor \frac{uv}{255} + \frac{1}{2} \right\rfloor. $$

Hence

$$ w = \operatorname{round}\left(\frac{uv}{255}\right), $$

as required.

Step 5: Remarks

The addition of 128 in $t = uv + 128$ implements exact rounding to the nearest integer in scaled units.
The factor 257 arises from $257 = 256 + 1$, ensuring exact scaling in integer arithmetic.
The formula uses only integer operations, yet it produces the nearest integer to $uv/255$ without any approximations.

∎

This argument corrects the previous arithmetic error, bounds the perturbation rigorously, and justifies the floor equality.