Everything you wanted to know about rounding (but were too afraid to ask) - Embedded.com

Everything you wanted to know about rounding (but were too afraid to ask)

I remember when I was a kid at school and the teacher first taught us how to round numbers. The technique he taught us is known as arithmetic rounding , also called round-half-up . In this case, values such as 3.1, 3.2, 3.3, and 3.4 round down to 3; values of 3.6, 3.7, 3.8, and 3.9 round up to 4; and a “half-way value” such as 3.5 will also round up to 4.

The tricky point with the round-half-up algorithm — which our teacher somehow neglected to mention — 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 this algorithm. 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, mathematicians (bless their little cotton socks) 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.

The problem lies in the fact that different applications can opt for the symmetric or asymmetric implementation depending on the preference of their creators. The round method of the Java Math Library, for example, provides an asymmetric implementation of the round-half-up algorithm, while the round function in MATLAB provides a symmetric implementation. And just to keep us on our toes, the round function in Visual Basic for Applications 6.0 actually implements the round-half-even algorithm, which is also known as “Banker's rounding.”

The bottom line is that the concept of rounding is non-trivial, and there are many different approaches one can take, including round-half-up (symmetric and asymmetric), round-half-down (symmetric and asymmetric), round-half-even , round-half-odd , round-half-ceiling , and round-half-floor (and don’t even get me started talking about things like stochastic rounding).


Summary of main rounding modes
[as applied to standard (sign-magnitude) decimal values].

I became interested in all of this stuff when we (my chum Alvin and I) were writing How Computers Do Math . This spawned a rather interesting Rounding Algorithms paper on our DIY Calculator website. In addition to rounding decimal values, this paper also considers the rounding of sign-magnitude and signed binary values.

The reason I'm waffling on about this here is that I just received an email as follows:

I am Olivier Rukundo with Tilburg University in the Netherlands, currently working on computational issues in computer vision and graphics.

I can't thank you enough for having published this introduction to rounding algorithms. It is two years now since I started attempting to solve the round-offs errors problems.

I am writing because, after reading your page, I had problems of finding the source codes of the algorithms listed on this your page.

I must admit that this puzzled me, because I didn’t actually recall mentioning the source code for the algorithms listed on this page. I just bounced over to my paper and skimmed through it… no mention of source code. “Hmm,” I thought to myself. So I emailed Olivier asking if this was the page to which he was referring, and he replied that he was, in fact, talking about this article on EE Times.

If the truth be told, I'd forgotten all about this article, but now I come to re-read it, I realize that it is worth a gander. The first page summarizes the algorithms presented in my original paper. Where things become really interesting is the second page, because a guy called Tim Vanevenhoven from AccelChip (which was subsequently purchased by Xilinx in 2006) was kind enough to create and run some test cases in MATLAB to illustrate the types of errors associated with the different rounding schemes applied at various stages throughout a digital filter. And yes! There at the bottom is a reference and link to the source code Tim used. Hurray!

I just downloaded the ZIP file containing this source code and emailed it to Oliver. Then I thought to myself “all of this information is really rather useful,” at which point I decided to remind the members of the Embedded.com and EETimes.com communities that it is there, ripe for the plucking, just waiting to be perused and pondered. If you do have a moment to take a look, I'd be very interested to hear what you think — especially if there's anything you think I missed.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.