next up previous contents
Next: Sticky Rounding Up: Rounding Previous: Rounding Away from Zero   Contents


Unbiased Rounding

Next, we examine the mode that the IEEE standard designates as “round to nearest”, which may round in either direction, selecting the representable number that is closest to its argument. This mode is also sometimes called “round to nearest even” because of the manner in which it resolves the ambiguous case of a midpoint, i.e, a number that is equidistant from two successive representable numbers.

Definition 5.3.1   (near) Given $ x \in \mathbb{Q}$ and $ n \in \mathbb{N}$ , let $ z = \lfloor 2^{n-1}sig(x)\rfloor$ , and $ f = 2^{n-1}sig(x) - z$ . Then

$\displaystyle near(x,n) = \left\{\begin{array}{ll} trunc(x,n) & \mbox{if $f < 1... ...even}\\ away(x,n) & \mbox{if $f = 1/2$ and $z$ is odd}. \end{array} \right. $

Example: Let $ x = \verb!b!101.101$ and $ n = 5$ . Then

$\displaystyle z = \lfloor 2^{n-1}sig(x) \rfloor = \lfloor \verb!b!10110.1 \rfloor = \verb!b!10110$

and

$\displaystyle f = 2^{n-1}sig(x) - z = \verb!b!10110.1 - \verb!b!10110 = \verb!b!0.1 = 1/2,$

indicating a “tie”, i.e., that $ x$ is equidistant from two successive 5-exact numbers. Since $ z$ is even, the tie is broken in favor of the lesser of the two:

$\displaystyle near(x,n) = trunc(x,n) = \verb!b!101.1.$

Like all rounding modes, the value of near is always that of either trunc or away.

Lemma 5.3.1   (near-choice) For all $ x \in \mathbb{Q}$ and $ n \in \mathbb{N}$ , either

$\displaystyle near(x,n) = trunc(x,n)$

or

$\displaystyle near(x,n) = away(x,n).$

We list several properties of near that may be derived from Lemma 5.3.1 and the corresponding properties of trunc and away.

Lemma 5.3.2   (sgn-near) Let $ x \in \mathbb{Q}$ and $ n \in \mathbb{N}$ . If $ n>0$ , then

$\displaystyle sgn(near(x,n)) = sgn(x).$

Lemma 5.3.3   (near-exactp-a) For all $ x \in \mathbb{Q}$ and $ n \in \mathbb{N}$ , $ near(x,n)$ is $ n$ -exact.

Lemma 5.3.4   (near-exactp-b) Let $ x \in \mathbb{Q}$ and $ n \in \mathbb{N}$ . If $ n>0$ and x is $ n$ -exact, then

$\displaystyle near(x,n) = x.$

Lemma 5.3.5   (near-exactp-c,near-exactp-d) Let $ x \in \mathbb{Q}$ , $ a \in \mathbb{Q}$ , and $ n \in \mathbb{N}$ , $ n>0$ . Suppose $ a$ is $ n$ -exact.

(a) If $ a \geq x$ , then $ a \geq near(x,n)$ .
(b) If $ a \leq x$ , then $ a \leq near(x,n)$ .

Lemma 5.3.6   (expo-near) Let $ x \in \mathbb{Q}$ , $ n \in \mathbb{N}$ , and $ n>0$ . If $ \vert near(x,n)\vert \neq 2^{expo(x)+1}$ , then

$\displaystyle expo(near(x,n)) = expo(x).$

  (near<=away, near>=trunc) Let $ x \in \mathbb{Q}$ and $ n \in \mathbb{N}$ . If $ x \geq 0$ , then

$\displaystyle trunc(x,n) \leq near(x,n) \leq away(x,n).$

PROOF: This follows from Lemmas 5.1.5 and 5.2.5, which together ensure that $ trunc(x,n) \leq away(x,n)$ . 

  (near-shift) For all $ x \in \mathbb{Q}$ , $ n \in \mathbb{N}$ , and $ k \in \mathbb{Z}$ ,

$\displaystyle near(2^kx,n) = 2^k near(x,n).$

PROOF: It is clear from Definition 5.3.1 that the choice between $ trunc(x,n)$ and $ away(x,n)$ depends only on $ sig(x)$ . Thus, for example, if $ near(x,n) = trunc(x,n)$ , then since $ sig(2^kx) = sig(x)$ , $ near(2^kx,n) = trunc(2^kx,n)$ as well, and by Lemma 5.1.4,

$\displaystyle near(2^kx,n) = trunc(2^kx,n) = 2^ktrunc(x,n) = 2^k near(x,n).$

  (near-minus) For all $ x \in \mathbb{Q}$ and $ n \in \mathbb{N}$ ,

$\displaystyle near(-x,n) = -near(x,n).$

PROOF: This may be derived from Lemmas 5.1.3 and 5.2.3 by following the same reasoning as used in the proof of Lemma 5.3.8. 


In the computation of $ near(x,n)$ , the choice between $ trunc(x,n)$ and $ away(x,n)$ is governed by their relative distances from $ x$ .

  (near1-a, near1-b) Let $ x \in \mathbb{Q}$ and $ n \in \mathbb{N}$ .

(a) If $ \vert x - trunc(x,n)\vert < \vert x - away(x,n)\vert$ , then $ near(x,n) = trunc(x,n)$ .

(b) If $ \vert x - trunc(x,n)\vert > \vert x - away(x,n)\vert$ , then $ near(x,n) = away(x,n)$ .

PROOF: We may assume that $ 2^{n-1}sig(x) \notin \mathbb{Z}$ , for otherwise

$\displaystyle trunc(x,n) = away(x,n) = near(x,n) = x.$

Let $ f = 2^{n-1}sig(x)-\lfloor 2^{n-1}sig(x)\rfloor$ . Then
$\displaystyle \vert x - trunc(x,n)\vert$ $\displaystyle =$ $\displaystyle \vert x\vert - \vert trunc(x,n)\vert$  
  $\displaystyle =$ $\displaystyle 2^{expo(x)+1-n}(2^{n-1}sig(x)-\lfloor 2^{n-1}sig(x)\rfloor)$  
  $\displaystyle =$ $\displaystyle 2^{expo(x)+1-n}f$  

and
$\displaystyle \vert x - away(x,n)\vert$ $\displaystyle =$ $\displaystyle \vert away(x,n)\vert - \vert x\vert$  
  $\displaystyle =$ $\displaystyle 2^{expo(x)+1-n}(\lceil 2^{n-1}sig(x) \rceil - 2^{n-1}sig(x))$  
  $\displaystyle =$ $\displaystyle 2^{expo(x)+1-n}(1-f).$  

Thus, (a) and (b) correspond to $ f < 1/2$ and $ f > 1/2$ , respectively. 


It follows that no $ n$ -exact number can be closer to $ x$ than is $ near(x,n)$ .

  (near2) Let $ x \in \mathbb{Q}$ , $ y \in \mathbb{Q}$ , and $ n \in \mathbb{N}$ . If $ n>0$ and y is n-exact, then

$\displaystyle \vert x-y\vert \geq \vert x-near(x,n)\vert.$

PROOF: Assume $ \vert x-y\vert < \vert x-near(x,n)\vert$ . We shall only consider the case $ x>0$ , as the case $ x<0$ is handled similarly.

First suppose $ near(x,n) = trunc(x,n)$ . Since $ near(x,n) \leq x$ , we must have $ y > near(x,n)$ and hence $ y > x$ by Lemma 5.1.12. But since $ away(x,n) - x \geq x-near(x,n)$ by Lemma 5.3.10, we also have $ y < away(x,n)$ , and hence $ y < x$ by Lemma 5.2.14.

In the remaining case, $ near(x,n) = away(x,n) > x$ . Now $ y < near(x,n)$ and by Lemma 5.2.14, $ y < x$ . But in this case, Lemma 5.3.10 implies $ y > trunc(x,n)$ , and hence $ y > x$ by Lemma 5.1.12. 


Consequently, the maximum near rounding error is half the distance between successive representable numbers.

  (near-est) If $ x \in \mathbb{Q}$ , $ n \in \mathbb{N}$ , and $ n>0$ , then

$\displaystyle \vert x-near(x,n)\vert \leq 2^{expo(x)-n}.$

PROOF: By Lemma 5.3.9, we may assume $ x>0$ . Let

$\displaystyle a = trunc(x,n)+2^{expo(x)+1-n} =$   fp$\displaystyle ^+(trunc(x,n),n).$

If the statement fails, then since $ trunc(x,n)$ and $ away(x,n)$ are both $ n$ -exact, Lemma 5.3.11 implies

$\displaystyle trunc(x,n) < x-2^{expo(x)-n} < x+2^{expo(x)-n} < away(x,n),$

and hence $ a < away(x,n)$ . Then by Lemmas 4.2.15 and 5.2.14, we have $ a<x$ , contradicting Lemma 5.1.7. 


Another consequence of Lemma 5.3.11 is the monotonicity of near rounding.

  (near-monotone) Let $ x \in \mathbb{Q}$ , $ y \in \mathbb{Q}$ , and $ n \in \mathbb{N}$ . If $ x \leq y$ and $ n>0$ , then

$\displaystyle near(x,n) \leq near(y,n).$

PROOF: Suppose $ x < y$ and $ near(x,n) > near(y,n)$ . Then Lemma 5.3.11 implies $ x>near(y,n)$ , otherwise $ x \leq near(y,n) < near(x,n)$ and $ \vert x-near(y,n)\vert < \vert x-near(x,n)\vert$ . Similarly, $ y < near(x,n)$ , and thus $ near(y,n) < x \leq y < near(x,n)$ . Applying Lemma 5.3.11 again, we have $ x-near(y,n) \geq near(x,n) - x$ , and hence $ 2x \geq near(x,n) + near(y,n)$ . Similarly, $ near(x,n)-y \geq y-near(y,n)$ , and hence $ near(x,n)+near(y,n) \geq 2y$ . Consequently, $ 2x \geq 2y$ , contradicting $ x < y$ .

A midpoint with respect to a precision $ n$ may be characterized as a number that is $ (n+1)$ -exact but not $ n$ -exact. By virtue of the following result, the term rounding boundary is sometimes used as well.

  (near-near-lemma) Let $ x \in \mathbb{Q}$ , $ y \in \mathbb{Q}$ , and $ n \in \mathbb{N}$ . If $ 0<x<y$ and $ near(x,n) \neq near(y,n)$ , then for some $ a \in \mathbb{Q}$ , $ x \leq a \leq y$ and a is $ (n+1)$ -exact but not $ n$ -exact.

PROOF: By Lemma 5.3.13, $ near(x,n) < near(y,n)$ . Let $ e = expo(near(x,n))$ ,

$\displaystyle a =$   fp$\displaystyle ^+(near(x,n),n+1) = near(x,n) = near(x,n) + 2^{e-n}$

and

$\displaystyle b =$   fp$\displaystyle ^+(near(x,n),n) = near(x,n) + 2^{e+1-n} = a+2^{e-n}.$

Since $ near(x,n)$ and $ near(y,n)$ are both $ n$ -exact by Lemma 5.3.3, Lemma 4.2.14 implies that $ a$ is $ (n+1)$ -exact and $ b$ is $ n$ -exact and consequently, by Lemma 4.2.15, $ a$ is not $ n$ -exact and $ near(y,n) \geq b$ . Thus,

$\displaystyle near(x,n) < a < b < near(y,n).$

Moreover, $ x \leq a \leq y$ , for if $ x > a$ , then $ \vert x-b\vert < \vert x-near(x,n\vert$ , contradicting Lemma 5.3.11 and similarly if $ y < a$ , then $ \vert y-near(x,n)\vert < \vert y-near(y,n\vert$ . 

  (near-near) Let $ x \in \mathbb{Q}$ , $ y \in \mathbb{Q}$ , $ a \in \mathbb{Q}$ , $ n \in \mathbb{N}$ , and $ k \in \mathbb{N}$ with $ n \geq k > 0$ . If $ a$ is $ (n+1)$ -exact, $ 0<a<x$ , and $ 0 < y <a+2^{expo(a)-n}$ , then $ near(x,k) \geq near(y,k)$ .

PROOF: By Lemma 5.3.13, we may assume $ x < y$ , so that $ a<x<y<a+2^{expo(a)-n}$ . By Lemmas 4.2.14 and 4.2.15, $ a$ and $ a+2^{expo(a)-n}$ are successive $ (n+1)$ -exact numbers, and hence $ near(x,k) = near(y,k)$ by Lemma 5.3.14. 


We also have the following partial converse of Lemma 5.3.14.

  (near-boundary) Let $ x \in \mathbb{Q}$ , $ y \in \mathbb{Q}$ , $ a \in \mathbb{Q}$ , and $ n \in \mathbb{N}$ . If $ n>0$ , $ 0<x <a < y$ and $ a$ is $ (n+1)$ -exact but not $ n$ -exact, then

$\displaystyle near(x,n) < near(y,n).$

PROOF: Let $ e = expo(a)$ . Since $ a$ is not $ n$ -exact, $ a \neq 2^e$ . Let

$\displaystyle b =$   fp$\displaystyle ^-(a,n+1) = a - 2^{e-n}/$

By Lemma 4.2.19,

fp$\displaystyle ^+(b,n+1) = b + 2^{expo(b)-n} = a = b + 2^{e-n},$

and it follows that $ expo(b) = e$ .

By hypothesis, $ 2^{n-e}a \in \mathbb{Z}$ but $ 2^{n-1-e}a \in \mathbb{Z}$ , and therefore, $ 2^{n-e}a$ is odd, i.e., $ 2^{n-e}a = 2k+1$ , where $ k \in \mathbb{Z}$ . Now since

$\displaystyle 2^{n-1-e}b = 2^{n-1-e}(a-2^{n-e}) = \frac{1}{2}(2^{n-e}a-1) = k \in \mathbb{Z},$

$ b$ is $ n$ -exact. Let

$\displaystyle c =$   fp$\displaystyle ^+(b,n) = b + 2^{n+1-e} = a + 2^{n-e}.$

By Lemma 4.2.14, $ c$ is $ n$ -exact as well.

If $ near(x,n) > b$ , then by Lemma 4.2.15, $ near(x,n) \geq c$ , which implies $ \vert b-x\vert < \vert near(x,n) - x\vert$ , contradicting Lemma 5.3.11. Similarly, if $ near(y,n) < c$ , then $ near(y,n) \leq b$ and $ \vert c-y\vert < \vert near(y,n) - y\vert$ . Thus,

$\displaystyle near(x,n) \leq b < a < c \leq near(y,n).$

The meaning of “round to nearest even” is that in the case of a midpoint $ x$ , $ near(x,n)$ is defined to be the “rounder” of the two nearest $ n$ -exact numbers, i.e., the one that is $ (n-1)$ -exact.

  (near-exact) Let $ n \in \mathbb{N}$ , $ n>1$ , and $ x \in \mathbb{Q}$ . If $ x$ is $ (n+1)$ -exact but not $ n$ -exact, then $ near(x,n)$ is $ (n-1)$ -exact.

PROOF: Again we may assume $ x>0$ . Let $ z = \lfloor 2^{n-1}sig(x)\rfloor$ and $ f = 2^{n-1}sig(x) - z$ . Since $ 2^{n-1}sig(x) \notin \mathbb{Z}$ , $ 0<f<1$ . But $ 2^{n}sig(x) = 2z+2f \in \mathbb{Z}$ , hence $ 2f \in \mathbb{Z}$ and $ f=\frac{1}{2}$ .

If $ z$ is even, then

$\displaystyle near(x,n) = trunc(x,n) = z2^{expo(x)+1-n}$

and by Lemma 5.1.6,

$\displaystyle 2^{n-2-expo(near(x,n))}near(x,n) = 2^{n-2-expo(x)}z2^{expo(x)+1-n} = z/2 \in \mathbb{Z}.$

If $ z$ is odd, then

$\displaystyle near(x,n) = away(x,n) = (z+1)2^{expo(x)+1-n}.$

We may assume $ away(x,n) \neq 2^{expo(x)+1}$ , and hence by Corollary 5.2.10,
$\displaystyle 2^{n-2-expo(near(x,n))}near(x,n)$ $\displaystyle =$ $\displaystyle 2^{n-2-expo(x)}(z+1)2^{expo(x)+1-n}$  
  $\displaystyle =$ $\displaystyle (z+1)/2$  
  $\displaystyle \in$ $\displaystyle \mathbb{Z}.$  

One consequence of this result is that a midpoint is sometimes rounded up and sometimes down, and therefore, over the course of a long series of computations and approximations, rounding error is less likely to accumulate to a significant degree in one particular direction than it would be if the the choice were made more consistently. The cost of this feature is a more complicated definition, requiring a more expensive implementation.

When the goal of a computation is provable accuracy rather than IEEE-compliance, a simpler version of “round to nearest” may be appropriate. The critical feature of this mode then becomes the relative error bound guaranteed by Lemma 5.3.12, since this is likely to be the basis for any formal error analysis. The following definition presents an alternative to near that respects the same error bound (see Lemma 5.3.29) but admits a simpler implementation and is therefore commonly used for internal floating-point calculations.

Definition 5.3.2   (near+) Given $ x \in \mathbb{Q}$ and $ n \in \mathbb{N}$ , let $ z = \lfloor 2^{n-1}sig(x)\rfloor$ , and $ f = 2^{n-1}sig(x) - z$ . Then

$\displaystyle near^{+}(x,n) = \left\{\begin{array}{ll} trunc(x,n) & \mbox{if $f < 1/2$}\\ away(x,n) & \mbox{if $f \geq 1/2$.} \end{array} \right. $

Example: Let $ x = \verb!b!101.101$ and $ n = 5$ . Since

$\displaystyle f = 2^{n-1}sig(x) - \lfloor 2^{n-1}sig(x) \rfloor = \verb!b!10110.1 - \verb!b!10110 = \verb!b!0.1 = 1/2,$

$\displaystyle near^+(x,n) = away(x,n) = \verb!b!101.11$

Naturally, many of the properties of near are held by $ near^+$ as well. We list some of them here, omitting the proofs, which are essentially the same as those given above for near.

Lemma 5.3.18   (near+-choice) For all $ x \in \mathbb{Q}$ and $ n \in \mathbb{N}$ , either

$\displaystyle near^{+}(x,n) = trunc(x,n)$

or

$\displaystyle near^{+}(x,n) = away(x,n).$

Lemma 5.3.19   (near+<=away, near+>=trunc) Let $ x \in \mathbb{Q}$ and $ n \in \mathbb{N}$ . If $ x \geq 0$ , then

$\displaystyle trunc(x,n) \leq near^{+}(x,n) \leq away(x,n).$

Lemma 5.3.20   (near+-shift) For all $ x \in \mathbb{Q}$ , $ n \in \mathbb{N}$ , and $ k \in \mathbb{Z}$ ,

$\displaystyle near^{+}(2^kx,n) = 2^k near^{+}(x,n).$

Lemma 5.3.21   (near+-minus) For all $ x \in \mathbb{Q}$ and $ n \in \mathbb{N}$ ,

$\displaystyle near^{+}(-x,n) = -near^{+}(x,n).$

Lemma 5.3.22   (sgn-near+) Let $ x \in \mathbb{Q}$ and $ n \in \mathbb{N}$ . If $ n>0$ , then

$\displaystyle sgn(near+(x,n)) = sgn(x).$

Lemma 5.3.23   (near+-exactp-a) For all $ x \in \mathbb{Q}$ and $ n \in \mathbb{N}$ , $ near^{+}(x,n)$ is $ n$ -exact.

Lemma 5.3.24   (near+-exactp-b) Let $ x \in \mathbb{Q}$ and $ n \in \mathbb{N}$ . If $ n>0$ and x is $ n$ -exact, then

$\displaystyle near^{+}(x,n) = x.$

Lemma 5.3.25   (near+-exactp-c,near+-exactp-d) Let $ x \in \mathbb{Q}$ , $ a \in \mathbb{Q}$ , and $ n \in \mathbb{N}$ , $ n>0$ . Suppose $ a$ is $ n$ -exact.

(a) If $ a \geq x$ , then $ a \geq near^{+}(x,n)$ .
(b) If $ a \leq x$ , then $ a \leq near^{+}(x,n)$ .

Lemma 5.3.26   (expo-near+) For all $ x \in \mathbb{Q}$ and $ n \in \mathbb{N}$ , if $ \vert near^+(x,n)\vert \neq 2^{expo(x)+1}$ , then

$\displaystyle expo(near^+(x,n)) = expo(x).$

Lemma 5.3.27   (near+1-a, near+1-b) Let $ x \in \mathbb{Q}$ and $ n \in \mathbb{N}$ .

(a) If $ \vert x - trunc(x,n)\vert < \vert x - away(x,n)\vert$ , then $ near^{+}(x,n) = trunc(x,n)$ .

(b) If $ \vert x - trunc(x,n)\vert > \vert x - away(x,n)\vert$ , then $ near^{+}(x,n) = away(x,n)$ .

Lemma 5.3.28   (near+2) Let $ x \in \mathbb{Q}$ , $ y \in \mathbb{Q}$ , and $ n \in \mathbb{N}$ . If $ n>0$ and y is n-exact, then

$\displaystyle \vert x-y\vert \geq \vert x-near^{+}(x,n)\vert.$

Lemma 5.3.29   (near+-est) If $ x \in \mathbb{Q}$ , $ n \in \mathbb{N}$ , and $ n>0$ , then

$\displaystyle \vert x-near^{+}(x,n)\vert \leq 2^{expo(x)-n}.$

Lemma 5.3.30   (near+-monotone) Let $ x \in \mathbb{Q}$ , $ y \in \mathbb{Q}$ , and $ n \in \mathbb{N}$ . If $ x \leq y$ and $ n>0$ , then

$\displaystyle near^{+}(x,n) \leq near^{+}(y,n).$

The difference between near and $ near^+$ is that the latter always rounds a midpoint away from 0.

  (near+-midpoint) Let $ x \in \mathbb{Q}$ and $ n \in \mathbb{N}$ . If $ x$ is $ (n+1)$ -exact but not $ n$ -exact, then

$\displaystyle near^+(x,n) = away(x,n) = x + sgn(x)2^{expo(x)-n}.$

PROOF: By Lemmas 5.3.9 and 5.2.3, we may assume $ x>0$ . Let $ z = \lfloor 2^{n-1}sig(x)\rfloor$ and $ f = 2^{n-1}sig(x) - z$ . Since $ 2^{n-1}sig(x) \notin \mathbb{Z}$ , $ 0<f<1$ . But $ 2^{n}sig(x) = 2z+2f \in \mathbb{Z}$ , hence $ 2f \in \mathbb{Z}$ and $ f=\frac{1}{2}$ . Therefore, according to Definition 5.3.2, $ near^+(x,n) = away(x,n)$ . The second inequality is a restatement of Lemma 5.2.17. 


There is one case of a midpoint for which near and $ near^+$ are guaranteed to produce the same result: if the greater of the two representable numbers that are equidistant from $ x$ is a power of 2, i.e., $ x = 2^{expo(x)+1} - 2^{expo(x)-n}$ , then both modes round to this number.

  (near-power-a, near-power-b,near+-power)
Let $ n \in \mathbb{N}$ , $ n>1$ , and $ x \in \mathbb{Q}$ , $ x>0$ . If $ x + 2^{expo(x)-n} \geq 2^{expo(x)+1}$ , then

$\displaystyle near(x,n) = near^+(x,n) = 2^{expo(x)+1} = trunc(x+2^{expo(x)-n},n).$

PROOF: Suppose $ near(x,n) \neq 2^{expo(x)+1}$ . Then Lemma 5.3.6 implies

$\displaystyle near(x,n) < 2^{expo(x)+1}$

and by Lemmas 4.2.15 and 5.3.12,
$\displaystyle 2^{expo(x)+1}$ $\displaystyle \geq$ $\displaystyle near(x,n)+2^{expo(x)+1-n}$  
  $\displaystyle \geq$ $\displaystyle x - 2^{expo(x)-n} + 2^{expo(x)+1-n}$  
  $\displaystyle =$ $\displaystyle x + 2^{expo(x)-n}$  
  $\displaystyle \geq$ $\displaystyle 2^{expo(x) + 1}.$  

It follows that $ x = 2^{expo(x)+1} - 2^{expo(x)-n}$ , which is easily seen to be $ (n+1)$ -exact but not $ n$ -exact, while $ near(x,n) = 2^{expo(x)+1} - 2^{expo(x)+1-n}$ is $ n$ -exact but not $ (n-1)$ -exact, contradicting Lemma 5.3.17.

Now suppose $ near^+(x,n) \neq 2^{expo(x)+1}$ . Using Lemmas 5.3.26 and 5.3.29, we may show in the same way as above that $ x = 2^{expo(x)+1} - 2^{expo(x)-n}$ . Once again, $ x$ is $ (n+1)$ -exact but not $ n$ -exact, and hence, by Lemma 5.3.31,

$\displaystyle near^+(x,n) = x + 2^{expo(x)-n} = 2^{expo(x)+1},$

a contradiction.

Finally, suppose $ 2^{expo(x)+1} \neq trunc(x+2^{expo(x)-n},n)$ . Since $ 2^{expo(x)+1}$ is $ n$ -exact, $ 2^{expo(x)+1} < trunc(x+2^{expo(x)-n},n)$ by Lemma 5.1.12. But then by Lemma 4.2.15,

$\displaystyle trunc(x+2^{expo(x)-n},n)$ $\displaystyle \geq$ $\displaystyle 2^{expo(x)+1} + 2^{expo(x)+2-n} > x+ 2^{expo(x)-n},$  

contradicting Lemma 5.1.5. 


The additive property shared by trunc and away that is described in Lemmas 5.1.16 and 5.2.19, respectively, does not hold for near in precisely the same form. For example, let $ x = 2 = \verb!b!10$ , $ y = 5 = \verb!b!101$ , and $ k = 2$ . Then

$\displaystyle k + expo(x) - expo(y) = 2 + 1 - 2 = 1$

and

$\displaystyle k + expo(x+y) - expo(y) = 2 + 2 - 2 = 2.$

Although $ x$ is clearly $ (k+expo(x)-expo(y))$ -exact,

$\displaystyle x + near(y,k) = \verb!b!10 + near(\verb!b!101,2) = \verb!b!10 + \verb!b!100 = \verb!b!110,$

while

$\displaystyle near(x+y,k + expo(x+y) - expo(y)) = near(\verb!b!111,2) = \verb!b!1000.$

However, this property is shared by $ near^+$ , and a slightly weaker version holds for near.

  (near-plus,near+-plus) Let $ x \in \mathbb{Q}$ , $ y \in \mathbb{Q}$ , and $ k \in \mathbb{Z}$ with $ x \geq 0$ and $ y \geq 0$ . Let

$\displaystyle k' = k+expo(x)-expo(y)$

and

$\displaystyle k” = k+expo(x+y)-expo(y).$

(a) If $ x$ is $ (k'-1)$ -exact, then

$\displaystyle x+near(y,k) = near(x+y,k”).$

(b) If $ x$ is $ k'$ -exact, then

$\displaystyle x+near^+(y,k) = near^+(x+y,k”).$

PROOF:

(a) Applying Lemma 5.1.16 and 5.2.19, we need only show that either

$\displaystyle near(y,k) = trunc(y,k)$    and $\displaystyle near(x+y,k”) = trunc(x+y,k”)$

or

$\displaystyle near(y,k) = away(y,k)$    and $\displaystyle near(x+y,k”) = away(x+y,k”).$

Let $ z_1 = \lfloor 2^{k-1}sig(y)\rfloor$ , $ f_1 = 2^{k-1}sig(y) - z_1$ , $ z_2 = \lfloor 2^{k”-1}sig(x+y)\rfloor$ , and $ f_2 = 2^{k”-1}sig(x+y) - z_2$ . According to Definition 5.3.1, it will suffice to show that

$\displaystyle 2^{k”-1}sig(x+y) - 2^{k-1}sig(y) = 2\ell,$

for some $ \ell \in \mathbb{Z}$ , for then Lemma 1.1.6 will imply that $ z_2 = z_1 + 2\ell$ and $ f_2 = f_1$ . But
$\displaystyle 2^{k”-1}sig(x+y) - 2^{k-1}sig(y)$ $\displaystyle =$ $\displaystyle 2^{k”-expo(x+y) - 1}(x+y) - 2^{k-expo(y)-1}y$  
  $\displaystyle =$ $\displaystyle 2^{k-expo(y) - 1}(x+y) - 2^{k-expo(y)-1}y$  
  $\displaystyle =$ $\displaystyle 2^{k-expo(y) - 1}x$  
  $\displaystyle =$ $\displaystyle 2^{k'-expo(x) - 1}x$  
  $\displaystyle =$ $\displaystyle 2\ell,$  

where

$\displaystyle \ell = 2^{(k'-1)-expo(x)-1} \in \mathbb{Z}$

by Lemma 4.2.1.

(b) Here we must show that either

$\displaystyle near^+(y,k) = trunc(y,k)$    and $\displaystyle near^+(x+y,k”) = trunc(x+y,k”)$

or

$\displaystyle near^+(y,k) = away(y,k)$    and $\displaystyle near^+(x+y,k”) = away(x+y,k”).$

According to Definition 5.3.2, this is true whenever $ f_1 = f_2$ . Thus, we need only show that

$\displaystyle 2^{k”-1}sig(x+y) - 2^{k-1}sig(y) = 2^{k'-expo(x) - 1}x \in \mathbb{Z},$

which is equivalent to the hypothesis that $ x$ is $ k'$ -exact. 


The rounding constant (see the discussion preceding Lemma 5.2.22) for both of the modes $ near$ and $ near^+$ is a simple power of 2, equal to half the value of the leasr signifivant bit of the rounded result. That is, if the rounding precision is $ n$ and the unrounded result is

$\displaystyle x = \verb!b!1.\beta_1\beta_2\cdots \times 2^e,$

then $ {\cal C} = 2^{e-n}$ , as illustrated below.


\begin{picture}(120,55)(-25,22)\setlength{\unitlength}{2mm} \par \put(10,10){... ...\put(28.7,8){$\times \:\:\:2^e$} \par \put(10,6.8){\line(1,0){23}} \end{picture}

The following lemma exposes the extra expense of implementing $ near$ as compared to $ near^+$ . While the correctly rounded result is given by $ trunc(x+{\cal C},n)$ in most cases, special attention is required for the computation of $ near$ in the case where it differs from $ near^+$ , i.e., when $ x$ is $ (n+1)$ -exact and $ \beta_n = 1$ . In this case, the least significant bit must be forced to 0. This is accomplished by truncating $ x+{\cal C}$ to $ n-1$ bits rather than $ n$ .

  (near-trunc,near+trunc) If $ n \in \mathbb{N}$ , $ n>1$ , $ x \in \mathbb{Q}$ , and $ x>0$ , then

$\displaystyle near(x,n) = \left\{\begin{array}{ll} trunc(x\mbox{\rm +}2^{expo(x... ...\\ trunc(x\mbox{\rm +}2^{expo(x)-n},n) & \mbox{otherwise} \end{array} \right. $

and

$\displaystyle near^{+}(x,n) = trunc(x+2^{expo(x)-n},n).$

PROOF: If $ x + 2^{expo(x)-n} \geq 2^{expo(x)+1}$ , then by Lemma 5.3.32,

$\displaystyle near(x,n) = near^+(x,n) = 2^{expo(x)+1} = trunc(x+2^{expo(x)-n},n).$

But then, by Lemmas 5.1.15, 4.2.6, and 5.1.11,
$\displaystyle trunc(x+2^{expo(x)-n},n-1)$ $\displaystyle =$ $\displaystyle trunc(trunc(x+2^{expo(x)-n},n), n-1)$  
  $\displaystyle =$ $\displaystyle trunc(2^{expo(x)+1},n-1)$  
  $\displaystyle =$ $\displaystyle 2^{expo(x)+1}$  
  $\displaystyle =$ $\displaystyle trunc(x+2^{expo(x)-n},n).$  

Thus, we may assume $ x+2^{expo(x)-n} < 2^{expo(x)+1}$ , and it follows from Lemmas 5.3.6, 5.3.12, 5.3.26, and 5.3.29 that

$\displaystyle expo(near(x,n)) = expo(near^+(x,n)) = expo(x+2^{expo(x)-n}) = expo(x).$

Case 1: $ x$ is $ n$ -exact

By Lemma 5.1.12, $ trunc(x+2^{expo(x)-n},n) \geq x$ . But since

$\displaystyle trunc(x+2^{expo(x)-n},n) \leq x+2^{expo(x)-n} < x+2^{expo(x)+1-n},$

Lemma 4.2.15 yields $ trunc(x+2^{expo(x)-n},n) \leq x$ , and hence

$\displaystyle trunc(x+2^{expo(x)-n},n) = x = near(x,n) = near^+(x,n).$

Case 2: $ x$ is not $ (n+1)$ -exact

We have $ near(x,n) > x-2^{expo(x)-n}$ , for otherwise Lemma 5.3.12 <would imply

$\displaystyle near(x,n) = x-2^{expo(x)-n},$

and since $ near(x,n)$ is $ (n+1)$ -exact, so would be

$\displaystyle near(x,n)+2^{expo(near(x,n))-n} = x-2^{expo(x)-n}+2^{expo(near(x,n))-n}=x.$

Since $ near(x,n) \leq x+2^{expo(x)-n}$ , $ near(x,n) \leq trunc(x+2^{expo(x)-n},n)$ by Lemma 5.1.12. But since

$\displaystyle trunc(x+2^{expo(x)-n},n) \leq x+2^{expo(x)-n} < near(x,n)+2^{expo(x)+1-n},$

$ trunc(x+2^{expo(x)-n},n) \leq near(x,n)$ .

The same argument applies to $ near^+(x,n)$ , but with Lemma 5.3.29 invoked in place of Lemma 5.3.12.



Case 3: $ x$ is $ (n+1)$ -exact but not $ n$ -exact

The identity for $ near^+(x,n)$ is given by Lemma 5.3.31. To prove the claim for $ near^+$ , we first consider the case $ near(x,n) > x$ . Since $ near(x,n)$ is $ (n+1)$ -exact, $ near(x,n) \geq x+2^{expo(x)-n}$ , hence $ near(x,n) = x+2^{expo(x)-n}$ , and by Lemma 5.3.17,

$\displaystyle trunc(x+2^{expo(x)-n},n-1) = trunc(near(x,n),n-1) = near(x,n).$

Now suppose $ near(x,n) < x$ . Then $ near(x,n) < x+2^{expo(x)-n}$ implies $ near(x,n) \leq trunc(x+2^{expo(x)-n},n-1)$ . But since

$\displaystyle trunc(x+2^{expo(x)-n},n-1)$ $\displaystyle \leq$ $\displaystyle x + 2^{expo(x)-n}$  
  $\displaystyle =$ $\displaystyle x - 2^{expo(x)-n} + 2^{expo(x)+1-n}$  
  $\displaystyle <$ $\displaystyle near(x,n)+2^{expo(x)+2-n},$  

we have $ trunc(x+2^{expo(x)-n},n-1) \leq near(x,n)$ . 


As a consequence of the preceding lemma, $ near^+(x,m)$ may be depends only on the most significant $ m+1$ bits of $ x$ .

  (near+trunc-cor) Let $ x \in \mathbb{Q}$ , $ m \in \mathbb{N}$ , and $ n \in \mathbb{N}$ . If $ n>m>0$ , then

$\displaystyle near^+(trunc(x,n),m) = near^+(x,m).$

PROOF: By Lemmas 5.3.21 and 5.1.3, we may assume that $ x>0$ . Furthermore, it will suffice to consider the case $ n=m+1$ , because then for $ n>m+1$ ,

$\displaystyle near^+(trunc(x,n),m)$ $\displaystyle =$ $\displaystyle near^+(trunc(trunc(x,n),m+1),m)$  
  $\displaystyle =$ $\displaystyle near^+(trunc(x,m+1),m)$  
  $\displaystyle =$ $\displaystyle near^+(x,m).$  

Thus, according to Lemmas 5.3.34 and 5.1.6, our goal is to prove

$\displaystyle trunc(trunc(x,m+1)+2^{expo(x)-n},m) = trunc(x+2^{expo(x)-n},m),$

but after applying Lemma 5.1.5, we need only show

$\displaystyle trunc(trunc(x,m+1)+2^{expo(x)-n},m) \geq trunc(x+2^{expo(x)-n},m).$

Let

$\displaystyle y = trunc(x,m+1)+2^{expo(x)-n} =$   fp$\displaystyle ^+(trunc(x,m+1),m+1).$

By Lemmas 5.1.9 and 4.2.14, $ y$ is $ (m+1)$ -exact. Now since $ trunc(x+2^{expo(x)-n},m)$ is also $ (m+1)$ -exact and Lemmas 5.1.5 and 5.1.7 imply
$\displaystyle trunc(x+2^{expo(x)-n},m)$ $\displaystyle \leq$ $\displaystyle x + 2^{expo(x)-n}$  
  $\displaystyle <$ $\displaystyle trunc(x,m+1) + 2^{expo(x)-n} + 2^{expo(x)-n}$  
  $\displaystyle =$ $\displaystyle y + 2^{expo(x)-n}$  
  $\displaystyle =$ fp$\displaystyle ^+(y,m+1),$  

Lemma 4.2.15 yields $ trunc(x+2^{expo(x)-n},m) \leq y$ . Finally, by Lemma 5.1.12,

$\displaystyle trunc(x+2^{expo(x)-n},m) \leq trunc(y,m).$

next up previous contents
Next: Sticky Rounding Up: Rounding Previous: Rounding Away from Zero   Contents
David Russinoff 2007-01-02