The rounding integer implementation considers an integer as a binary fixed-point number with no bits to the right of the radix point. Integer addition, subtraction, and multiplication produce exact results. They are implemented using the arithmetic operations for the underlying integral type.
Integer division truncates toward zero. To round the result of integer division, the code takes advantage of the C++ modulus (%) operator. The value of a%b is the integer remainder of the expression a/b. If the remainder is greater than or equal to half the divisor, the quotient is rounded up by adding 1. Rather than divide the divisor by 2 (reintroducing the undesirable truncation), I double the remainder (using multiplication, which has an exact result) and compare it to the divisor.
assert(n >= 0 && d > 0); q = n / d; r = n % d; if ((r<<1) >= d) q += 1;
The integer division instruction on most processors produces both a quotient and a remainder. The Visual C++ optimizer efficiently reuses the already-computed remainder instead of recomputing it. On more modest hardware, or less-optimizing compilers, the Standard C runtime function ldiv() can be used to produce a structure containing both quotient and remainder. ldiv() is not an intrinsic function in VC7, so it has a high performance cost.
The signs of the operands present a further challenge in rounding. The signs of the quotient and remainder depend on the signs of the divisor and dividend. Handling all four cases of operand signs generates some code bloat, but not much speed penalty. I have verified this code on Intel-architecture processors. Other processors implement the sign of the remainder differently, so users of this template should verify its correctness with their processor.
I investigated a branch-free rounding computation to improve performance, but there was no observable improvement on the PC. The branch-free code is compact, but was difficult to construct. Listing Two shows the division code with rounding.
Listing Two
// Listing2.h: scaled multiplication and rounded division
template <typename T> inline T scaled_multiplication(T a, T b, int s)
{
T p = rounded_division(a * b, (T)s);
return p;
}// end rounded_multiplication
template <typename T> inline T rounded_division(T n, T d)
{
T q = n / d;
T r = n % d;
# if defined BRANCH_FREE
q += sign(n^d) & neg(abs(d) - (abs(r)<<1) - 1);
# elif defined NO_ROUNDING
# else
if (n < 0)
if (d < 0)
{// num -, den -, quot +, rem -
if ((r << 1) < d)
++q;
}
else // d >= 0)
{// num -, den +, quot -, rem -
if ((-r << 1) > d)
--q;
}
else // n >= 0
if (d < 0)
{// num +, den -, quot -, rem +
if ((-r << 1) < d)
--q;
}
else // d >= 0
{// num +, den +, quot +, rem +
if ((r << 1) > d)
++q;
}
# endif
return q;
} // end rounded_division
