How to integer-divide round negative numbers *down*?

Question

Seems like whenever I divide a negative int by a positive int, I need it to round down (toward -inf), not toward 0. But both C# and C++ round toward 0.

So I guess I need a DivideDownward() method. I can write it in a few lines with a test for negative and so on, but my ideas seem klugey. So I'm wondering if I'm missing something and if you have an "elegant" way to round negative division downward.

Answer 1

Whenever I divide a negative int by a positive int, I need it to round down.

It's hell, isn't it? Knuth wrote why this is the right way to do things, but we're stuck with legacy integer hardware.

• If you can afford the loss of precision, the simplest and cleanest way to do this is to cast a 32-bit integer to a 64-bit double and use the FP rounding mode to round toward minus infinity when you convert the quotient back to integer. Today's floating-point units are pretty fast and may actually divide faster than an integer unit; to be sure, you'd have to measure.

• If you need full 64-bit integer precision, I've dealt with this problem as a compiler writer by doing the two conditional branches so that you wind up dividing the magnitudes, then get the correct sign. But this was a while back when the conditional branch was cheap compared to a divide; on today's hardware, I would have to experiment before I'd be able to recommend something.

• In principle, you could pull the floating-point trick on 64-bit ints by using the legacy Intel 80-bit floating-point numbers, but it's wildly unportable, and I don't trust Intel to keep making that unit fast. These days the floating point speed is in the SSE unit.

• Places to look for other tricks would include Hank Warren's book Hacker's Delight (my copy is at work) and the MLton compiler for Standard ML, which requires integer division to round toward minus infinity.

Whatever you do, when you get settled on it, if you are using C++ or C99, stick your divide routine into a .h file and make it static inline. That way when your solution turns out to be suboptimal for new whizbang hardware delivered in 5 years, you have one place to change it.