[Python-Dev] Re: PEP239 (Rational Numbers) Reference Implementation and new issues (original) (raw)

M.-A. Lemburg mal@lemburg.com
Fri, 04 Oct 2002 20:16:57 +0200

Tim Peters wrote:

[M.-A. Lemburg]

... But isn't division much more costly than addition and multiplication if you have long integers to deal with ? (I can't tell, because the works are done by GMP in mxNumber) There's no real bound on how large partial quotients can get, and rationals can grow extremely large. Dividing once to get, e.g., 10000, is enormously cheaper than going around a Python loop 10000 times, and creating and destroying several times that many temporary longs, just to avoid one relatively fast C-speed longint division with a small quotient.

Well, I'm working with GMP here, so temporary longs are not that expensive (plus they reuse already allocated memory). That's why I was asking.

It's essentially the same as figuring out "the fastest" way to code a gcd, and that's a very tricky problem at the Python level. Partial quotients are usually 1, and then subtraction is cheaper, and it's also possible to meld both approaches to exploit that.

I see. Thanks.

... How useful are .trim() and .approximate() in practice ?

You're going to get as many responses to that as Guido got to his query about how mxNumber users like its type hierarchy .

:-)

If they are, then I could put them on the TODO list for mxNumber.

They're useful for people who want to mix rationals with approximation, and that's an unlikely intersection outside of expert use. trim is essentially what fixed-slash and floating-slash arithmetics use under the covers to keep rigorous bounds on memory use, in exchange for losing information. How useful is that in practice? Beats me; it depends so much on whose practice we're talking about .

Point taken.

I just added the Farey algorithm to mxNumber because it seemed like a nice way of limiting the size of the integers involved in the rational representation of floats.

It sometimes even helps to e.g. backpatch rounding/representation errors in floating point calculations when you know that your dealing with small denominator rationals:

1/3.0 0.33333333333333331 FareyRational(1/3.0, 100) 1/3

-- Marc-Andre Lemburg CEO eGenix.com Software GmbH

eGenix.com -- Makers of the Python mx Extensions: mxDateTime,mxODBC,... Python Consulting: http://www.egenix.com/ Python Software: http://www.egenix.com/files/python/