Fast Integer Rounding

From arrizza.org wiki

Jump to navigation Jump to search
Previous ⇦ Running Average Algorithms ⇫ Up Algorithms ⇨ Next

Overview

This page shows how to round the result of an integer division quickly using low level operations.

Git repository

https://bitbucket.org/arrizza/algorithms/src/master/rounded.cpp

git clone git@bitbucket.org:arrizza/algorithms.git

The Algorithm

Infinite Precision

To perform a division using two variables is easy:

and you get infinite precision for free. You only round the result when it's easier for people to understand the answer.

Using Doubles

In software, it's not possible to get infinite precision, but for almost all applications you can get close using float or double:

   #include <cmath>
   // ... snip ...
   
   double actual = (double) n / m;

   // round it using the stdlib round() function
   double rounded_d = std::round(actual);

   printf("%3d %3d %8.1f %8.1f\n", n, m, actual, rounded_d);

will print the result of to one digit after the decimal point and it also shows the rounded result (to the integer).

Using Integers

But what if you only have integers to work with? Floating point arithmetic is expensive and takes up a lot of room and so you need a nice simple way to get a correct rounded value:

   int m = 11;
   int n =   3;
   int result_i = m / n;

   printf("%3d %3d %d\n", n, m,  rounded_i);
   // prints 3
 

The Trick

Using normal integer arithmetic truncates the result. To get proper rounding you have to do a trick - you multiply everything by 10, do the division and rounding, and then divide the result by 10. This get's you an extra digit of precision that you use to do the rounding.

the first part gets a result that is 10 times more than it should be. Then 5 is added it to it:

If the result ended with 0, 1, 2, 3, or 4, adding 5 to it does not cause it to roll over into the next decade. For example, if it was 32, then adding 5 gets it to 37, it's still in the 30s.

But if it ended with 5 or more, then adding 5 will cause the tens digit to roll over to the value. For example if it was 35, then adding 5 gets it to 40, so now the tens digit has bumped to the next value. And 36 goes to 41, and so on up to 39 which goes to 44.

And finally dividing that result by 10, gets you the correct rounded value. gets you 3, gets you 4, etc.

Simplifying the Trick With Another Trick

Multiplying by 10, adding 5 and dividing by 10 are fairly expensive operations even with integers. So let's do another trick, let's factor out 5 from the original formula:

Why? Because we can replace the individual operations with simpler and faster ones.

n * 2

can be done with left shift

 n << 1

And

x + 1

can be done with an increment

 x++

And finally

y / 2

can be done with right shift

 y >> 1

Putting it all together:

      // rounded_i = (((n * 2) / m) + 1) / 2;
      // simplifies to:
      int two_n     = n << 1;
      int rounded_i = two_n / m;
      ++rounded_i;
      rounded_i >>= 1;

Testing

How do we know this works correctly?

To test it we can randomly choose a bunch of integers,

  std::random_device              rd;
  std::mt19937                    generator(rd());
  // choose uniformly distributed random numbers
  std::uniform_int_distribution<> dist(1, 32452843);

  int      n = dist(generator);

divide each one as many times as it makes sense

    // divide n with 1 to n - 1
    for (int m = 1; m < n; ++m)
      {

      // calculate it using integer arithmetic:
      //     rounded_i = (((n * 10) / m) + 5) / 10;
      // which is equivalent to:
      // rounded_i = (((n * 2) / m) + 1) / 2;
      // which simplifies to:
      int two_n     = n << 1;
      int rounded_i = two_n / m;
      ++rounded_i;
      rounded_i >>= 1;

and compare the rounded values against a rounded value using doubles:

      // get the actual value as a double
      double actual = (double) n / m;

      // round it using the stdlib round() function
      double rounded_d = std::round(actual);

      // the std:round and the integer arithmetic should match
      // if not, print a warning
      if ((int) rounded_d != rounded_i)
        {
        // it's an error!
        errs++;
        }

  printf("Found %d errors in %d checks\n", errs, num_checked);

See the Mercurial files for the full set of code.

Result

I ran this using 100 randomly chosen integers. That resulted in about 1.7 billion divisions. The output was:

Found 0 errors in 1769307763 checks

In other words, the result of rounding using doubles matched the result of rounding using integers for all divisions that were tested.

If you're not convinced, run it again. That will do another 1+ billion divisions. Repeat until you're convinced.

Personal tools