Arbitrary precision integer arithmetic: ceiling?

Discussion in 'Python' started by Alasdair, Mar 8, 2008.

1. AlasdairGuest

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

Alasdair, Mar 8, 2008

2. Paul RubinGuest

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

Paul Rubin, Mar 8, 2008

3. Robert KernGuest

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
an underlying truth."
-- Umberto Eco

Robert Kern, Mar 8, 2008
4. Mark DickinsonGuest

I prefer:

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

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

Mark

Mark Dickinson, Mar 9, 2008
5. Steven D'ApranoGuest

Unfortunately it doesn't give the right answer.
-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 D'Aprano, Mar 9, 2008
6. Mark DickinsonGuest

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

Mark Dickinson, Mar 9, 2008
7. Steven D'ApranoGuest

Unfortunately that doesn't work reliably.
-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

3002399751580334.0

It even works for infinities, if supported by your platform:
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 D'Aprano, Mar 9, 2008
8. Terry ReedyGuest

| On Sat, 08 Mar 2008 17:09:11 -0800, Mark Dickinson wrote:
|
| >> > 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

Terry Reedy, Mar 9, 2008
9. Mark DickinsonGuest

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

Mark Dickinson, Mar 9, 2008
10. Steven D'ApranoGuest

Which, of course, they are.

math.ceil() and math.floor()

I knew that. *cough*

Steven D'Aprano, Mar 9, 2008
11. Steven D'ApranoGuest

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 D'Aprano, Mar 9, 2008
12. Steven D'ApranoGuest

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 D'Aprano, Mar 9, 2008
13. Paul RubinGuest

I should have mentioned (a+b-1)//b expects a and b to be positive
integers.

Paul Rubin, Mar 9, 2008
14. Steven D'ApranoGuest

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 D'Aprano, Mar 9, 2008
15. AlasdairGuest

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.

Alasdair, Mar 9, 2008
16. Steven D'ApranoGuest

// is integer division.
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:
2.5

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

Steven D'Aprano, Mar 9, 2008