Integer ceiling divide

ncoghlan · May 10, 2025, 5:51am

It’s one of those tricky topics where on its own the answer to “Should we group the existing discrete arithmetic functions into a new dedicated standard library module?” is fairly obviously “No, it’s too much work for not enough practical benefit” (thus making a standalone discussion very short).

However, at some point, some proposal is going to have to hit the threshold of “OK, this is getting silly, we need a dedicated place to access and document these, separate from math and the builtin namespace”. Until then, we’re going to have the “math isn’t the right place, but it’s the best option we have readily available” discussion each time.

I guess a dedicated thread would at least provide a place to summarise the full list of relevant APIs that already exist in the stdlib (using @madeleineth’s list in Integer ceiling divide - #13 by madeleineth as a starting point).

madeleineth · May 10, 2025, 6:20am

As a datapoint on my claim that codebases tend to end up with multiple copies of the function, I found three variations in cpython (2/3 on the C side), two of them confusing enough that the authors felt the need to comment what the expression meant.

github.com/python/cpython

Lib/fractions.py

832058274


      
              else:
                  return a._numerator // a._denominator
          
          def __floor__(a):
              """math.floor(a)"""
              return a._numerator // a._denominator
          
          def __ceil__(a):
              """math.ceil(a)"""
              # The negations cleverly convince floordiv to return the ceiling.
              return -(-a._numerator // a._denominator)
          
          def __round__(self, ndigits=None):
              """round(self, ndigits)
          
              Rounds half toward even.
              """
              if ndigits is None:
                  d = self._denominator
                  floor, remainder = divmod(self._numerator, d)
                  if remainder * 2 < d:

github.com/python/cpython

Python/pytime.c

832058274


      
          {
              return pytime_from_double(result, seconds, round, SEC_TO_NS);
          }
          
          
          static PyTime_t
          pytime_divide_round_up(const PyTime_t t, const PyTime_t k)
          {
              assert(k > 1);
              if (t >= 0) {
                  // Don't use (t + k - 1) / k to avoid integer overflow
                  // if t is equal to PyTime_MAX
                  PyTime_t q = t / k;
                  if (t % k) {
                      q += 1;
                  }
                  return q;
              }
              else {
                  // Don't use (t - (k - 1)) / k to avoid integer overflow
                  // if t is equals to PyTime_MIN.

https://github.com/python/cpython/blob/832058274dd99e30321a5f9a3773038cd0424c11/Include/internal/mimalloc/mimalloc/internal.h#L320

oscarbenjamin · May 10, 2025, 11:36am

Sorry I should have been more explicit. There is a thread right now that is discussing exactly this:

Concrete suggestions about the proposed module name would make more sense in that thread rather than this one.

storchaka · May 12, 2025, 2:52pm

If ceildiv() is added to stdlib, we should add also a function for division with rounding to the nearest integer (like _pydatetime._divide_and_round() or _PyLong_DivmodNear()). It may be useful in more cases than rounding up.

The initial gcd() implementation was in the fractions module. It contains also an implementation for division with rounding to the nearest integer, but not as a public function.

Dutcho · November 11, 2025, 9:47pm

Now that math.integer will be implemented in Python 3.15, perhaps we can continue this thread.

Question:
If mod() gives the remainder of floordiv(), should we consider ceilmod() for the spares of ceildiv()? I.e. for the ‘x objects and containers size y’ of OP, ceildiv(x, y) gives the number of containers and ceilmod(x, y) tells how many empty slots remain.

def ceildiv(m, n): return -(m // -n)
def ceilmod(m, n): return -(m % -n)
for m in tests:
  for n in tests:
    assert n == 0 or ceildiv(m, n) * n - ceilmod(m, n) == m, "new invariant"
    assert n == 0 or floordiv(m, n) * n + mod(m, n) == m, "regular invariant"

Orthogonality would suggest so, but this path risks growth with ceildivmod(), roundmod(), and rounddivmod().

Dutcho · November 11, 2025, 10:23pm

OTOH, Java has math.ceilMod() with an opposite sign:

def ceildiv(m, n): return -(m // -n)
def ceilmod(m, n): return (m % -n)
for m in tests:
  for n in tests:
    assert n == 0 or ceildiv(m, n) * n + ceilmod(m, n) == m, "same invariant as floor"
    assert n == 0 or floordiv(m, n) * n + mod(m, n) == m, "regular invariant"

To avoid confusion, following this definition seems advisable (even if positive operands then give negative outcomes).