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

Question

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++

Answer 1

Less assembly instructions in the generated code and quicker path to the result I think.

For the RISC machines with huge numbers of registers this one is better, as there are no branches at all and it is good for the pipeline and the cache.

For x86 actually it does not matter.

int floor_div3(int a, int b) {
    int d = a / b;


    return d * b == a ? d : d - ((a < 0) ^ (b < 0));
}

Answer 2

div() functions in standard C

I think you should look at the div() functions from <stdlib.h>. (They are standard C functions and are defined in all versions of the standard, despite the link to the POSIX specification.)

The C11 standard §7.22.6.2 specifies:

The div … functions compute numer / denom and numer % denom in a single operation.

Note that C11 specifies integer division in §6.5.5 (and C99 was similar):

When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded.¹⁰⁵⁾

¹⁰⁵⁾ This is often called "truncation toward zero".

but C90 (§6.3.5) was more flexible yet less useful:

When integers are divided and the division is inexact. if both operands are positive the result of the / operator is the largest integer less than the algebraic quotient and the result of the % operator is positive. If either operand is negative, whether the result of the / operator is the largest integer less than or equal to the algebraic quotient or the smallest integer greater than or equal to the algebraic quotient is implementation-defined, as is the sign of the result of the % operator.

floor_div()

The computational code for the requested floor_div() using div() is neat and tidy.

int floor_div(int a, int b)
{
    assert(b != 0);
    div_t r = div(a, b);
    if (r.rem != 0 && ((a < 0) ^ (b < 0)))
        r.quot--;
    return r.quot;
}

Test code

The print formatting in the code below is tailored rather precisely to the sample data. (It would be better, but more expansive, to use %4d and %-4d throughout). This code prints lines of length 89 characters plus newline; the more general layout would print lines of length 109. Neither avoids the horizontal scroll bar on SO.

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

static int floor_div(int a, int b)
{
    assert(b != 0);
    div_t r = div(a, b);
    if (r.rem != 0 && ((a < 0) ^ (b < 0)))
        r.quot--;
    return r.quot;
}

static void test_floor_div(int n, int d)
{
    assert(d != 0);
    printf(   "%3d/%-2d = %-3d (%3d)", +n, +d, floor_div(+n, +d), +n / +d);
    printf(";  %3d/%-3d = %-4d (%4d)", +n, -d, floor_div(+n, -d), +n / -d);
    if (n != 0)
    {
        printf(";  %4d/%-2d = %-4d (%4d)", -n, +d, floor_div(-n, +d), -n / +d);
        printf(";  %4d/%-3d = %-3d (%3d)", -n, -d, floor_div(-n, -d), -n / -d);
    }
    putchar('\n');
}

int main(void)
{
    int numerators[] = { 0, 1, 2, 4, 9, 23, 291 };
    enum { NUM_NUMERATORS = sizeof(numerators) / sizeof(numerators[0]) };
    int denominators[] = { 1, 2, 3, 6, 17, 23 };
    enum { NUM_DENOMINATORS = sizeof(denominators) / sizeof(denominators[0]) };

    for (int i = 0; i < NUM_NUMERATORS; i++)
    {
        for (int j = 0; j < NUM_DENOMINATORS; j++)
            test_floor_div(numerators[i], denominators[j]);
        putchar('\n');
    }

    return 0;
}

Test output

  0/1  = 0   (  0);    0/-1  = 0    (   0)
  0/2  = 0   (  0);    0/-2  = 0    (   0)
  0/3  = 0   (  0);    0/-3  = 0    (   0)
  0/6  = 0   (  0);    0/-6  = 0    (   0)
  0/17 = 0   (  0);    0/-17 = 0    (   0)
  0/23 = 0   (  0);    0/-23 = 0    (   0)

  1/1  = 1   (  1);    1/-1  = -1   (  -1);    -1/1  = -1   (  -1);    -1/-1  = 1   (  1)
  1/2  = 0   (  0);    1/-2  = -1   (   0);    -1/2  = -1   (   0);    -1/-2  = 0   (  0)
  1/3  = 0   (  0);    1/-3  = -1   (   0);    -1/3  = -1   (   0);    -1/-3  = 0   (  0)
  1/6  = 0   (  0);    1/-6  = -1   (   0);    -1/6  = -1   (   0);    -1/-6  = 0   (  0)
  1/17 = 0   (  0);    1/-17 = -1   (   0);    -1/17 = -1   (   0);    -1/-17 = 0   (  0)
  1/23 = 0   (  0);    1/-23 = -1   (   0);    -1/23 = -1   (   0);    -1/-23 = 0   (  0)

  2/1  = 2   (  2);    2/-1  = -2   (  -2);    -2/1  = -2   (  -2);    -2/-1  = 2   (  2)
  2/2  = 1   (  1);    2/-2  = -1   (  -1);    -2/2  = -1   (  -1);    -2/-2  = 1   (  1)
  2/3  = 0   (  0);    2/-3  = -1   (   0);    -2/3  = -1   (   0);    -2/-3  = 0   (  0)
  2/6  = 0   (  0);    2/-6  = -1   (   0);    -2/6  = -1   (   0);    -2/-6  = 0   (  0)
  2/17 = 0   (  0);    2/-17 = -1   (   0);    -2/17 = -1   (   0);    -2/-17 = 0   (  0)
  2/23 = 0   (  0);    2/-23 = -1   (   0);    -2/23 = -1   (   0);    -2/-23 = 0   (  0)

  4/1  = 4   (  4);    4/-1  = -4   (  -4);    -4/1  = -4   (  -4);    -4/-1  = 4   (  4)
  4/2  = 2   (  2);    4/-2  = -2   (  -2);    -4/2  = -2   (  -2);    -4/-2  = 2   (  2)
  4/3  = 1   (  1);    4/-3  = -2   (  -1);    -4/3  = -2   (  -1);    -4/-3  = 1   (  1)
  4/6  = 0   (  0);    4/-6  = -1   (   0);    -4/6  = -1   (   0);    -4/-6  = 0   (  0)
  4/17 = 0   (  0);    4/-17 = -1   (   0);    -4/17 = -1   (   0);    -4/-17 = 0   (  0)
  4/23 = 0   (  0);    4/-23 = -1   (   0);    -4/23 = -1   (   0);    -4/-23 = 0   (  0)

  9/1  = 9   (  9);    9/-1  = -9   (  -9);    -9/1  = -9   (  -9);    -9/-1  = 9   (  9)
  9/2  = 4   (  4);    9/-2  = -5   (  -4);    -9/2  = -5   (  -4);    -9/-2  = 4   (  4)
  9/3  = 3   (  3);    9/-3  = -3   (  -3);    -9/3  = -3   (  -3);    -9/-3  = 3   (  3)
  9/6  = 1   (  1);    9/-6  = -2   (  -1);    -9/6  = -2   (  -1);    -9/-6  = 1   (  1)
  9/17 = 0   (  0);    9/-17 = -1   (   0);    -9/17 = -1   (   0);    -9/-17 = 0   (  0)
  9/23 = 0   (  0);    9/-23 = -1   (   0);    -9/23 = -1   (   0);    -9/-23 = 0   (  0)

 23/1  = 23  ( 23);   23/-1  = -23  ( -23);   -23/1  = -23  ( -23);   -23/-1  = 23  ( 23)
 23/2  = 11  ( 11);   23/-2  = -12  ( -11);   -23/2  = -12  ( -11);   -23/-2  = 11  ( 11)
 23/3  = 7   (  7);   23/-3  = -8   (  -7);   -23/3  = -8   (  -7);   -23/-3  = 7   (  7)
 23/6  = 3   (  3);   23/-6  = -4   (  -3);   -23/6  = -4   (  -3);   -23/-6  = 3   (  3)
 23/17 = 1   (  1);   23/-17 = -2   (  -1);   -23/17 = -2   (  -1);   -23/-17 = 1   (  1)
 23/23 = 1   (  1);   23/-23 = -1   (  -1);   -23/23 = -1   (  -1);   -23/-23 = 1   (  1)

291/1  = 291 (291);  291/-1  = -291 (-291);  -291/1  = -291 (-291);  -291/-1  = 291 (291)
291/2  = 145 (145);  291/-2  = -146 (-145);  -291/2  = -146 (-145);  -291/-2  = 145 (145)
291/3  = 97  ( 97);  291/-3  = -97  ( -97);  -291/3  = -97  ( -97);  -291/-3  = 97  ( 97)
291/6  = 48  ( 48);  291/-6  = -49  ( -48);  -291/6  = -49  ( -48);  -291/-6  = 48  ( 48)
291/17 = 17  ( 17);  291/-17 = -18  ( -17);  -291/17 = -18  ( -17);  -291/-17 = 17  ( 17)
291/23 = 12  ( 12);  291/-23 = -13  ( -12);  -291/23 = -13  ( -12);  -291/-23 = 12  ( 12)