tags:

views:

288

answers:

4

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.

+2  A: 

Math.Floor((double)a/(double)b)
if you need it as an int, cast it afterwards
(int)Math.Floor((double)a/(double)b)

ItzWarty
`decimal` is the [slowest](http://msdn.microsoft.com/en-us/library/xtba3z33.aspx) numeric type, and it doesn't add anything here. `float` or `double` would be more appropriate.
Matthew Flaschen
You also don't need to cast the denominator, just the numerator.
Phong
@Matthew Flaschen: I was considering that. I did not realize the int he was talking about was an int32. If you plug in the extraneous values for a and b [Int64.MaxValue-1 and Int64.MaxValue respectively], using double will break because of floating point error, and you'll get 1 instead of 0. Answer has been fixed.
ItzWarty
This answer works, but given the performance cost of fp, I'd consider it no improvement over my "kludgey" method ideas.
Conrad Albrecht
+4  A: 

If you wanted to write this just using integers in a relatively succinct way, then you can write this:

var res = a / b - (a % b < 0 ? 1 : 0);

This probably compiles to quite a few instructions, but it may still be faster than using floating-points.

Tomas Petricek
The OP didn't mention C, but it's still worth noting this is not guaranteed to work in C89 due to implementation-defined %. I think you can generalize it by changing to `a % b != 0`.
Matthew Flaschen
@Matthew: That's tricky. However, it needs to return 0 if `a % b` returns a number larger than zero (so that's why I need `<` in C#).
Tomas Petricek
Matthew Flaschen
I think the given answer is implementation-dependent, but Matthew's modification appears concise and reliable. If it was an answer I'd checkmark it. Thank you (everyone)!
Conrad Albrecht
@Matthew: actually, this is guarenteed to work by both C89 and C99 -- they require that `(a/b)*b + a%b == a` unless `b == 0` even though the actual values returned by `/` and `%` are implementation defined for negative operands. Your version will fail if the builtin / rounds towards -inf instead of 0.
Chris Dodd
@Chris: At least by MS docs, in both C# and C++ / rounds toward 0, not -inf.
Conrad Albrecht
@Chris, you're right. I forgot that `/` was also implementation-defined in C89.
Matthew Flaschen
+2  A: 

[c++]

This is probably what you meant by 'kludgey', but it's what I came up with ;)

int divideDown(int a, int b){
    int r=a/b;
    if (r<0 && r*b!=a)
        return r-1;
    return r;
}

In the if statement, I put r<0 - however I'm not sure if that's what you want. You may wish to change the if statement to

if (a<0 && b>0)

which would be consistent with your description "Seems like whenever I divide a negative int by a positive int ".

Cam
This *is* what I meant by klugey, but I don't know anything better. Especially for the r*b!=a test, which is probably more efficient than a%b!=0, and justifies the extra lines of code as compared to the single-line expressions offered, I award this "the answer".
Conrad Albrecht
+4  A: 

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.

Norman Ramsey
I thought int32 -> double wouldn't lose any precision. But I just optimized some fp code where fstp ops (on near-0 numbers) were taking most of my CPU time. Maybe not relevant, but I'm soured on unnecessary fp for now. ;)
Conrad Albrecht