Integer ceiling divide (original) (raw)

I would like python to have integer-ceiling-divide. The usual expression is -(x // -y), with similar semantics to // except rounding up instead of down.

It is generally used to answer the question “I have x objects and containers of size y. How many containers do I need?” Because of this, it would be somewhat less error-prone if it were ArithmeticError for x to be anything but a nonnegative integer, or y to be anything but a positive integer. But in practice errors like that are rare, so for symmetry and simplicity it would probably be appropriate to exactly match the semantics of // except with the opposite rounding direction.

math.cdiv would be a good name, to match triton.language.cdiv.

The real question is, why can’t people just type -(x // -y) or (x+y-1)//y? The answer is, in every large python codebase (or C/C++ codebase for that matter) I have worked in that I can remember, there are numerous slightly-different often-buggy versions of this same function. People could just type -(x // -y) but in my experience they do not, and to be honest I am not 100% sure I got the first one right in this post and I only realized I’d screwed up the second one while typing this very sentence. I think the latter is correct now, for positive integers.

I am not aware of any other discussion topics or PEPs related to this. There was one offhand comment about it on a mailing list in 2018: Mailman 3 Re: [Python-ideas] Add the imath module - Python-ideas - python.org

jamestwebber (James Webber) May 8, 2025, 5:26pm 2

If you’re importing math, why not use math.ceil(x / y)?

NeilGirdhar (Neil Girdhar) May 8, 2025, 5:35pm 3

Seems reasonable to me, but I would go with a longer name that’s more obvious to readers.

tstefan (Stefan) May 8, 2025, 5:51pm 4

Because this would construct a float first, which has limited accuracy.

jamestwebber (James Webber) May 8, 2025, 6:07pm 5

Fair enough, although I suspect this is rarely a problem for the use-case described in the OP.

madeleineth (Madeleine Thompson) May 8, 2025, 6:53pm 6

As Stefan said, floating-point will also give the wrong result sometimes.

>>> cdiv = lambda x, y: -(-x // y)
>>> cdiv(2**60, 3)
384307168202282326
>>> import math
>>> math.ceil(2**60 / 3)
384307168202282304

But also it will confuse people reading the code, who will have to know the fiddly details of floating-point math to know under what circumstances it gives integer-exact answers.

To Neil’s comment about names, a longer name that would have precedent would be ceildiv, by analogy with operator.floordiv.

Rosuav (Chris Angelico) May 8, 2025, 8:38pm 7

The operator module specifically implements operators. It has floordiv because the double-slash operator exists.

The math module, on the other hand, is closely associated with floats, so it’s not an ideal fit for this either. But I can’t think of any better place for it, so +0.5 on putting it there.

tim.one (Tim Peters) May 8, 2025, 9:56pm 8

They’re not the same, and only the first is correct if y may be negative:

>>> x, y = 9, -4
>>> -(x // -y)
-2
>>> (x+y-1)//y
-1

The second way is very popular in C code, though, where the programmer knows (or just really hopes ) that y is positive. Another correct way:

def ceildiv(x, y):
    q, r = divmod(x, y)
    return q + (r != 0)

That’s akin to how CPython would implement it in C (unary minus on bigints can be arbitrarily expensive, which is why it’s generally a little faster to write it now as -(x // -y) instead of -(-x // y): same results, but x generally has larger magnitude than y, so it’s generally cheaper to do -y than -x).

I agree it would be good to add this. Unfortunately, as the old thread you uncovered said, the math module isn’t a good home for integer functions (e.g., it’s a poor home for isqrt(), comb(), and gcd() too). But there’s no better place for it now.

+1 for ceildiv, -1 for cdiv. If there were an imath module, I could live with imath.cdiv, but in the math module–whose focus is floats–a lone c isn’t much of a clue.

skirpichev (Sergey B Kirpichev) May 9, 2025, 5:24am 9

What about other rounding modes?

How about the ntheory? (Inspired by submodule name in the diofant/sympy.)

We have isqrt(), how about idiv() with round kwarg?

(BTW, gmpy2 now has a set of integer functions t_div(), c_div() and f_div().)

tim.one (Tim Peters) May 9, 2025, 5:42am 10

I’d much rather follow gmpy2 here than add an annoying keyword argument to a do-everything wrapper function . Internally the implementation would pass a rounding-mode argument to a common routine, but an end user wants the single function they want.

“imath”, “ntheory”, don’t much care what it’s called, just so there’s some place to put our growing collection of integer functions outside of the increasingly conceptually incoherent math module.

hprodh (hprodh) May 9, 2025, 1:15pm 11

Maybe not…
Idk what the “typical end user” would prefer but what I would rather like is actually the other way around

math.div(a, b, integer=True, round='up')

… and this for one sole reason : if I need that function once, I don’t want to open a web browser, use a search engine, etc… I would use the interactive introspection of a modern IDE. First I think I need division so I type math.div( intuitively and the interactive object inspector automatically shows the available options, and if they are explicit enough, I can complete the task without interrupting my workflow. I am still free to use c_div = lambda ... if I need a shortcut, and this way implicitness (thus confusability) is reduced to a bare minimum.

tim.one (Tim Peters) May 9, 2025, 6:03pm 12

Where I wouldn’t think “I want division”, but “I want ceiling int division”, and my IDE’s auto-complete would quickly figure out the rest after I type the “math.c” part. “Ah, yes. math.ceildiv is the name I was looking for”. Even easier in an imath module, which wouldn’t contain integer-irrelevant functions like cos, cosh, copysign, and ceil too.

The catch-all interface you propose looks like a near-bottomless pit on its own. interger=True? You want this to work for, e.g, floats and decimals too? You want people to remember the names of rounding modes? “up” is confusable on its own: “to plus infinity” (“ceiling”) is one possible meaning, but “away from zero” is another (which is actually what decimal.ROUND_UP means), decimal has 8 rounding modes, BTW. Does anyone ever want, e.g nearest/even rounding for int division? And so on.

The only thing the OP is asking for is integer ceiling division, and I’m sticking to that, although truncating (“round to 0”) int division has also come up (gmpy2’s t_div()), bur not as often as ceiling.

madeleineth (Madeleine Thompson) May 9, 2025, 6:56pm 13

math.div(a, b, integer=True, round='up') is verbose enough that the practice of writing wrappers would not end; my purpose in suggesting this is to eliminate duplicative, inconsistent wrappers.

For completeness, the division variants I have personally seen in use, not counting specialized numerical libraries, are the one called / in python, the one called // in python, the integer-ceiling-division one we are discussing here, and “exact integer division”:

def exact_integer_divide(x, y):
    q, r = divmod(x, y)
    if r:
        raise ArithmeticError(f"Inexact division: {x} % {y} = {r}")
    return q

I’m less enthusiastic about adding that to the standard library.

After seeing the discussion above, I’m convinced on the math.ceildiv name. The two places I’m aware of in the python standard library with conceptually-related functions are math (gcd, isqrt, lcm) and built-ins (divmod, max, sum, etc.). And I don’t think crowding the global namespace is a good idea.

I think it’s okay for this not to be in the standard library. Not to say it isn’t useful, but we have a rich 3rd party ecosystem for numerical tasks already, already have a way to do this in the decimal module, and it’s also simple to write yourself (either inline, or as a reused helper)

oscarbenjamin (Oscar Benjamin) May 9, 2025, 7:13pm 15

I don’t think I’ve ever used ceiling divide but exact division is useful. SymPy calls it exquo and gmpy2 calls it divexact but even these two have different behaviour:

>>> from sympy import ZZ
>>> ZZ.exquo(4, 2)
2
>>> ZZ.exquo(4, 3)
...
ExactQuotientFailed: 3 does not divide 4 in ZZ 
>>> import gmpy2
>>> gmpy2.divexact(4, 2)
mpz(2)
>>> gmpy2.divexact(4, 3)
mpz(12297829382473034412)

I guess gmpy2’s version is garbage in garbage out but it is presumably more efficient for large integers than something that checks if the result is valid.

tim.one (Tim Peters) May 9, 2025, 7:41pm 16

Much more efficient, yes. Sketch: If you know the remainder is 0. then shift x & y right so long as y’s last bit is clear. Then y is odd. So y has a modular inverse modulo 2**k (for whatever k you like). That inverse can be computed efficiently, without any division, but I’ll skip the details (it’s a quadratically convergent integer method with increasing precision across iterations, and you can start with that every odd int is its own inverse mod 8) Then a single modular multiply of that and x finishes the job.

Note the output from this:

>>> pow(3, -1, 2**63) * 4
12297829382473034412

You may have seen that number before .

gmpy2’s goal with divexact is purely speed, and that the remainder is 0 is an unchecked precondition. sympy’s goal with exquo is very different.

oscarbenjamin (Oscar Benjamin) May 9, 2025, 9:50pm 17

I’m not sure the goal is different but it isn’t actually written down anywhere. The practical use for exquo and divexact is to support a whole class of algorithms that are fraction-free (not the same as division-free) that use only exact division e.g. the Bareiss algorithm. These functions are only supposed to be used when you have a priori knowledge that the division is exact and the function has permission to make use of that information if possible. Getting an exception if that turns out to be false is useful but is not the purpose of these functions (much like an assert).

The generic implementation of exquo in SymPy uses divmod and by default ZZ uses only the stdlib which does not provide divexact. SymPy can also use gmpy2 as the backend for ZZ though and in that situation I would consider it valid for ZZ.exquo to be an alias for gmpy2.divexact (although this is not done currently).

tim.one (Tim Peters) May 9, 2025, 11:16pm 18

This is getting way off topic, and we’re not going to agree anyway .

The SymPy docs promise to raise

ExactQuotientFailed: if exact division is not possible.

That’s the purpose of exquo, in service of supplying a form of division that doesn’t leave the “domain” of the inputs, which domain may well be a non-field ring, but nevertheless support exact division for specific pairs of domain elements.

Contrast, e.g., with Python ints, which convert both inputs to a containing field (floats) before division. and returns an element of that field, regardless of whether the exact result is representable in the ring of ints.

GMP doesn’t care about any of that. It has in mind only speeding algorithms where it’s known in advance that integer quotients are exact integers.

Then it would have to add additional checks of its own, to fulfill the docs’ promise to raise ExactQuotientFailed when exact division isn’t psssible.

ncoghlan (Alyssa Coghlan) May 10, 2025, 12:34am 19

I don’t have a strong opinion on whether ceildiv is sufficiently common to be worth adding to the standard library, but wanted to point out that imath would look like a module for working with imaginary numbers as much or moreso than one for working with integers.

intmath could work as a less ambiguous alternative, though (if we did decide to separate the standard library’s discrete arithmetic support from the floating point support in math).

oscarbenjamin (Oscar Benjamin) May 10, 2025, 12:45am 20

This is not the thread for that proposal although the discussion overlaps.