# An introduction to different rounding algorithms

*Editor's Note:* I just thought I should mention that there's an ongoing, ever-evolving, and dramatically different presentation of this topic entitled Rounding 101 on my personal website.

It is often said that it's only when you try to explain something to someone else that you come to realize that there are "holes" in your understanding of the topic in question. Such was the case when it came to presenting the concept of rounding in our recently-published book: How Computers Do Math (ISBN: 0471732788) featuring a virtual 8-bit computer-calculator called the DIY Calculator. In fact, the mind soon boggles at the variety and intricacies of the rounding algorithms that may be used for different applications.

For example, we have *round-up*, *round-down*, *round-toward-nearest*, *arithmetic rounding*, *round-half-up*, *round-half-down*, *round-half-even*, *round-half-odd*, *round-toward-zero*, *round-away-from-zero*, *round-ceiling*, *round-floor*, *truncation* (chopping), *round-alternate*, and *round-random* (stochastic rounding), to name but a few. What makes things even more exciting is that some of these terms can refer to the same thing (or not, depending on the application and to whom you are talking). Similarly, some rounding schemes work one way on sign-magnitude values (like standard decimal numbers and sign-magnitude binary numbers) and a different way on complement representations (like twos complement [signed binary] and tens complement [signed decimal]).

But, nothing daunted, we are going to rip the veils asunder and discover more about rounding than most of us ever wanted to know. We will commence by introducing a smorgasbord of basic concepts. Then, in order to provide some "meat," Tim Vanevenhoven at AccelChip was kind enough to create and run some test cases in MATLAB® from The MathWorks to illustrate the types of errors associated with different rounding schemes applied at various stages throughout a fixed-point digital filter implemented in hardware (the MATLAB source files are available for you to download and play with as described later in this article).

**Rounding in decimal**

We'll start the ball rolling by considering the various rounding schemes in the context of the decimal numbers we know and love so well. The most fundamental fact associated with rounding is that it involves transforming some quantity from a greater precision to a lesser precision; for example, rounding a reasonably precise value like $3.21 to the nearest dollar would result in $3.00, which is a less precise entity.

Given a choice, we would generally prefer to use a rounding algorithm that minimizes the effects of this loss of precision, especially in the case where multiple processing iterations – each involving rounding – can result in "creeping errors" (by this we mean that errors increase over time due to performing rounding operations on data that has previously been rounded). However, in the case of hardware implementations targeted toward tasks such as digital signal processing (DSP) algorithms, for example, we also have to be cognizant of the overheads associated with the various rounding techniques so as to make appropriate design trade-offs.

For the purposes of the following discussions, we will assume that the goal is to round to an integer value. In real-world applications we might wish to round to any particular digit (usually a fractional digit), but the principles are exactly the same.

A summary of the actions of the main rounding modes as applied to standard (sign-magnitude) decimal values is provided in *Table 1*.

**Round-toward-nearest:** This is perhaps the most intuitive of the various rounding algorithms. In this case, values such as 3.1, 3.2, 3.3, and 3.4 would round down to 3, while values of 3.6, 3.7, 3.8, and 3.9 would round up to 4. The trick, of course, is to decide what to do in the case of the half-way value 3.5. In fact, *round-toward-nearest* may be considered to be a superset of two complementary options known as *round-half-up* and *round-half-down*, each of which treats the 3.5 value in a different manner as discussed below.

**Round-half-up:** This algorithm, which may also be referred to as *arithmetic rounding*, is the one that we typically associate with the rounding we learned at grade-school. In this case, a half-way value such as 3.5 will round up to 4. One way to view this is that, at this level of precision and for this particular example, we can consider there to be ten values that commence with a 3 in the most-significant place (3.0, 3.1, 3.2, 3.3, 3.4, 3.5, 3.6, 3.7, 3.8, and 3.9). On this basis, it intuitively makes sense for five of the values to round down and for the other five to round up; that is, for the five values 3.0 through 3.4 to round down to 3, and for the remaining five values 3.5 through 3.9 to round up to 4.

The tricky point with the *round-half-up* algorithm arrives when we come to consider negative numbers. In the case of the values -3.1, -3.2, -3.3, and -3.4, these will all round to the nearest integer, which is -3; similarly, in the case of values like -3.6, -3.7, -3.8, and -3.9, these will all round to -4. The problem arises in the case of -3.5 and our definition as to what "up" means in the context of *round-half-up*. Based on the fact that a value of +3.5 rounds up to +4, most of us would intuitively expect a value of -3.5 to round to -4. In this case, we would say that our algorithm was *symmetric* for positive and negative values.

However, some applications (and mathematicians) regard "up" as referring to positive infinity. Based on this, -3.5 will actually round to -3, in which case we would class this as being an *asymmetric* implementation of the *round-half-up* algorithm. For example, the *round* method of the Java Math Library provides an asymmetric implementation of the *round-half-up* algorithm, while the *round* function in MATLAB provides a symmetric implementation. (Just to keep us on our toes, the *round* function in Visual Basic for Applications 6.0 actually implements the *round-half-even* [Banker's rounding] algorithm discussed below.)

**Round-half-down:** This acts in the opposite manner to its *round-half-up* counterpart. In this case, a half-way value such as 3.5 will round down to 3. Once again, we run into a problem when we come to consider negative numbers, depending on what we assume "down" to mean. In the case of a symmetric implementation of the algorithm, a value of -3.5 will round to -3. By comparison, in the case of an asymmetric implementation of the algorithm, in which "down" is understood to refer to negative infinity, a value of -3.5 will actually round to -4.

As a point of interest, the symmetric versions of rounding algorithms are sometimes referred to as "Gaussian implementations." This is because the theoretical frequency distribution known as a Gaussian distribution – which is named for the German mathematician and astronomer Karl Friedrich Gauss (1777-1855) – is symmetrical about its mean value.

**Round-half-even:** If half-way values are always rounded in the same direction (for example 3.5 rounds to 4 and 4.5 rounds to 5), the result can be a bias that grows as more rounding operations are performed. One solution toward minimizing this bias is to sometimes round up and sometimes round down.

In the case of the *round-half-even* algorithm (which is often referred to as *Banker's Rounding* because it is commonly used in financial calculations), half-way values are rounded toward the nearest *even* number. Thus, 3.5 will round *up* to 4 and 4.5 will round *down* to 4. This algorithm is, by definition, symmetric for positive and negative values, so both -3.5 and -4.5 will round to -4.

In the case of data sets that feature a relatively large number of "half-way" values (financial records provide a good example of this), the *round-half-even* algorithm performs significantly better than the *round-half-up* scheme in terms of total bias. However, in the case of data sets containing a relatively small number of "half-way" values – such as real-world values being applied to DSP algorithms – the overhead involved in performing the *round-half-even* algorithm in hardware does not justify its use (see also the filter examples shown later in this paper).

**Round-half-odd:** This is the theoretical counterpart to the *round-half-even* algorithm, in which half-way values are rounded toward the nearest odd number. In this case, 3.5 will round to 3 and 4.5 will round to 5 (similarly, -3.5 will round to -3, and -4.5 will round to -5). The reason we say "theoretical" is that, in practice, the *round-half-odd* algorithm is rarely (if ever) never used because it will never round to zero (rounding to zero is often a desirable attribute for rounding algorithms).

**Round-alternate:** Also known as *alternate rounding*, this is similar in concept to the *round-half-even* and *round-half-odd* schemes discussed above, in that the purpose of the *round-alternate* algorithm is to minimize the bias that can be caused by always rounding half-way values in the same direction.

In the case of the *round-half-even* approach, for example, it would be possible for a bias to occur if the data being processed contained a disproportionate number of odd and even half-way values. One solution is to use the *round-alternate* algorithm, in which the first half-way value is rounded up (for example); the next is rounded down, the next up, the next down, and so on.

**Round-random:** This may also be referred to as *random rounding* or *stochastic rounding*, where the term "stochastic" comes from the Greek *stokhazesthai*, meaning "to guess at." With this technique, in the case of "half-way" values, we effectively toss a metaphorical coin in the air and randomly (or pseudo-randomly) round the value up or down.

Although this technique typically gives the best overall result over a large number of calculations, it is only employed in very specialized applications, because the nature of this algorithm makes it difficult to implement and tricky to verify the results.

**Round-ceiling:** This refers to rounding towards positive infinity. In the case of a positive number, the result will remain unchanged if the digits to be discarded are all zero; otherwise it will be rounded up. For example, 3.0 will be rounded to 3, but 3.1, 3.2, 3.3, 3.4, 3.5, 3.6, 3.7, 3.8, and 3.9 will all be rounded to 4. By comparison, in the case of a negative number, the unwanted digits are simply discarded. For example, -3.0, -3.1, -3.2, -3.3, -3.4, -3.5, -3.6, -3.7, -3.8, and -3.9 will all be rounded to -3.

This algorithm (which is implemented using the *ceil* function in MATLAB), results in a cumulative positive bias and also requires additional logic when realized in hardware. For these reasons, the round-ceiling algorithm is not often used in hardware implementations. (In the case of non-hardware implementations, or during analysis of a system using software simulation, the *round-ceiling* approach is sometimes employed to determine the upper limit of the algorithm for use in diagnostic functions).

**Round-floor:** The counterpart to *round-ceiling*, this refers to rounding towards negative infinity. In the case of a negative number, the result will remain unchanged if the digits to be discarded are all zero; otherwise it will be rounded down. For example, -3.0 will be rounded to -3, but -3.1, -3.2, -3.3, -3.4, -3.5, -3.6, -3.7, -3.8, and -3.9 will all be rounded to -4. By comparison, in the case of a positive number, the unwanted digits are simply discarded. For example, 3.0, 3.1, 3.2, 3.3, 3.4, 3.5, 3.6, 3.7, 3.8, and 3.9 will all be rounded to 3.

This algorithm (which is implemented using the *floor* function in MATLAB), results in a cumulative negative bias. However, round-floor is "cheap" in terms of a hardware implementation since it involves only a simple truncation; this technique is therefore very often used with regard to hardware implementations. (In the case of non-hardware implementations, or during analysis of a system using software simulation, the *round-floor* approach is sometimes employed to determine the lower limit of the algorithm for use in diagnostic functions).

**Round-toward-zero:** As its name suggests, this refers to rounding in such a way that the result heads toward zero. For example, 3.1, 3.2, 3.3, 3.4, 3.5, 3.6, 3.7, 3.8, and 3.9 will all be rounded to 3. Similarly, -3.1, -3.2, -3.3, -3.4, -3.5, -3.6, -3.7, -3.8, and -3.9 will all be rounded to -3.

Another way to think about this is that *round-toward-zero* (which is implemented using the *fix* function in MATLAB) acts in the same way as the *round-floor* algorithm for positive numbers and as the *round-ceiling* algorithm for negative numbers.

**Round-away-from-zero:** The counterpart to *round-toward-zero*, this refers to rounding in such a way that the result heads away from zero. For example, 3.1, 3.2, 3.3, 3.4, 3.5, 3.6, 3.7, 3.8, and 3.9 will all be rounded to 4. Similarly, -3.1, -3.2, -3.3, -3.4, -3.5, -3.6, -3.7, -3.8, and -3.9 will all be rounded to -4.

Another way to think about this is that *round-away-from-zero* acts in the same manner as a *round-ceiling* algorithm for positive numbers and as a *round-floor* algorithm for negative numbers.

**Round-up:** The actions of this rounding mode depend on what one means by "up". Some applications understand "up" to refer to heading towards positive infinity; in this case, *round-up* is synonymous for *round-ceiling*.

Alternatively, some applications regard "up" as referring to an absolute value heading away from zero; in this case, *round-up* acts in the same manner as the *round-away-from-zero* algorithm.

**Round-down:** The counterpart to the *round-up* algorithm, the actions of this mode depend on what one means by "down". Some applications understand "down" to refer to heading towards negative infinity; in this case, *round-down* is synonymous for *round-floor*.

Alternatively, some applications regard "down" as referring to an absolute value heading toward zero; in this case, *round-down* acts in the same manner as the *round-toward-zero* algorithm.

**Truncation:** Also known as *chopping*, truncation simply means discarding any unwanted digits. Although this would appear – on the surface – to be relatively simple, things become a little more interesting when we realize that the actions resulting from truncation vary depending on whether we are working with sign-magnitude, unsigned, or signed (complement) values. In the case of sign-magnitude values (like the standard decimal values we've been considering thus far), and also when working with unsigned binary values, the actions of truncation are identical to those of the *round-toward-zero* mode. In the case of signed binary values, however, truncation works somewhat differently for negative values (we'll return to this point shortly).

post a commentregarding this story.