Fast Integer Rounding

Fri 22 December 2023 Algorithms algorithm / integer rounding

Overview

• installation: see https://arrizza.com/setup-common

Summary

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

Scripts

• See Quick Start for information on using scripts.
• See xplat-utils submodule for information on the submodule.

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 / (double) 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. 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 gets 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 with every integer less than that value

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

// 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;
//
// or you can use the one-line equivalent:
uint_fast64_t rounded_i = (((n << 1U) / m) + 1U) >> 1U;

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 (rounded_d != (double) rounded_i)
{
// it's an error!
errs++;
}

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

Result

Function do_rounded() has a flag to choose either a fixed sample of results

 n   m   act=n/m   rounded      fast
 15   1      15.0      15.0        15
 15   2       7.5       8.0         8
 15   3       5.0       5.0         5
 15   4       3.8       4.0         4
 15   5       3.0       3.0         3
 <snip>
 25  22       1.1       1.0         1
 25  23       1.1       1.0         1
 25  24       1.0       1.0         1
Found 0 errors in 38 checks in 0.000 seconds

or to run 100 randomly chosen integers. That resulted in about 1.7 billion divisions. The output was:

Found 0 errors in 1717234415 checks in 26.525 seconds

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.