Move Demo/classes/Rat.py to Lib/fractions.py and fix it up.

[jyasskin]

BPO	1682
Nosy	@gvanrossum, @rhettinger, @facundobatista, @mdickinson, @ncoghlan, @wm75
Files	rational.patch rational.patch: V2, ported to 2.6 rational.patch: V3, still minimal rational_tweaks.patch: Some tweaks on top of the original implementation lehmer_gcd.py: Revised Lehmer gcd algorithm lehmer_gcd_2.py: Benchmark gcd implementations lehmer_gcd.patch fraction_inline_arith.patch

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2008-07-01.20:35:22.398>
created_at = <Date 2007-12-21.17:41:30.425>
labels = ['type-bug', 'library']
title = 'Move Demo/classes/Rat.py to Lib/fractions.py and fix it up.'
updated_at = <Date 2014-09-25.11:53:54.268>
user = 'https://bugs.python.org/jyasskin'

bugs.python.org fields:

activity = <Date 2014-09-25.11:53:54.268>
actor = 'wolma'
assignee = 'jyasskin'
closed = True
closed_date = <Date 2008-07-01.20:35:22.398>
closer = 'mark.dickinson'
components = ['Library (Lib)']
creation = <Date 2007-12-21.17:41:30.425>
creator = 'jyasskin'
dependencies = []
files = ['9021', '9114', '9152', '9201', '9464', '9485', '9486', '9570']
hgrepos = []
issue_num = 1682
keywords = ['patch']
message_count = 92.0
messages = ['58949', '59424', '59425', '59582', '59583', '59608', '59614', '59615', '59633', '59635', '59636', '59639', '59640', '59645', '59650', '59651', '59656', '59657', '59659', '59665', '59747', '59755', '59772', '59773', '59870', '59884', '59886', '59958', '59982', '60080', '60081', '60131', '60132', '60133', '60137', '61737', '61995', '62001', '62005', '62010', '62011', '62013', '62028', '62029', '62099', '62189', '62192', '62218', '62222', '62227', '62236', '62249', '62251', '62252', '62253', '62254', '62256', '62257', '62258', '62271', '62305', '62311', '62318', '62320', '62324', '62335', '62337', '62340', '62380', '62401', '62403', '62406', '62547', '62550', '62564', '62566', '62567', '62568', '62671', '62672', '63087', '63126', '68725', '68732', '68757', '68822', '68823', '68843', '68851', '69020', '69027', '69069']
nosy_count = 7.0
nosy_names = ['gvanrossum', 'rhettinger', 'facundobatista', 'mark.dickinson', 'ncoghlan', 'jyasskin', 'wolma']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = None
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue1682'
versions = ['Python 2.6', 'Python 3.0']

[jyasskin]

This is written against the 3.0 branch, but before submitting it, I need
to backport numbers.py and submit it against 2.6 instead. I'm posting it
now to get a head start on comments.

The numbers.py part is necessary for this to work but will be a separate
patch.

[mdickinson]

Some random comments: take with a large pinch of salt

(1) In __init__ I think you want something like:

 self._numerator = int(numerator)//g

instead of

 self._numerator = int(numerator / g)

and similarly for the denominator. At the moment I get, for example:

>>> Rational(10**23)
rational.Rational(99999999999999991611392,1)

(2) What's the reason for repr of a Rational being "rational.Rational(...)", while repr
of a Decimal is just "Decimal(...)"? I'm not suggesting that either is wrong; just
wondering whether there's some sort of guiding principle that would suggest one or the
other.

(3) My first thought on looking at the _gcd function was: "Shouldn't there be an abs()
somewhere in there"; since the gcd of two (possibly negative) integers is often
(usually?) defined as the largest *nonnegative* common divisor. But on closer
examination it's clear that the result of _gcd(a, b) has the same sign as that of b
(unless b == 0). So _gcd very cleverly chooses exactly the right sign so that the
denominator after rescaling is positive. I'm not sure whether this is a happy accident
or clever design, but either way it probably deserves a comment.

(4) the __ceil__ operation could be spelt more neatly as

return -(-a.numerator // a.denominator)

...but perhaps that just amounts to obfuscation :)

(5) It looks as though two-argument round just truncates when the second argument is
negative. Presmably this isn't what's wanted here?

>>> round(Rational(26), -1) # expecting Rational(30, 1)
rational.Rational(20,1)

(6) The behaviour of the equality test is questionable when floats are involved. For
example:

>>> 10**23 == float(10**23) # expect False
False
>>> Rational(10**23) == float(10**23) # I'd also expect False here
True

Ideally, if x is a Rational and y is a float then I'd suggest that x == y should return
True only when the numeric values really are equal. Coding this could be quite tricky,
though. One option would be to convert the float to an (exactly equal) Rational first--
-there's code to do this in the version of Rational.py in the sandbox.

(7) For purely selfish reasons, I for one will be very happy if/when this makes it into
2.6/3.0: I use Python a lot for teaching (geometry, number theory, linear algebra,
...); it's natural to work with rational numbers in this context; and it'll be much
easier to tell an interested student to just download Python than to tell them they also
need gmp and gmpy, or some other third party package, just to try out the code examples
I've given them.

[mdickinson]

Two more questions:

(1) should a Rational instance be hashable?
(2) Should "Rational(5,2) == Decimal('2.5')" evaluate to True or False?

If Rationals are hashable and 2.5 == Rational(5, 2) == Decimal('2.5') then the
rule that objects that compare equal should have equal hash is going to make
life *very* interesting...

[jyasskin]

Thanks again for the excellent comments.

__init__: good catch.

repr(Rational): The rule for repr is "eval(repr(object)) == object".
Unfortunately, that doesn't decide between the two formats, since both
assume some particular import statements. I picked the one more likely
to be unique, and I assume Decimal picked the shorter one. I can go
either way.

_gcd's sign: It's a happy accident for me. Possibly Sjoerd Mullender
designed it that way. I've added a comment and a test.

__ceil__: I like that implementation better.

2-argument round: Fixed and tested.

equality: Very good point. I've stolen the sandbox code and added
Rational.from_float() using it. I think I also need to make this change
to the comparisons.

hashing: oops, yes these should be hashable. Decimal cheats by comparing
!= to even floats that it's equal to, so I'm going to assume that they
also want Rational(5,2) != Decimal('2.5').

The new patch is against 2.6.

[rhettinger]

FWIW, I'm -1 on moving this module to the standard library. There has
been basically *zero* demand for something like this. Because rational
implementations seem to be more fun to write than to use, I think there
are some competing implementations.

[gvanrossum]

Raymond, do you *always* have to be such a grinch?

The mere existance of competing implementations proves that there's a
need. Hopefully having one in the stdlib will inspire others to
contribute improvements rather than starting from scratch.

[rhettinger]

Not sure I'm the grinch on this one. I thought PEPs on this were
rejected long ago and no one complained afterwards. After years of
watching newsgroup discussions and feature requests, I do not recall a
single request or seeing a single problem that was better solved with a
rational package. On python-help and the tutorial newsgroup, I've
never seen a question about the existing module in the Tools directory
or even a question on the topic.

I think rational modules are ubiquitous for the same reason as Sudoku
solvers -- they are cute, an easy exercise, and fun to write. There is
some variation in how each chooses to make compromises so the
denominators do not get unusably large. Also, there is some variation
in sophistication of the GCD/LCD algorithm.

I had thought the standards for inclusion in the standard library had
risen quite a bit (best-in-class category killers and whatnot). ISTM,
this is aspiring cruft -- I cannot remember encountering a real
business or engineering problem that needed rational arithmetic (the
decimal module seems to meet the rare need for high precision
arithmetic).

All that being said, maybe the module with serve some sort of
educational purpose or will serve to show-off the numeric tower
abstract base classes.

[facundobatista]

The PEP-239 is Rejected (http://www.python.org/dev/peps/pep-0239/).

If a Rational data type would be included in the stdlib, my
recommendation is that first that PEP would be reopened and pushed until
get accepted.

Also, note the kind of questions Mark is asking here: the analysis and
answer of those questions belongs to a PEP, not to a patch. We risk to
not be very rational (1/2 wink) in these decisions.

I'd close this patch as Rejected (as for the PEP), at least until the
PEP gets accepted (if ever).

[gvanrossum]

The rejection of PEP-239 was years ago. PEP-3141 was accepted; it
includes adding a rational type to the stdlib, and Jeffrey is doing this
with my encouragement.

The motivation is to have at least one example of each type in our
modest numeric tower in the stdlib. I'm sure there will be plenty of
uses for rational.py, e.g. in education. Of course, if someone has a
better candidate or a proposed improvement, speak up now! It looks like
Mark's suggestions can be treated as code review; I don't think we need
a new PEP.

Note that the mere existence of PEP-239 again points out that the demand
is not zero.

[rhettinger]

If this goes in, I have some recommendations:

• Follow the decimal module's lead in assiduously avoiding
  float->rational conversions. Something like Rat.from_float(1.1) is
  likely to produce unexpected results (like locking in an inexact input
  and having an unexpectedly large denominator).

• Likewise, follow decimal's lead in avoiding all automatic coercisions
  from floats: Rational(3,10) + 0.3 for example. The two don't mix.

• Consider following decimal's lead on having a context that can limit
  the maximum size of a denominator. There are various strategies for
  handling a limit overflow including raising an exception or finding the
  nearest rational upto the max denominator (there are some excellent
  though complex published algorithms for this) or rounding the nearest
  fixed-base (very easy). I'll dig out my HP calculator manuals at some
  point -- they had worked-out a number of challenges with fractional
  arithmetic (including their own version of an Inexact tag).

• Consider adding Decimal.from_rational and Rational.from_decimal. I
  believe these are both easy and can be done losslessly.

• Automatic coercions to/from Decimal need to respect the active decimal
  context. For example the result of Rational(3,11) +
  Decimal('3.1415926') is context dependent and may not be commutative.

• When in doubt, keep the API minimal so we don't lock-in design mistakes.

• Test the API by taking a few numerical algorithms and seeing how well
  they work with rational inputs (for starters, try
  http://docs.python.org/lib/decimal-recipes.html ).

• If you do put in a method that accepts floats, make sure that it can
  accept arguments to control the rational approximation. Ideally, you
  would get something something like this Rational.approximate(math.pi, 6)
  --> 355/113 that could produce the smallest rationalal approximation to
  a given level of accuracy.

[facundobatista]

2008/1/9, Raymond Hettinger said:

• Consider adding Decimal.from_rational and Rational.from_decimal. I
  believe these are both easy and can be done losslessly.

If it's lossless, why not just allow Decimal(Rational(...)) and
Rational(Decimal(...))?

[rhettinger]

If it's lossless, why not just allow
Decimal(Rational(...)) and Rational(Decimal(...))?

Those conversions are fine.

It's the float<-->rational conversions that are problematic. There are
exact float to rational conversions using math.frexp() but I don't think
the results tend to match what users expect (since 1.1 isn't exactly
represented). Also, there may be overflow issues with trying to go from
rationals to floats when the denomintor is very large.

I think the history of rational modules is that simplistic
implementations get built and then the writers find that exploding
denominators limit their usefulness for anything other than trivial
problems. The solution is to limit denominators but that involves less
trivial algorithms and a more sophisticated API.