Rounding and Machine Epsilon

Rounding and Machine Epsilon

The floating-point number line is a discrete set of points. Any real number $x$ that does not fall exactly on one of those points must be rounded to the nearest one. This section formalises that process and introduces machine epsilon $\xi_M$ which represents the worst-case relative rounding error.

---

The Floating-Point Representation $fl(x)$

Given a real number $x$, its floating-point representation $fl(x)$ is the nearest number in the system $F$:

$fl(x) = \text{the closest element of } F \text{ to } x$

Because the floating-point number line is discrete, values that fall between representable numbers are rounded to the closest available point. For example, a number closer to the left bound will round down, while a number closer to the right bound will round up.

As shown above:

• $0.100001$ is closer to $0.100$ than to $0.101$. It rounds down to $0.100$, which we define as truncation or rounding down.
• $0.100101$ is closer to $0.101$ than to $0.100$. It rounds up to $0.101$, which we define as rounding up.

Tie-Breaking Rule

When $x$ falls exactly halfway between two adjacent floating-point numbers, standard proximity rounding can’t decide. To prevent statistical bias from always rounding up or always rounding down, IEEE 754 uses the round-to-nearest-even (or banker’s rounding) rule.

The number is rounded to the adjacent floating-point value whose last digit is even (which means it ends in 0 in binary).

As shown above:

• $0.1001$ is the exact midpoint between $0.100$ and $0.101$. It rounds down to $0.100$ because it ends in 0 (even).
• $0.1011$ is the exact midpoint between $0.101$ and $0.110$. It rounds up to $0.110$ because it ends in 0 (even).

Quick Tricks for Binary Rounding

When rounding a binary fraction to $m$ mantissa bits, inspect the bits immediately following the $m$-th position:

• Round Down (Truncate)
  If the immediate next bit (the $(m+1)$-th bit) is 0. The value is closer to the lower representable number, regardless of any bits that follow.

• Round Up
  If the immediate next bit is 1 AND there are additional non-zero bits after it. This means the value is strictly greater than the halfway point.

• Round to Nearest Even (Tie-Breaker)
  If the immediate next bit is 1 AND it is the only remaining bit (or all subsequent bits are 0). The value sits exactly at the midpoint, so you round up or down to ensure the final $m$-th bit is 0 (even).

Scale-Invariant (Relative) Error

$\delta = \frac{|fl(x) - x|}{|x|}$

Rearranging:

$fl(x) - x = \delta \cdot x \qquad\Longrightarrow\qquad \boxed{fl(x) = x\,(1 + \delta)}$

This compact form says: $fl(x)$ is $x$ multiplied by a factor that deviates from 1 by at most $\delta$.

---

Machine Epsilon $\xi_M$

Machine epsilon is the maximum possible relative rounding error in a floating-point system:

$\xi_M = \max_x \; \delta = \max_x \frac{|fl(x) - x|}{|x|}$

To find the worst-case (maximum) relative error, our goal is to maximize the numerator (the absolute rounding error) and minimize the denominator (the true value $x$).

The absolute rounding error is maximized when a number falls exactly halfway between two adjacent representable numbers. The minimum value depends on the floating-point convention being used.

Deriving $\xi_M$: Standard Form

In the Standard Form representation, the mantissa is written as $0.d_1 d_2 \ldots d_m$ where $d_1 \neq 0$. Let’s assume $m=3$ and $\beta=2$.

• Minimize Denominator: The smallest normalized magnitude is $|x|_{\min} = 0.100_2 = \beta^{-1}$.
• Maximize Numerator: The maximum absolute error $(\text{R.E.})_{\max}$ is half the distance between $0.100$ and $0.101$. $(\text{R.E.})_{\max} = \frac{1}{2} \times (0.101 - 0.100) = \frac{1}{2} \times \beta^{-3} = \frac{1}{2}\beta^{-m}$

Dividing the maximum error by the minimum value gives:

$$\xi_M = \frac{\frac{1}{2}\,\beta^{-m}}{\beta^{-1}} = \frac{1}{2}\,\beta^{1-m}$$

Deriving $\xi_M$: Normalized Form

In this Normalized Form, let’s look at an $m=3$ setup where the mantissa is padded (e.g., $0.1 d_2 d_3 d_4$).

• Minimize Denominator: The smallest magnitude is $|x|_{\min} = 0.1000_2 = \beta^{-1}$.
• Maximize Numerator: The maximum error is half the distance between $0.1000$ and $0.1001$. $(\text{R.E.})_{\max} = \frac{1}{2} \times (0.1001 - 0.1000) = \frac{1}{2} \times \beta^{-4} = \frac{1}{2}\beta^{-(m+1)}$

Dividing the two yields:

$$\xi_M = \frac{\frac{1}{2}\,\beta^{-(m+1)}}{\beta^{-1}} = \frac{1}{2}\,\beta^{-m}$$

Deriving $\xi_M$: De-normalized Form

In the De-normalized (or implicit leading bit) form, numbers are represented as $1.d_1 d_2 d_3$. Let’s again use $m=3$.

• Minimize Denominator: The smallest magnitude is $|x|_{\min} = 1.000_2 = \beta^0 = 1$.
• Maximize Numerator: The maximum error is half the distance between $1.000$ and $1.001$. $(\text{R.E.})_{\max} = \frac{1}{2} \times (1.001 - 1.000) = \frac{1}{2} \times \beta^{-3} = \frac{1}{2}\beta^{-m}$

Dividing them provides:

$$\xi_M = \frac{\frac{1}{2}\,\beta^{-m}}{\beta^0} = \frac{1}{2}\,\beta^{-m}$$

Comparison Summary

Convention	$\lvert x\rvert_{\min}$	$(\text{R.E.})_{\max}$	$\xi_M$
Standard Form	$\beta^{-1}$	$\frac{1}{2}\beta^{-m}$	$\frac{1}{2}\beta^{1-m}$
Normalized Form	$\beta^{-1}$	$\frac{1}{2}\beta^{-(m+1)}$	$\frac{1}{2}\beta^{-m}$
De-normalized Form	$\beta^0$	$\frac{1}{2}\beta^{-m}$	$\frac{1}{2}\beta^{-m}$

Notice how both the Normalized and De-normalized forms achieve a tighter (smaller) machine epsilon, granting higher precision by effectively utilizing the available bits.

---

Key Property

For any representable number $x$:

$\delta \le \xi_M$

That is, every individual rounding satisfies the machine epsilon bound.

---

Quick Example

$\beta = 2$, $m = 3$, $e_{\min}=-1$, $e_{\max}=2$, Convention 1.

Between $(0.100)_2 \times 2^0 = 0.5$ and $(0.101)_2 \times 2^0 = 0.625$:

• Gap $= 0.125$
• Midpoint $= 0.5625$
• A real value of $x = 0.5625$ would round to the nearest even-last-digit number.
  • $0.5$ ends in 0 (even), $0.625$ ends in 1 (odd) → rounds to $fl(0.5625) = 0.5$
• Relative error $= |0.5 - 0.5625| / 0.5625 = 0.0625 / 0.5625 \approx 0.111$
• $\xi_M = \frac{1}{2} \times 2^{1-3} = \frac{1}{8} = 0.125 \ge 0.111$ ✓

---

Caution

Key Takeaway: Machine epsilon $\xi_M$ bounds the relative error of any single rounding. For IEEE 754 double precision ($\beta=2$, $m=52$, Normalized Form):
$\xi_M = \frac{1}{2} \times 2^{-52} \approx 1.11 \times 10^{-16}$
This is why doubles give you roughly 15–16 significant decimal digits.

---