FAQ
I need to apply the ceiling function to arbitrary sized (long) integers.
However, division automatically returns the type of its operands, so that,
for example: math.ceil(7/4) returns 1. I can use float, as in:
math.ceil(7/float(4)), except that for very large integers float causes an
unacceptable loss of precision.

What is the best way of finding a ceiling of a quotient of arbitrary sized
integers?

Thanks,
Alasdair

From http Sun Mar 9 00:26:35 2008
From: http (Paul Rubin)
Date: 08 Mar 2008 15:26:35 -0800
Subject: Arbitrary precision integer arithmetic: ceiling?
References: <fqv6ih$jvd$1@news-01.bur.connect.com.au>
Message-ID: <7xhcfg94r8.fsf@ruckus.brouhaha.com>
Status: RO
Content-Length: 81972
Lines: 2301

Alasdair <amca01 at gmail.com> writes:
What is the best way of finding a ceiling of a quotient of arbitrary sized
integers?
ceiling(a/b) = (a+b-1)//b

Search Discussions

  • Robert Kern at Mar 8, 2008 at 11:31 pm

    Alasdair wrote:
    I need to apply the ceiling function to arbitrary sized (long) integers.
    However, division automatically returns the type of its operands, so that,
    for example: math.ceil(7/4) returns 1. I can use float, as in:
    math.ceil(7/float(4)), except that for very large integers float causes an
    unacceptable loss of precision.

    What is the best way of finding a ceiling of a quotient of arbitrary sized
    integers?
    Use divmod() to get the quotient and the remainder at the same time. Add 1 to
    the quotient if and only the remainder is greater than 0.


    In [11]: def qceil(x, y):
    ....: """ Find the ceiling of a quotient x/y.
    ....:
    ....: This is especially useful for very large Python long integers.
    ....: """
    ....: q, r = divmod(x, y)
    ....: if r > 0:
    ....: q += 1
    ....: return q
    ....:

    In [13]: qceil(7, 4)
    Out[13]: 2

    In [14]: qceil(8, 4)
    Out[14]: 2

    In [15]: qceil(9, 4)
    Out[15]: 3

    In [16]: qceil(100000000000000000000000003, 10)
    Out[16]: 10000000000000000000000001L

    --
    Robert Kern

    "I have come to believe that the whole world is an enigma, a harmless enigma
    that is made terrible by our own mad attempt to interpret it as though it had
    an underlying truth."
    -- Umberto Eco
  • Mark Dickinson at Mar 9, 2008 at 1:09 am

    On Mar 8, 6:26?pm, Paul Rubin wrote:
    Alasdair <amc... at gmail.com> writes:
    What is the best way of finding a ceiling of a quotient of arbitrary sized
    integers?
    ceiling(a/b) = (a+b-1)//b
    I prefer:

    ceiling(a/b) = -(-a)//b

    which also works if a and b are something other
    than integers (e.g. rational numbers).

    Mark
  • Steven D'Aprano at Mar 9, 2008 at 1:48 am

    On Sat, 08 Mar 2008 17:09:11 -0800, Mark Dickinson wrote:
    On Mar 8, 6:26?pm, Paul Rubin wrote:
    Alasdair <amc... at gmail.com> writes:
    What is the best way of finding a ceiling of a quotient of arbitrary
    sized integers?
    ceiling(a/b) = (a+b-1)//b
    I prefer:

    ceiling(a/b) = -(-a)//b

    which also works if a and b are something other than integers (e.g.
    rational numbers).

    Unfortunately it doesn't give the right answer.
    a, b = 101.0, 10.0
    -(-a)//b # should be 11.0
    10.0
    a, b = -101.0, 10.0
    -(-a)//b # should be -10.0
    -11.0

    Looks like you've confused ceiling() and floor().

    (And the ease that these mistakes can happen is why such fundamental
    functions should be in the standard library, no matter how easy they are
    to implement.)


    --
    Steven
  • Mark Dickinson at Mar 9, 2008 at 2:11 am

    On Mar 8, 8:48?pm, Steven D'Aprano <st... at REMOVE-THIS- cybersource.com.au> wrote:
    On Sat, 08 Mar 2008 17:09:11 -0800, Mark Dickinson wrote:
    I prefer:
    ceiling(a/b) = -(-a)//b
    Unfortunately it doesn't give the right answer.
    a, b = 101.0, 10.0
    -(-a)//b ?# should be 11.0
    10.0
    a, b = -101.0, 10.0
    -(-a)//b ?# should be -10.0
    -11.0

    Looks like you've confused ceiling() and floor().
    Whoops, you're right. No, I didn't confuse ceiling and floor;
    I misplaced the parentheses. I meant to type:

    ceiling(a/b) = -(-a//b)

    Mark
  • Terry Reedy at Mar 9, 2008 at 2:19 am
    "Steven D'Aprano" <steve at REMOVE-THIS-cybersource.com.au> wrote in message
    news:13t6gf5on1qnhbe at corp.supernews.com...
    On Sat, 08 Mar 2008 17:09:11 -0800, Mark Dickinson wrote:
    On Mar 8, 6:26 pm, Paul Rubin wrote:
    Alasdair <amc... at gmail.com> writes:
    What is the best way of finding a ceiling of a quotient of arbitrary
    sized integers?
    ceiling(a/b) = (a+b-1)//b
    I prefer:

    ceiling(a/b) = -(-a)//b
    Obvious typo: -(-a)//b == a//b

    This should be -(-a//b) == -((-a)//b)
    Unfortunately it doesn't give the right answer.
    Looks like you've confused ceiling() and floor().

    (And the ease that these mistakes can happen is why such fundamental
    functions should be in the standard library, no matter how easy they are
    to implement.)
    I'll let Paul say whether is was a typo, due to answering too quickly, or a
    logic error, but I suspect the former. *Any* expression can be mistyped.

    tjr
  • Mark Dickinson at Mar 9, 2008 at 2:27 am

    On Mar 8, 9:19?pm, "Terry Reedy" wrote:
    Obvious typo: -(-a)//b == a//b

    This should be -(-a//b) == -((-a)//b)
    Yes: thanks for the correction!

    A lesson to me to include parentheses even when redundant...

    This reminds me of the following parenthesization gem
    (see next to last line):

    def isqrt(n):
    """Find the closest integer to sqrt(n), for n a positive
    integer."""
    a, b = n, 1
    while a != b:
    a, b = a -- n // a >> 1, a
    return a

    Mark
  • Steven D'Aprano at Mar 9, 2008 at 2:30 am

    On Sun, 09 Mar 2008 01:48:21 +0000, Steven D'Aprano wrote:

    (And the ease that these mistakes can happen is why such fundamental
    functions should be in the standard library, no matter how easy they are
    to implement.)
    Which, of course, they are.

    math.ceil() and math.floor()

    I knew that. *cough*

    --
    Steven
  • Steven D'Aprano at Mar 9, 2008 at 2:16 am

    On Sat, 08 Mar 2008 15:26:35 -0800, Paul Rubin wrote:

    Alasdair <amca01 at gmail.com> writes:
    What is the best way of finding a ceiling of a quotient of arbitrary
    sized integers?
    ceiling(a/b) = (a+b-1)//b

    Unfortunately that doesn't work reliably.
    a, b = 9007199254741000.0, -3.0
    a/b
    -3002399751580333.5
    (a+b-1)//b # should be -3002399751580333
    -3002399751580332.0



    I make no claim that this is the most efficient way to do it, but this
    should work:


    def splitfloat(f):
    """Return the integer and fraction part of a float."""
    fp = abs(f) % 1.0
    ip = abs(f) - fp
    if f < 0:
    ip, fp = -ip, -fp
    return (ip, fp)

    def ceil(f):
    ip, fp = splitfloat(f)
    if fp == 0:
    return ip
    elif f < 0:
    return ip
    else:
    return ip + 1

    a, b = 9007199254741000.0, -3.0
    ceil(a/b)
    -3002399751580333.0
    a, b = 9007199254741000.0, 3.0
    ceil(a/b)
    3002399751580334.0

    It even works for infinities, if supported by your platform:
    ceil(1.0/inf)
    0.0

    (Disclaimer: if you consider that 1.0/inf is a tiny bit more than zero,
    and therefore you want ceil(1.0/inf) to give 1.0, then you will disagree
    with me.)



    --
    Steven
  • Steven D'Aprano at Mar 9, 2008 at 2:38 am

    On Sun, 09 Mar 2008 02:16:39 +0000, Steven D'Aprano wrote:
    On Sat, 08 Mar 2008 15:26:35 -0800, Paul Rubin wrote:

    Alasdair <amca01 at gmail.com> writes:
    What is the best way of finding a ceiling of a quotient of arbitrary
    sized integers?
    ceiling(a/b) = (a+b-1)//b

    Unfortunately that doesn't work reliably.
    But of course you didn't intend it to work with floats, did you?

    Sigh.

    I'm just glad I didn't rant about people who think that floats are just
    like reals when they're not.


    --
    Steven
  • Steven D'Aprano at Mar 9, 2008 at 5:55 am

    On Sat, 08 Mar 2008 21:32:04 -0800, Paul Rubin wrote:

    I should have mentioned (a+b-1)//b expects a and b to be positive
    integers.
    Oh, I don't think that would have made any difference. I think I'm seeing
    floats everywhere today, including coming out of the walls.


    --
    Steven
  • Steven D'Aprano at Mar 9, 2008 at 2:31 am

    On Sun, 09 Mar 2008 10:11:53 +1100, Alasdair wrote:

    I need to apply the ceiling function to arbitrary sized (long) integers.
    However, division automatically returns the type of its operands, so
    that, for example: math.ceil(7/4) returns 1. I can use float, as in:
    math.ceil(7/float(4)), except that for very large integers float causes
    an unacceptable loss of precision.

    What is the best way of finding a ceiling of a quotient of arbitrary
    sized integers?
    def quot_ceil(a, b):
    """Returns the integer ceiling of the quotient of longints."""
    q, r = divmod(a, b)
    if r: return q+1
    else: return q



    --
    Steven
  • Alasdair at Mar 9, 2008 at 9:57 am
    Thanks, all - you've been most helpful. By the way, what does // do? I
    haven't yet run down its definition in the manual.

    -A.
  • Steven D'Aprano at Mar 9, 2008 at 12:09 pm

    On Sun, 09 Mar 2008 20:57:15 +1100, Alasdair wrote:

    Thanks, all - you've been most helpful. By the way, what does // do? I
    haven't yet run down its definition in the manual.
    // is integer division.
    10//5
    2
    11//5
    2



    In Python 2.5 and older, / means integer division, unless you do

    from __future__ import division

    in which case / is true division, that is:
    10/5
    2
    11/5
    2.5


    In Python 3.x, / will always be true division, and you won't need the
    import.


    --
    Steven

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
grouppython-list @
categoriespython
postedMar 8, '08 at 11:11p
activeMar 9, '08 at 12:09p
posts14
users5
websitepython.org

People

Translate

site design / logo © 2022 Grokbase