[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.python

Arbitrary precision integer arithmetic: ceiling?

Alasdair

3/8/2008 11:12:00 PM

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
15 Answers

Paul Rubin

3/8/2008 11:27:00 PM

0

Alasdair <amca01@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

Robert Kern

3/8/2008 11:32:00 PM

0

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

3/9/2008 1:09:00 AM

0

On Mar 8, 6:26 pm, Paul Rubin <http://phr...@NOSPAM.invalid> wrote:
> Alasdair <amc...@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

3/9/2008 1:48:00 AM

0

On Sat, 08 Mar 2008 17:09:11 -0800, Mark Dickinson wrote:

> On Mar 8, 6:26 pm, Paul Rubin <http://phr...@NOSPAM.invalid> wrote:
>> Alasdair <amc...@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

3/9/2008 2:11:00 AM

0

On Mar 8, 8:48 pm, Steven D'Aprano <st...@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

Steven D'Aprano

3/9/2008 2:17:00 AM

0

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

> Alasdair <amca01@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

Terry Reedy

3/9/2008 2:20:00 AM

0


"Steven D'Aprano" <steve@REMOVE-THIS-cybersource.com.au> wrote in message
news:13t6gf5on1qnhbe@corp.supernews.com...
| On Sat, 08 Mar 2008 17:09:11 -0800, Mark Dickinson wrote:
|
| > On Mar 8, 6:26 pm, Paul Rubin <http://phr...@NOSPAM.invalid> wrote:
| >> Alasdair <amc...@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

3/9/2008 2:27:00 AM

0

On Mar 8, 9:19 pm, "Terry Reedy" <tjre...@udel.edu> 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

3/9/2008 2:31:00 AM

0

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

3/9/2008 2:31:00 AM

0

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