Fast floor of a signed integer division in C / C++

user_432509 0
Viewed 3940

In C a floor division can be done, eg:

int floor_div(int a, int b) {
    int d = a / b;
    if (a < 0 != b < 0) {  /* negative output (check inputs since 'd' isn't floored) */
        if (d * a != b) {  /* avoid modulo, use multiply instead */
            d -= 1;        /* floor */
        }
    }
    return d;
}

But this seems like it could be simplified.

Is there a more efficient way to do this in C?

Note that this is nearly the reverse of this question: Fast ceiling of an integer division in C / C++

floor-division integer-division c
4 Answers

The remainder of a "floor division", is either 0, or has the same sign as the divisor.

(the proof)  
a: dividend  b: divisor
q: quotient  r: remainder

q = floor(a/b)
a = q * b + r  
r = a - q * b = (a/b - q) * b  
                ~~~~~~~~~
                    ^ this factor in [0, 1)

And luckily, the result of / and % in C/C++ is standardized to "truncated towards zero" after C99/C++11. (before then, library function div in C and std::div in C++ played the same roles).

Let's compare "floor division" and "truncate division", focus on the range of remainder:

       "floor"     "truncate"
b>0    [0, b-1]    [-b+1, b-1]
b<0    [b+1, 0]    [b+1, -b-1]

For convenience of discussion:

  • let a, b = dividend and divisor;
  • let q, r = quotient and remainder of "floor division";
  • let q0, r0 = quotient and remainder of "truncate division".

Assume b>0, and unluckily, r0 is in [-b+1, -1]. However we can get r quite easily: r = r0+b, and r is guaranteed to be in [1, b-1], which is inside the "floor" range. The same is true for the case b<0.

Now that we can fix the remainder, we can also fix the quotient. The rule is simple: we add b to r0, then we have to subtract 1 from q0.

As an ending, an implementation of "floor division" in C++11:

void floor_div(int& q, int& r, int a, int b)
{
    int q0 = a / b;
    int r0 = a % b;
    if (b > 0){
        q = r0 >= 0 ? q0 : q0 - 1;
        r = r0 >= 0 ? r0 : r0 + b;
    }
    else {
        q = r0 <= 0 ? q0 : q0 - 1;
        r = r0 <= 0 ? r0 : r0 + b;
    }
}

Compared to the famous (a < 0) ^ (b < 0) method, this method has an advantage: if the divisor is a compile-time constant, only one comparison is needed to fix the results.

user_92411380
Related