Does anyone know of an open-source C or C++ library with functions implementing every integer division mode one might want? Possible behaviors (for positive result):
round_down, round_up,
round_to_nearest_with_ties_rounding_up,
round_to_nearest_with_ties_rounding_down,
round_to_nearest_with_ties_rounding_to_even,
round_to_nearest_with_ties_rounding_to_odd
with each (aside from round-to-even and round-to-odd) having two variants
// (round relative to 0; -divide(-x, y) == divide(x, y))
negative_mirrors_positive,
// (round relative to -Infinity; divide(x + C*y, y) == divide(x, y) + C)
negative_continuous_with_positive
.
I know how to write it, but surely someone has done so already?
As an example, if we assume (as is common and is mandated in C++11) that built-in signed integral division rounds towards zero, and that built-in modulus is consistent with this, then
int divide_rounding_up_with_negative_mirroring_positive(int dividend, int divisor) {
// div+mod is often a single machine instruction.
const int quotient = dividend / divisor;
const int remainder = dividend % divisor;
// this ?:'s condition equals whether quotient is positive,
// but we compute it without depending on quotient for speed
// (instruction-level parallelism with the divide).
const int adjustment = (((dividend < 0) == (divisor < 0)) ? 1 : -1);
if(remainder != 0) {
return quotient + adjustment;
}
else {
return quotient;
}
}
Bonus points: work for multiple argument types; fast; optionally return modulus as well; do not overflow for any argument values (except division by zero and MIN_INT/-1, of course).
If I don't find such a library, I'll write one in C++11, release it, and link to it in an answer here.
So, I wrote something. The implementation is typically ugly template and bitwise code, but it works well. Usage:
divide(dividend, divisor, rounding_strategy<...>())
where rounding_strategy<round_up, negative_mirrors_positive> is an example strategy; see list of variants in my question or in the source code. https://github.com/idupree/Lasercake/blob/ee2ce96d33cad10d376c6c5feb34805ab44862ac/data_structures/numbers.hpp#L80
depending only on C++11 [*], with unit tests (using Boost Test framework) starting at https://github.com/idupree/Lasercake/blob/ee2ce96d33cad10d376c6c5feb34805ab44862ac/tests/misc_utils_tests.cpp#L38
It is polymorphic, decent speed, and does not overflow, but doesn't currently return modulus.
[*] (and on boost::make_signed and boost::enable_if_c, which are trivial to replace with std::make_signed and std::enable_if, and on our caller_error_if() which can be replaced with assert() or if(..){throw ..} or deleted. You can ignore and delete the rest of the file assuming you're not interested in the other things there.)
Each divide_impl's code can be adapted to C by replacing each T with e.g. int and T(CONSTANT) with CONSTANT. In the case of the round_to_nearest_* variant, you'd either want to make the rounding kind be a runtime argument or create six copies of the code (one for each distinct rounding variation it handles). The code relies on '/' rounding towards zero, which is common and also specified by C11 (std draft N1570 6.5.5.6) as well as C++11. For C89/C++98 compatibility, it could use stdlib.h div()/ldiv() which are guaranteed to round towards zero (see http://www.linuxmanpages.com/man3/div.3.php , http://en.cppreference.com/w/cpp/numeric/math/div )