Ceil division with math.ceildiv

@tim-one

BPO	46639
Nosy	@tim-one, @mdickinson, @stevendaprano, @serhiy-storchaka, @nathanielmanistaatgoogle

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = None
created_at = <Date 2022-02-04.19:25:23.669>
labels = ['type-feature', 'library', '3.11']
title = 'Ceil division with math.ceildiv'
updated_at = <Date 2022-02-08.07:28:32.645>
user = 'https://bugs.python.org/VladimirFeinberg'

bugs.python.org fields:

activity = <Date 2022-02-08.07:28:32.645>
actor = 'serhiy.storchaka'
assignee = 'none'
closed = False
closed_date = None
closer = None
components = ['Library (Lib)']
creation = <Date 2022-02-04.19:25:23.669>
creator = 'Vladimir Feinberg'
dependencies = []
files = []
hgrepos = []
issue_num = 46639
keywords = []
message_count = 12.0
messages = ['412527', '412541', '412580', '412583', '412590', '412593', '412594', '412751', '412780', '412803', '412814', '412815']
nosy_count = 6.0
nosy_names = ['tim.peters', 'mark.dickinson', 'steven.daprano', 'serhiy.storchaka', 'Nathaniel Manista', 'Vladimir Feinberg']
pr_nums = []
priority = 'normal'
resolution = None
stage = None
status = 'open'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue46639'
versions = ['Python 3.11']

I have a request related to the rejected proposal (https://bugs.python.org/issue43255) to introduce a ceildiv operator.

I frequently find myself wishing for a ceildiv function which computes ceil(x/y) for integers x,y. This comes up all the time when "batching" some resource and finding total consumption, be it for memory allocation or GUI manipulation or time bucketing or whatnot.

It is easy enough to implement this inline, but math.ceildiv would express intent clearly.

# x, y, out: int

# (A)
import math
out = math.ceil(x / y)  # clear intent but subtly changes type, and also incorrect for big ints

# (B)
out = int(math.ceil(x / y))  # wordy, especially if using this multiple times, still technically wrong

# (C)
out = (x + y - 1) // y  # too clever if you haven't seen it before, does it have desirable semantics for negatives?

# (D)
out = -(-x//y) 

def ceildiv(a: int, b: int) -> int:  # Clearest and correct, but should my library code really invent this wheel? 
  """Returns ceil(a/b)."""
  return -(-x//y)

out = ceildiv(x, y)

Even though these are all "one-liners", as you can see leaving people to complex manually-implemented ceildivs might result in bugs or unclear handling of negatives.

See also bpo-31978.

I'm not convinced that this deserves to be a math module function. I agree that -(-x // y), while simple to write, isn't necessarily obvious. But it does have some advantages, like not needing an import, and being naturally duck-typed, so that it automatically does the right thing for floats, or fractions.Fraction objects, or numpy.int64 objects, or SymPy integers. (Not for Decimal instances, but that's another story.) Unless we were to add a whole ceildiv mechanism, a math module implementation would necessarily be limited to integers. (Or perhaps integers and floats.)

There's also the "thin end of the wedge" argument: if ceildiv, why not also ceilrem, ceildivrem, rounddiv, roundmod, etc.

The main issue with the -(-x // y) spelling seems to be discoverability: if everyone knew that this was the right way to spell ceiling division, then there wouldn't be a problem. And I'm not convinced that a math.ceildiv function would necessarily solve the discoverability problem, either.

So maybe the solution is to advertise the -(-x // y) pattern better in documentation, for example at the point where floor division is introduced in the library reference?

Mark, I will say I'm pretty sympathetic to the feature-bloat avoidance
perspective here, and if the outcome here is to improve docs, that's still
a win, I think.

That said, since this thread will become precedent, and I think
math.ceildiv is the exactly-appropriate amount of commitment Lib should
make to the function (not ceildiv and not "just" a doc note), let me
try to give ceildiv the strongest legs I can think of before we make a
decision.

Not needing an import - I don't find importing such a standard library
as math that onerous. We're not adding a new package here, just a
function. This skepticism could be applied to any existing library
function. Even sys.stdout needs an import.
Natural duck typing - I'll admit, this is pretty nice. But if that's the
argument, I'd expect this to work to its fullest extent. Namely, I'd expect
this to "naturally" work for any ring, and it doesn't. Z/nZ is a common one
and np.uint is a more common one where the identity -(-x // y) = ceildiv(x,
y) does not hold. The benefit of math.ceildiv is it'd either support it,
or say it doesn't, but at least it's explicit.
Thin end of wedge - A priori, I would put ceildiv as special because of
the "resource coverage" use case I described in my initial bug message. A
posteriori, there's a clear "kink" in the graph of usage here: ceildiv
(3033) https://github.com/search?l=&q=ceildiv+language%3APython&type=code,
rounddiv (25)
https://github.com/search?q=rounddiv+language%3APython&type=code, roundmod
(7) https://github.com/search?q=roundmod+language%3APython&type=code, ceilrem
(0) https://github.com/search?q=ceilrem+language%3APython&type=code,
ceildivrem
(0) https://github.com/search?q=ceildivrem+language%3APython&type=code.

But most importantly, let me detail what motivated me to post this. I was
working on unit tests for linear algebra code which blocked its operations.
But to not involve a lot of context, I'll provide a similarly-structured
use case. Say we're making a controller for a game engine GUI and need to
figure out how to paint sprites.

# sprite_A.py
class A:
  def get_covering_rectangle():
    return self.x, self.y, self.x - (-self.width // GRID_WIDTH), self.y -
(-self.height // GRID_HEIGHT)

Especially if I also use -(-x//y) elsewhere, this is just asking too much
of the reader. I could leave a comment to the tune of # Note below is equivalent to + (-(-x//y)), the ceildiv operator, and this works because x isn't a uint. Should I do this at all usage sites? I'd end up factoring
into my own ceildiv for clarity, especially if I use this elsewhere, like
a test.

Where should this hand-rolled ceildiv live, if not recreated in everyone's
code? It seems too light to wrap as its own dependency, and we probably
don't want to go down the leftpad
https://www.theregister.com/2016/03/23/npm_left_pad_chaos/ path. math
seems most apt.

On Sat, Feb 5, 2022 at 8:31 AM Mark Dickinson <report@bugs.python.org>
wrote:

Mark Dickinson dickinsm@gmail.com added the comment:

I'm not convinced that this deserves to be a math module function. I agree
that -(-x // y), while simple to write, isn't necessarily obvious. But it
does have some advantages, like not needing an import, and being naturally
duck-typed, so that it automatically does the right thing for floats, or
fractions.Fraction objects, or numpy.int64 objects, or SymPy integers.
(Not for Decimal instances, but that's another story.) Unless we were to
add a whole ceildiv mechanism, a math module implementation would
necessarily be limited to integers. (Or perhaps integers and floats.)

There's also the "thin end of the wedge" argument: if ceildiv, why not
also ceilrem, ceildivrem, rounddiv, roundmod, etc.

The main issue with the -(-x // y) spelling seems to be discoverability:
if everyone knew that this was the right way to spell ceiling division,
then there wouldn't be a problem. And I'm not convinced that a math.ceildiv
function would necessarily solve the discoverability problem, either.

So maybe the solution is to advertise the -(-x // y) pattern better in
documentation, for example at the point where floor division is introduced
in the library reference?

----------

Python tracker <report@bugs.python.org>
<https://bugs.python.org/issue46639\>

GMP's mpz has 18 functions of this form. These are the 6 "ceiling" flavors:

c_divmod
c_div
c_mod

c_divmod_2exp
c_div_2exp
c_mod_2exp

The suggestion here is for c_div.

There are 6 more for floor rounding (with prefix "f_" instead of "c_"), and another 6 for truncation ("to-zero" rounding, with prefix "t_"). Curiously enough, there's no direct support for any form of "round to nearest".

So that's where this ends ;-)

I personally almost never use -(-x // y). Because it's a bit obscure, and in real life y is always known to be positive, so the nearly obvious (x + y - 1) // y works fine.

[Tim]

Because it's a bit obscure, and in real life y is always known to be positive, so the nearly obvious (x + y - 1) // y works fine.

Whereas I find (x + y - 1) // y less obvious at first sight than -(-x // y). :-) I don't care about negative y - that's not my reason for preferring -(-x // y). The preference comes from the fact that -(-x // y) still does the right thing for non-integral cases.

[Vladimir]

Say we're making a controller for a game engine GUI and need to
figure out how to paint sprites. [...]

For this example, I'd probably just use ceil(x / y). For "real world" things with x and y representing counts of something tangible (pixels, work items, row or column count of a matrix, lines of text, bytes of memory used, ...), you have to go quite a long way before ceil(x / y) gives you the wrong answer due to floating-point errors. E.g. if you know the quotient is no larger than 106, you're safe for all y <= 1010. (Or vice versa: if you know the quotient is at most 1010, then you're safe for y <= 106.)

not __ceildiv__ [...]

It would be a little odd (but only a little) to have __floor__, __ceil__, and __floordiv__ overloads, but not __ceildiv__. It probably wouldn't be long before someone requested it.

I'll quieten down now and wait to see what other people think.

I expect "obviousness" is mostly driven by background here. You know, e.g., that ceil(x) = -floor(-x) for any real x, and the application to integer division is just a special case of that. I expect programmers mostly don't know that, though. And Python having floor integer division is unusual among programming languages. Everyone coming from, say, C, has seen the (i + j - 1)/j "idiom" over and over, where "the usual" truncating integer division is the rule (and they know too that i and j are positive). Familiarity breeds "obviousness" too :-)

I don't understand why math.ceildiv couldn't ducktype. There's no rule that says it *must* convert arguments to float first, that's just a convention, and we've broken it before.

>>> math.prod([Fraction(1, 3), 7])
Fraction(7, 3)

Couldn't math.ceildiv(x, y) be implemented as -(-x//y) in a type-agnostic fashion?

Perhaps it is too late in the night for me, but I have no idea what ceilrem(x, y) would do or why anyone might want it.

I agree with Vladimir that the import thing is not an issue. If we can require an import for much more important functions as sin, cos, tan, log, etc, then requiring an import is not excessive for a function of secondary importance.

Feature-bloat: its taken 30 years for somebody to request ceildiv. At that rate, it will take another 500 years for us to catch up to mpz in terms of features/bloat. I'm not losing sleep over that :-)

Couldn't math.ceildiv(x, y) be implemented as -(-x//y) in a type-agnostic fashion?

Ah, good point. Yes, that could work.

We'd have to decide what to do about Decimal if we took this approach, since the -(-x//y) trick doesn't work there. (Document the issue? Try to make things work for Decimal?)

I'm going to close this here. Like every other design decision it's a trade-off. Both the benefit and the cost are small, but to my eyes the cost outweighs the benefits here.

@serhiy-storchaka

@serhiy-storchaka Is it worth re-opening/re-considering this issue now that there's a more obvious place to put a ceildiv function?

One wrinkle - in the place I most recently found myself wanting a ceildiv operation, I was actually working with datetime.timedelta objects rather than integers (or floats). That is, I was doing something along the lines of:

>>> import datetime
>>> video_length = datetime.timedelta(minutes=59)
>>> max_analysis_length = datetime.timedelta(minutes=10)
>>> analysis_count = -(video_length // -max_analysis_length)
>>> analysis_count
6

and I wanted to be able to spell that fourth line as analysis_count = ceildiv(video_length, max_analysis_length).

So if ceildiv got added to math.integer, would it break the math.integer module policy to have it accept timedelta objects as well as ints? What about accepting floats?

So if ceildiv got added to math.integer, would it break the math.integer module policy to have it accept timedelta objects as well as ints? What about accepting floats?

Maybe worth noting that other similarly type-generic functions (math.prod, math.sumprod) are still in math, not math.integer.

It is easier to implement ceildiv and friends only for integers (_PyLong_DivmodNear only supports integers), but it would be more convenient if they are general, applicable to floats, decimals, fractions. Should we add two variants -- integer-only and general?

And if add ceildiv, we need to add also variants with rounding to the nearest integer, to zero, to infinity, and corresponding divmod variants.

We have also to keep in mind that in future we may add the rounding option for isqrt() and for future ilog() or ilog2().

See also #139273. We may need more such complicated code if we want support high-precision timedelta.

The only thing that's actually been requested (& more than once) I've seen is ceildiv(int, int). Would it be possible to just start with that, to make some users happy, without making any progress for years on end due to hypothetical "purity" arguments? 😉.

Python just doesn't need GMP's 18 variations, but GMP is there if people want them. Real Python programmers do want what the OP of this report asked for. It's not at all uncommon in "number theory" work too - int ceiling division is a fundamental primitive.

Other types can follow later if there's real need demonstrated repeatedly. But it's a pit. For example, timedelta // timedelta returns an int now, but timedelta // int returns a timedelta, and timedelta // float raises TypeError.

If args aren't int, I'd be fine with falling back to the generic -(x // -y), but special-casing Decimal to raise TypeError instead (since decimal's implementation of __floordiv__ doesn't work for this, and better to refuse to pretend that whatever it does is fine).

I do not remember I even needed ceildiv (perhaps because this was easy to write in other way), but _divide_and_round is not so trivial.

If you only need integer operations -- I think that the bar to add new functions to math.integer is now lower.

Lets focus just on ceildiv and friends here. And reopen issue, indeed.

would it break the math.integer module policy to have it accept timedelta objects as well as ints?

Certainly yes.

What about accepting floats?

For floats, like Decimal's, maybe we have a better option? I.e. support contexts, that will expose FPE status flags and control modes.

And if add ceildiv, we need to add also variants with rounding to the nearest integer, to zero, to infinity, and corresponding divmod variants.
We have also to keep in mind that in future we may add the rounding option for isqrt()

If we are going to support different rounding modes for isqrt(), maybe we should do same for division, instead of bunch of gmpy2-like functions? (Though, for isqrt() I would rather prefer isqrt_rem() as a building block.)

It seems to me that for division - all three cases from the GMP do make sense (we have feature requests and/or code in the stdlib, which reinvent the wheel). But I'm not sure if we need something beyond the quotient, i.e. c_divmod(), t_mod() and so on. Note also, that MPFR/libmpdec have more rounding modes.

FYI: https://discuss.python.org/t/integer-ceiling-divide/91269

I'll close this issue in favor of #76159 (more old). Both asks for support of differently rounded division.

Navigation Menu

Repository navigation

Ceil division with math.ceildiv #90797

4 remaining items

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Ceil division with math.ceildiv #90797

Description

Activity

VladimirFeinberg commented on Feb 4, 2022

serhiy-storchaka commented on Feb 4, 2022

mdickinson commented on Feb 5, 2022

VladimirFeinberg commented on Feb 5, 2022

tim-one commented on Feb 5, 2022

mdickinson commented on Feb 5, 2022

tim-one commented on Feb 5, 2022

stevendaprano commented on Feb 7, 2022

mdickinson commented on Feb 7, 2022

4 remaining items

mdickinson commented on Apr 11, 2022

mdickinson commented on Nov 5, 2025

mdickinson commented on Nov 5, 2025

serhiy-storchaka commented on Nov 5, 2025

tim-one commented on Nov 5, 2025

serhiy-storchaka commented on Nov 5, 2025

skirpichev commented on Nov 5, 2025

skirpichev commented on May 8, 2026

skirpichev commented on May 31, 2026

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions