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 and , let , and . Then

Example: Let and . Then

and

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

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

Lemma 5.3.1   (near-choice) For all and , either

or

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 and . If , then

Lemma 5.3.3   (near-exactp-a) For all and , is -exact.

Lemma 5.3.4   (near-exactp-b) Let and . If and x is -exact, then

Lemma 5.3.5   (near-exactp-c,near-exactp-d) Let , , and , . Suppose is -exact.

 (a) If , then . (b) If , then .

Lemma 5.3.6   (expo-near) Let , , and . If , then

(near<=away, near>=trunc) Let and . If , then

PROOF: This follows from Lemmas 5.1.5 and 5.2.5, which together ensure that

(near-shift) For all , , and ,

PROOF: It is clear from Definition 5.3.1 that the choice between and depends only on . Thus, for example, if , then since , as well, and by Lemma 5.1.4,

(near-minus) For all and ,

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 , the choice between and is governed by their relative distances from .

(near1-a, near1-b) Let and .

(a) If , then .

(b) If , then .

PROOF: We may assume that , for otherwise

Let . Then

and

Thus, (a) and (b) correspond to and , respectively.

It follows that no -exact number can be closer to than is .

(near2) Let , , and . If and y is n-exact, then

PROOF: Assume . We shall only consider the case , as the case is handled similarly.

First suppose . Since , we must have and hence by Lemma 5.1.12. But since by Lemma 5.3.10, we also have , and hence by Lemma 5.2.14.

In the remaining case, . Now and by Lemma 5.2.14, . But in this case, Lemma 5.3.10 implies , and hence by Lemma 5.1.12

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

(near-est) If , , and , then

PROOF: By Lemma 5.3.9, we may assume . Let

fp

If the statement fails, then since and are both -exact, Lemma 5.3.11 implies

and hence . Then by Lemmas 4.2.15 and 5.2.14, we have , contradicting Lemma 5.1.7

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

(near-monotone) Let , , and . If and , then

PROOF: Suppose and . Then Lemma 5.3.11 implies , otherwise and . Similarly, , and thus . Applying Lemma 5.3.11 again, we have , and hence . Similarly, , and hence . Consequently, , contradicting .

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

(near-near-lemma) Let , , and . If and , then for some , and a is -exact but not -exact.

PROOF: By Lemma 5.3.13, . Let ,

fp

and

fp

Since and are both -exact by Lemma 5.3.3, Lemma 4.2.14 implies that is -exact and is -exact and consequently, by Lemma 4.2.15, is not -exact and . Thus,

Moreover, , for if , then , contradicting Lemma 5.3.11 and similarly if , then

(near-near) Let , , , , and with . If is -exact, , and , then .

PROOF: By Lemma 5.3.13, we may assume , so that . By Lemmas 4.2.14 and 4.2.15, and are successive -exact numbers, and hence by Lemma 5.3.14

We also have the following partial converse of Lemma 5.3.14.

(near-boundary) Let , , , and . If , and is -exact but not -exact, then

PROOF: Let . Since is not -exact, . Let

fp

By Lemma 4.2.19,

fp

and it follows that .

By hypothesis, but , and therefore, is odd, i.e., , where . Now since

is -exact. Let

fp

By Lemma 4.2.14, is -exact as well.

If , then by Lemma 4.2.15, , which implies , contradicting Lemma 5.3.11. Similarly, if , then and . Thus,

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

(near-exact) Let , , and . If is -exact but not -exact, then is -exact.

PROOF: Again we may assume . Let and . Since , . But , hence and .

If is even, then

and by Lemma 5.1.6,

If is odd, then

We may assume , and hence by Corollary 5.2.10,

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 and , let , and . Then

Example: Let and . Since

Naturally, many of the properties of near are held by 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 and , either

or

Lemma 5.3.19   (near+<=away, near+>=trunc) Let and . If , then

Lemma 5.3.20   (near+-shift) For all , , and ,

Lemma 5.3.21   (near+-minus) For all and ,

Lemma 5.3.22   (sgn-near+) Let and . If , then

Lemma 5.3.23   (near+-exactp-a) For all and , is -exact.

Lemma 5.3.24   (near+-exactp-b) Let and . If and x is -exact, then

Lemma 5.3.25   (near+-exactp-c,near+-exactp-d) Let , , and , . Suppose is -exact.

 (a) If , then . (b) If , then .

Lemma 5.3.26   (expo-near+) For all and , if , then

Lemma 5.3.27   (near+1-a, near+1-b) Let and .

(a) If , then .

(b) If , then .

Lemma 5.3.28   (near+2) Let , , and . If and y is n-exact, then

Lemma 5.3.29   (near+-est) If , , and , then

Lemma 5.3.30   (near+-monotone) Let , , and . If and , then

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

(near+-midpoint) Let and . If is -exact but not -exact, then

PROOF: By Lemmas 5.3.9 and 5.2.3, we may assume . Let and . Since , . But , hence and . Therefore, according to Definition 5.3.2, . The second inequality is a restatement of Lemma 5.2.17

There is one case of a midpoint for which near and are guaranteed to produce the same result: if the greater of the two representable numbers that are equidistant from is a power of 2, i.e., , then both modes round to this number.

(near-power-a, near-power-b,near+-power)
Let , , and , . If , then

PROOF: Suppose . Then Lemma 5.3.6 implies

and by Lemmas 4.2.15 and 5.3.12,

It follows that , which is easily seen to be -exact but not -exact, while is -exact but not -exact, contradicting Lemma 5.3.17.

Now suppose . Using Lemmas 5.3.26 and 5.3.29, we may show in the same way as above that . Once again, is -exact but not -exact, and hence, by Lemma 5.3.31,

Finally, suppose . Since is -exact, by Lemma 5.1.12. But then by Lemma 4.2.15,

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 , , and . Then

and

Although is clearly -exact,

while

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

(near-plus,near+-plus) Let , , and with and . Let

and

(a) If is -exact, then

(b) If is -exact, then

PROOF:

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

and

or

and

Let , , , and . According to Definition 5.3.1, it will suffice to show that

for some , for then Lemma 1.1.6 will imply that and . But

where

by Lemma 4.2.1.

(b) Here we must show that either

and

or

and

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

which is equivalent to the hypothesis that is -exact.

The rounding constant (see the discussion preceding Lemma 5.2.22) for both of the modes and 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 and the unrounded result is

then , as illustrated below.

The following lemma exposes the extra expense of implementing as compared to . While the correctly rounded result is given by in most cases, special attention is required for the computation of in the case where it differs from , i.e., when is -exact and . In this case, the least significant bit must be forced to 0. This is accomplished by truncating to bits rather than .

(near-trunc,near+trunc) If , , , and , then

and

PROOF: If , then by Lemma 5.3.32,

But then, by Lemmas 5.1.15, 4.2.6, and 5.1.11,

Thus, we may assume , and it follows from Lemmas 5.3.6, 5.3.12, 5.3.26, and 5.3.29 that

Case 1: is -exact

By Lemma 5.1.12, . But since

Lemma 4.2.15 yields , and hence

Case 2: is not -exact

We have , for otherwise Lemma 5.3.12 <would imply

and since is -exact, so would be

Since , by Lemma 5.1.12. But since

.

The same argument applies to , but with Lemma 5.3.29 invoked in place of Lemma 5.3.12.

Case 3: is -exact but not -exact

The identity for is given by Lemma 5.3.31. To prove the claim for , we first consider the case . Since is -exact, , hence , and by Lemma 5.3.17,

Now suppose . Then implies . But since

we have

As a consequence of the preceding lemma, may be depends only on the most significant bits of .

(near+trunc-cor) Let , , and . If , then

PROOF: By Lemmas 5.3.21 and 5.1.3, we may assume that . Furthermore, it will suffice to consider the case , because then for ,

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

but after applying Lemma 5.1.5, we need only show

Let

fp

By Lemmas 5.1.9 and 4.2.14, is -exact. Now since is also -exact and Lemmas 5.1.5 and 5.1.7 imply
 fp

Lemma 4.2.15 yields . Finally, by Lemma 5.1.12,

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