Fast ceiling of an integer division in C C

Question

Given integer values x and y  C and C   both return as the quotient q   x y the floor of the floating point equivalent   I m interested in a method of returning the ceiling instead   For example  ceil 10 5  2 and ceil 11 5  3   The obvious approach involves something like   q   x   y  if  q   y  lt  x    q    This requires an extra comparison and multiplication  and other methods I ve seen  used in fact  involve casting as a float or double   Is there a more direct method that avoids the additional multiplication  or a second division  and branch  and that also avoids casting as a floating point number

User · Answer

How about this   requires y non-negative  so don t use this in the rare case where y is a variable with no non-negativity guarantee   q    x  gt  0   1    x - 1  y   x   y     I reduced y y to one  eliminating the term x   y - 1 and with it any chance of overflow   I avoid x - 1 wrapping around when x is an unsigned type and contains zero   For signed x  negative and zero still combine into a single case   Probably not a huge benefit on a modern general-purpose CPU  but this would be far faster in an embedded system than any of the other correct answers

User · Answer

I would have rather commented but I don t have a high enough rep   As far as I am aware  for positive arguments and a divisor which is a power of 2  this is the fastest way  tested in CUDA      example y 8 q    x  gt  gt  3       x  amp  7     For generic positive arguments only  I tend to do it like so   q   x y      x   y

User · Answer

Sparky s answer is one standard way to solve this problem  but as I also wrote in my comment  you run the risk of overflows  This can be solved by using a wider type  but what if you want to divide long longs   Nathan Ernst s answer provides one solution  but it involves a function call  a variable declaration and a conditional  which makes it no shorter than the OPs code and probably even slower  because it is harder to optimize   My solution is this   q    x   y    x   y   1   x   y    It will be slightly faster than the OPs code  because the modulo and the division is performed using the same instruction on the processor  because the compiler can see that they are equivalent  At least gcc 4 4 1  performs this optimization with -O2 flag on x86   In theory the compiler might inline the function call in Nathan Ernst s code and emit the same thing  but gcc didn t do that when I tested it  This might be because it would tie the compiled code to a single version of the standard library   As a final note  none of this matters on a modern machine  except if you are in an extremely tight loop and all your data is in registers or the L1-cache  Otherwise all of these solutions will be equally fast  except for possibly Nathan Ernst s  which might be significantly slower if the function has to be fetched from main memory

User · Answer

For positive numbers  unsigned int x  y  q    To round up      q    x   y - 1    y    or  avoiding overflow in x y   q   1     x - 1    y      if x    0

User · Answer

This works for positive or negative numbers   q   x   y     x   y    0       x  gt  0     y  gt  0     0     If there is a remainder  checks to see if x and y are of the same sign and adds 1 accordingly

User · Answer

Compile with O3  The compiler performs optimization well   q   x   y  if  x   y     q

User · Answer

simplified generic form    int div up int n  int d        return n   d      n  lt  0     d  gt  0    amp  amp   n   d        i e   1 iff  not exact int  amp  amp  positive result    For a more generic answer  C   functions for integer division with well defined rounding strategy

User · Answer

You could use the div function in cstdlib to get the quotient  amp  remainder in a single call and then handle the ceiling separately  like in the below   include  lt cstdlib gt   include  lt iostream gt   int div ceil int numerator  int denominator            std  div t res   std  div numerator  denominator           return res rem    res quot   1    res quot     int main int  const char              std  cout  lt  lt   10   5      lt  lt  div ceil 10  5   lt  lt  std  endl          std  cout  lt  lt   11   5      lt  lt  div ceil 11  5   lt  lt  std  endl           return 0

User · Answer

There s a solution for both positive and negative x but only for positive y with just 1 division and without branches   int ceil int x  int y        return x   y    x   y  gt  0       Note  if x is positive then division is towards zero  and we should add 1 if reminder is not zero   If x is negative then division is towards zero  that s what we need  and we will not add anything because x   y is not positive

User · Answer

For positive numbers       q   x y    x   y    0

[c++] Fast ceiling of an integer division in C / C++

Examples related to c++

Examples related to c

Examples related to algorithm

Examples related to math