9

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

ideasman42
  • 42,413
  • 44
  • 197
  • 320
  • That depends on your compiler, target, optimisation setting, commpiler version, etc. – too honest for this site Sep 17 '17 at 15:15
  • 2
    Well, yes, of course *exact* optimizations depend on compiler version. Nevertheless, its common to ask about efficient C implementations of a function - eg, this is nearly the reverse of this question: https://stackoverflow.com/questions/2745074 – ideasman42 Sep 17 '17 at 15:18

5 Answers5

8

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));
}
0___________
  • 60,014
  • 4
  • 34
  • 74
5

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.105)

105) 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)
linux_pangolin
  • 61
  • 1
  • 7
Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
  • Thanks for the comprehensive answer and tests. However I was looking into this and found that with glibc at least, `div` isn't a builtin. While the answer is correct, I'm not sure I'd want to use it on performance critical code. see resulting asm: https://godbolt.org/g/9QmyFn – ideasman42 Sep 18 '17 at 02:47
3

Floored division can be performed by using a division and modulo.

There is no reason to avoid the modulo call since modern compilers optimize a divide & modulo into a single divide.

int floor_div(int a, int b) {
    int d = a / b;
    int r = a % b;  /* optimizes into single division. */
    return r ? (d - ((a < 0) ^ (b < 0))) : d;
}
ideasman42
  • 42,413
  • 44
  • 197
  • 320
1

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.

kevinjwz
  • 181
  • 6
0

Branchless version:

int floor_div(int x, int y)
{
    return x / y - (x % y != 0) * ((x < 0) ^ (y < 0));
}

https://godbolt.org/z/9n3637brs

I see that for other answers compiler generates conditional jumps and this means slower code.

Did some performance test and results are interesting:

Inspecting code generated by clang shows that clang was able to optimize away branches (ifs and ternary operator)

So this shows: measure firsts when optimizing :).

Marek R
  • 32,568
  • 6
  • 55
  • 140