[issue46639] Ceil division with math.ceildiv

[Serhiy Storchaka]

Serhiy Storchaka  added the comment:

Round division would be useful not less than ceil division, if not more. In the 
stdlib it would be used in:

1. The datetime module.
2. Fraction.__round__.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue46639] Ceil division with math.ceildiv

[Tim Peters]

Tim Peters  added the comment:

The `decimal` module intends to be a faithful implementation of external 
standards. The identity

x == (x // y) * y + x % y

isn't a minor detail, it's the dog on which all else is but a tail ;-)

It's why Guido picked -7 // 4 = -2 in Python[1]. That's really not all that 
useful on its own, and does surprise people. But it's necessary so that the 
identity implies -7 % 4 = 1, and _that's_ what drove it all, the desire that 
doing mod wrt a positive int always give a non-negative result.

The identity also implies that, under truncating division, mod returns a result 
with the sign of the dividend rather than of the divisor.

`decimal` implements what the external standards demand integer division do, 
and also integer modulus. The decimal context `divmod()` method returns both at 
once.

The behavior of int div and mod are linked by all standards I'm aware of, 
including by C89 (which didn't define what integer division did in all cases, 
but did demand that - whatever it did - % had to work in a way consistent with 
the named identity).

[1] 
http://python-history.blogspot.com/2010/08/why-pythons-integer-division-floors.html

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue46639] Ceil division with math.ceildiv

[Steven D'Aprano]

Steven D'Aprano  added the comment:

Decimal is a good question.

Why does floor division not do floor division on Decimal? The 
documentation says

The integer division operator // behaves analogously, returning the 
integer part of the true quotient (truncating towards zero) rather 
than its floor, so as to preserve the usual identity 
x == (x // y) * y + x % y

but it's not clear why that identity is more important than floor 
division returning the floor.

I guess we could just document the difference and maybe add a 
Decimal ceildiv method, although that makes me sad :-(

Could we "fix" Decimal?

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue46639] Ceil division with math.ceildiv

[Mark Dickinson]

Mark Dickinson  added the comment:

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

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue46639] Ceil division with math.ceildiv

[Steven D'Aprano]

Steven D'Aprano  added the comment:

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

--
nosy: +steven.daprano

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue46639] Ceil division with math.ceildiv

[Tim Peters]

Tim Peters  added the comment:

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

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue46639] Ceil division with math.ceildiv

[Mark Dickinson]

Mark Dickinson  added the comment:

[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 
10**6, you're safe for all y <= 10**10. (Or vice versa: if you know the 
quotient is at most 10**10, then you're safe for y <= 10**6.)

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

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue46639] Ceil division with math.ceildiv

[Tim Peters]

Tim Peters  added the comment:

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.

--
nosy: +tim.peters

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue46639] Ceil division with math.ceildiv

[Vladimir Feinberg]

Vladimir Feinberg  added the comment:

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) ,
rounddiv (25)
, roundmod
(7) , ceilrem
(0) ,
ceildivrem
(0) .

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
 path. `math`
seems most apt.

On Sat, Feb 5, 2022 at 8:31 AM Mark Dickinson 
wrote:

>
> Mark Dickinson  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 
> 
> ___
>

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue46639] Ceil division with math.ceildiv

[Mark Dickinson]

Mark Dickinson  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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue46639] Ceil division with math.ceildiv

[Serhiy Storchaka]

Serhiy Storchaka  added the comment:

See also issue31978.

--
nosy: +serhiy.storchaka

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue46639] Ceil division with math.ceildiv

[Gregory P. Smith]

Change by Gregory P. Smith :


--
nosy: +mark.dickinson

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue46639] Ceil division with math.ceildiv

[Nathaniel Manista]

Change by Nathaniel Manista :


--
nosy: +Nathaniel Manista

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue46639] Ceil division with math.ceildiv

[Vladimir Feinberg]

New submission from Vladimir Feinberg :

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 `ceildiv`s might result in bugs or unclear 
handling of negatives.

--
components: Library (Lib)
messages: 412527
nosy: Vladimir Feinberg
priority: normal
severity: normal
status: open
title: Ceil division with math.ceildiv
type: enhancement
versions: Python 3.11

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com