Overview
PyPi module | N/A |
git repository | https://bitbucket.org/arrizza-public/fast-integer-rounding |
git command | git clone git@bitbucket.org:arrizza-public/fast-integer-rounding.git |
Verification Report | https://arrizza.com/web-ver/fast-integer-rounding-report.html |
Version Info |
|
- 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.