Ceil division with math.ceildiv

[VladimirFeinberg]

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']

[VladimirFeinberg]

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.

[serhiy-storchaka]

See also bpo-31978.

[mdickinson]

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?

[VladimirFeinberg]

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.

1. 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.
2. 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.
3. 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\>

---

[tim-one]

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.

[mdickinson]

[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.

[tim-one]

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 :-)

[stevendaprano]

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 :-)

[mdickinson]

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?)