Floored integer division

Question

Is there an easy, efficient and correct (i.e. not involving conversions to/from double) way to do floored integer division (like e.g. Python offers) in C#.

In other words, an efficient version of the following, that does not suffer from long/double conversion losses.

(long)(Math.Floor((double) a / b))

or does one have to implement it oneself, like e.g.

static long FlooredIntDiv(long a, long b)
{
    if (a < 0)
    {
        if (b > 0)
            return (a - b + 1) / b;
        // if (a == long.MinValue && b == -1) // see *) below
        //    throw new OverflowException();
    }
    else if (a > 0)
    {
        if (b < 0)
            return (a - b - 1) / b;
    }
    return a / b;
}

*) Although the C# 4 spec of the Division operator leaves it open whether OverflowException is raised inside unchecked, in reality it does throw (on my system) and the Visual Studio .NET 2003 version even mandated it throw:

If the left operand is the smallest representable int or long value and the right operand is –1, [..] System.OverflowException is always thrown in this situation, regardless of whether the operation occurs in a checked or an unchecked context.

Edit

The crossed out statements about checked and unchecked are all nice and well, but checked is in fact only a compile time concept, so whether my function should wrap around or throw is up to me anyway, regardless of whether code calling the function is inside checked or not.

Marleah

You mean, an alternative to just passing the result into Math.Floor? – Asis

Integer division is already doing that, not literally calling Math.Floor, but result is the same, it cuts off whole decimal part. Math.Floor is redundant in this case. – Ballroom

@maremp: only for positive results. See the OP's table for examples of "floor" negative results that are different from the C# / operator implementation. – Threefold

Oh yeah @PeterDuniho, I forgot about that... – Ballroom

Not a solution, but I believe your code might fail in some corner cases. var a = long.MinValue; var b = -1L; OR var a = long.MaxValue; var b = -1L;. – Photojournalism

Answer 1

You can try this:

if (((a < 0) ^ (b < 0)) && (a % b != 0))
{
   return (a/b - 1);
}
else
{
   return (a/b);
}

Edit (after some discussions in comments below):

Without using if-else, I would go like this:

return (a/b - Convert.ToInt32(((a < 0) ^ (b < 0)) && (a % b != 0)));

Note: Convert.ToIn32(bool value) also needs a jump, see implemention of the method:

return value? Boolean.True: Boolean.False;

Theoretically, it is not possible to calculate the division for a = long.MinValue and b = -1L, since the expected result is a/b = abs(long.MinValue) = long.MaxValue + 1 > long.MaxValue. (Range of long is –9,223,372,036,854,775,808 to 9,223,372,036,854,775,807.)

Janiculum

PS: ^ is xor operator – Janiculum

Thanks L16H7. When implementing my FlooredIntDiv above, I started off similar to your solution, which is as efficient, and I believe, as correct as mine (I haven't thought through whether your solution catches all the 0 corner cases), but I went the if/else route because I think it's easier to read. So it is equivalent to my sample implementation, but neither easier nor more efficient. – Marleah

Normally, an "efficient" formula should not use any "if" statements and the like. It should based purely on low-level arithmetic operators. – Gun

If I have to remove if-else, I would go like this: { return (a/b - Convert.ToInt32(((a < 0) ^ (b < 0)) && (a % b != 0))); }. I'm using the fact that true = 1 and false = 0 when bool is converted to int. – Janiculum

@L16H7 FYI: Your solution throws an OverflowException for a = long.MinValue and b = -1L. I tested it because publicgk (incorrectly) suggested my solution might fail for those numbers. – Marleah

It should fail since for a = long.MinValue and b = -1L, the expected result is a/b = abs(long.MinValue) = long.MaxValue + 1. Range of long is –9,223,372,036,854,775,808 to 9,223,372,036,854,775,807. Does your program give the correct result? @EugeneBeresovsky – Janiculum

Put a limit on the input. :) Case closed. @EugeneBeresovsky – Janiculum

@L16H7 Re: correctness. I investigated a bit more, removed my previously uninformed comments and updated the question instead. – Marleah

So what do you want now? @EugeneBeresovsky. – Janiculum

@L16H7 I was just trying to say (as my question now clarifies) - neither your nor my implementation is "incorrect" - so sorry for upsetting the applecart. I'm however still interested in any easy and efficient solution, if there is one. – Marleah

Let us continue this discussion in chat. – Janiculum

What was the outcome? I'm interested too. The link to the chat does not work. – Chloe

There may be no if-elses, but wouldn't using && cause branching due to short-circuit logic? (branching when the left hand side is false) Using & would prevent short circuiting. – Ursine

Answer 2

If both arguments a and b are long (or any other integer type)

long c = a/b;

is giving a floor integer division in C# just like in Python. Nothing to convert to anything. It is even using a proper integer operation on the processor level.

All operations in C# are executed based on their types.

Ribband

Integer division rounds towards zero, so if a or b are negative the result will be rounded up instead of down. – Ilex