• 13

A PHP Error was encountered

Severity: Notice

Message: Undefined index: userid

Filename: views/question.php

Line Number: 191


File: /home/prodcxja/public_html/questions/application/views/question.php
Line: 191
Function: _error_handler

File: /home/prodcxja/public_html/questions/application/controllers/Questions.php
Line: 433
Function: view

File: /home/prodcxja/public_html/questions/index.php
Line: 315
Function: require_once

I found out about the // operator in Python which in Python 3 does division with floor.

Is there an operator which divides with ceil instead? (I know about the / operator which in Python 3 does floating point division.)

    • You should change accepted answer to dlitz's. math.ceil is for floats, it does not work with Python's arbitrary-precision long ints.
    • @milllimoose The question is valid, because 1) "ceil division" is also based on "division with modulus", 2) math doesn't really say what's common and what isn't, 3) you need this operation for "continuous bin packing problem", i.e. how many boxes of size $k$ are neeeded to pack $n$ items.

You can just do upside-down floor division:

def ceildiv(a, b):
    return -(-a // b)

This works because Python's division operator does floor division (unlike in C, where integer division truncates the fractional part).

This also works with Python's big integers, because there's no (lossy) floating-point conversion.

Here's a demonstration:

>>> from __future__ import division   # a/b is float division
>>> from math import ceil
>>> b = 3
>>> for a in range(-7, 8):
...     print(["%d/%d" % (a, b), int(ceil(a / b)), -(-a // b)])
['-7/3', -2, -2]
['-6/3', -2, -2]
['-5/3', -1, -1]
['-4/3', -1, -1]
['-3/3', -1, -1]
['-2/3', 0, 0]
['-1/3', 0, 0]
['0/3', 0, 0]
['1/3', 1, 1]
['2/3', 1, 1]
['3/3', 1, 1]
['4/3', 2, 2]
['5/3', 2, 2]
['6/3', 2, 2]
['7/3', 3, 3]
  • 287
Reply Report
    • @apadana I disagree. The question asked whether there "is" an operator for this "in" Python. Based on the responses, the answer appears to be "no." I'm upvoting dlitz's answer for its usefulness, though.
      • 2
    • @SlimCheney Toss this method into a documented function and you're good to go. Performance + readability in one sweeping motion.
      • 1
    • @SamyBencherif: Not just performance + readability, but also correctness for large inputs; floating point has representation limitations, while Python's int does not (well, no meaningful ones; on 64 bit Python you're limited to 30 * (2**63 - 1) bit numbers), and even temporarily converting to float can lose information. Compare math.ceil((1 << 128) / 10) to -(-(1 << 128) // 10).
    • @apadana I agree this is very smart, but not very readable and hard to maintain! I have decided to import ceil from math so that when one of my colleagues reads my line of code he will understand what it does!

There is no operator which divides with ceil. You need to import math and use math.ceil

  • 55
Reply Report
    • so foobar = math.ceil(foo / bar)? Hmm, I can live with that, don't know of anywhere I wanted to use that, was just curious, thanks
    • definitely stay in the integer domain. that's almost guaranteed to be more performant and less of a headache.
      • 1
    • Note that math.ceil is limited to 53 bits of precision. If you are working with large integers, you may not get exact results.

You could do (x + (d-1)) // d when dividing x by d, i.e. (x + 4) // 5.

  • 26
Reply Report

Solution 1: Convert floor to ceiling with negation

def ceiling_division(n, d):
    return -(n // -d)

Reminiscent of the Penn & Teller levitation trick, this "turns the world upside down (with negation), uses plain floor division (where the ceiling and floor have been swapped), and then turns the world right-side up (with negation again)"

Solution 2: Let divmod() do the work

def ceiling_division(n, d):
    q, r = divmod(n, d)
    return q + bool(r)

The divmod() function gives (a // b, a % b) for integers (this may be less reliable with floats due to round-off error). The step with bool(r) adds one to the quotient whenever there is a non-zero remainder.

Solution 3: Adjust the numerator before the division

def ceiling_division(n, d):
    return (n + d - 1) // d

Translate the numerator upwards so that floor division rounds down to the intended ceiling. Note, this only works for integers.

Solution 4: Convert to floats to use math.ceil()

def ceiling_division(n, d):
    return math.ceil(n / d)

The math.ceil() code is easy to understand, but it converts from ints to floats and back. This isn't very fast and it may have rounding issues. Also, it relies on Python 3 semantics where "true division" produces a float and where the ceil() function returns an integer.

  • 20
Reply Report

You can always just do it inline as well

((foo - 1) // bar) + 1

In python3, this is just shy of an order of magnitude faster than forcing the float division and calling ceil(), provided you care about the speed. Which you shouldn't, unless you've proven through usage that you need to.

>>> timeit.timeit("((5 - 1) // 4) + 1", number = 100000000)
>>> timeit.timeit("ceil(5/4)", setup="from math import ceil", number = 100000000)
  • 19
Reply Report
      • 1
    • Because code clarity trumps all. Clarity is objective in this case probably. But you should always make readable/maintainable first. When, and only when, you've discovered a performance checkpoint, do you get to break the rules. Modern machines are so fast, and so often all of the other stuff your program is doing renders this kind of difference lost in the noise.
    • @TravisGriggs using integer math instead of floating point math isn't just for speed. For large enough integers float math gives the wrong answer
    • just ran those tests myself I get about 12.5 seconds, ehrm, why wouldn't I care about speed when it is such a huge speed difference?
      • 1
    • @Cradam Note that he's using doing 100 million calls (number=100000000). Per single call, the difference is pretty insignificant.

Note that math.ceil is limited to 53 bits of precision. If you are working with large integers, you may not get exact results.

The gmpy2 libary provides a c_div function which uses ceiling rounding.

Disclaimer: I maintain gmpy2.

  • 8
Reply Report
      • 1
    • This package would be useful if I was doing something heavily mathematics or science orientated, I prefer the answer which uses core libraries though. I am giving an upvote though as it is a useful answer
    • Wow, can confirm. python2 -c 'from math import ceil;assert ceil(11520000000000000102.9)==11520000000000000000' (as well as substituting python3) BOTH are True

Trending Tags