A Revised Rational Proposal

[Mike Meyer]

This version includes the input from various and sundry people. Thanks
to everyone who contributed.

<mike

PEP: XXX
Title: A rational number module for Python
Version: $Revision: 1.4 $
Last-Modified: $Date: 2003/09/22 04:51:50 $
Author: Mike Meyer <mw*@mired.org>
Status: Draft
Type: Staqndards
Content-Type: text/x-rst
Created: 16-Dec-2004
Python-Version: 2.5
Post-History: 15-Dec-2004, 25-Dec-2004
Contents
========

* Abstract
* Motivation
* Rationale
+ Conversions
+ Python usability
* Specification
+ Explicit Construction
+ Implicit Construction
+ Operations
+ Exceptions
* Open Issues
* Implementation
* References
Abstract
========

This PEP proposes a rational number module to add to the Python
standard library.
Motivation
=========

Rationals are a standard mathematical concept, included in a variety
of programming languages already. Python, which comes with 'batteries
included' should not be deficient in this area. When the subject was
brought up on comp.lang.python several people mentioned having
implemented a rational number module, one person more than once. In
fact, there is a rational number module distributed with Python as an
example module. Such repetition shows the need for such a class in the
standard library.
n
There are currently two PEPs dealing with rational numbers - 'Adding a
Rational Type to Python' [#PEP-239] and 'Adding a Rational Literal to
Python' [#PEP-240], both by Craig and Zadka. This PEP competes with
those PEPs, but does not change the Python language as those two PEPs
do [#PEP-239-implicit]. As such, it should be easier for it to gain
acceptance. At some future time, PEP's 239 and 240 may replace the
``rational`` module.
Rationale
=========

Conversions
-----------

The purpose of a rational type is to provide an exact representation
of rational numbers, without the imprecistion of floating point
numbers or the limited precision of decimal numbers.

Converting an int or a long to a rational can be done without loss of
precision, and will be done as such.

Converting a decimal to a rational can also be done without loss of
precision, and will be done as such.

A floating point number generally represents a number that is an
approximation to the value as a literal string. For example, the
literal 1.1 actually represents the value 1.1000000000000001 on an x86
one platform. To avoid this imprecision, floating point numbers
cannot be translated to rationals directly. Instead, a string
representation of the float must be used: ''Rational("%.2f" % flt)''
so that the user can specify the precision they want for the floating
point number. This lack of precision is also why floating point
numbers will not combine with rationals using numeric operations.

Decimal numbers do not have the representation problems that floating
point numbers have. However, they are rounded to the current context
when used in operations, and thus represent an approximation.
Therefore, a decimal can be used to explicitly construct a rational,
but will not be allowed to implicitly construct a rational by use in a
mixed arithmetic expression.
Python Usability
-----------------

* Rational should support the basic arithmetic (+, -, *, /, //, **, %,
divmod) and comparison (==, !=, <, >, <=, >=, cmp) operators in the
following cases (check Implicit Construction to see what types could
OtherType be, and what happens in each case):

+ Rational op Rational
+ Rational op otherType
+ otherType op Rational
+ Rational op= Rational
+ Rational op= otherType
* Rational should support unary operators (-, +, abs).

* repr() should round trip, meaning that:

m = Rational(...)
m == eval(repr(m))

* Rational should be immutable.

* Rational should support the built-in methods:

+ min, max
+ float, int, long
+ str, repr
+ hash
+ bool (0 is false, otherwise true)

When it comes to hashes, it is true that Rational(25) == 25 is True, so
hash(Rational (25)) should be equal to hash(25).

The detail is that you can NOT compare Rational to floats, strings or
decimals, so we do not worry about them giving the same hashes. In
short:

hash(n) == hash(Rational(n)) # Only if n is int, long or Rational

Regarding str() and repr() behaviour, Ka-Ping Yee proposes that repr() have
the same behaviour as str() and Tim Peters proposes that str() behave like the
to-scientific-string operation from the Spec.
Specification
=============

Explicit Construction
---------------------

The module shall be ``rational``, and the class ``Rational``, to
follow the example of the decimal [#PEP-327] module. The class
creation method shall accept as arguments a numerator, and an optional
denominator, which defaults to one. Both the numerator and
denominator - if present - must be of integer or decimal type, or a
string representation of a floating point number. The string
representation of a floating point number will be converted to
rational without being converted to float to preserve the accuracy of
the number. Since all other numeric types in Python are immutable,
Rational objects will be immutable. Internally, the representation
will insure that the numerator and denominator have a greatest common
divisor of 1, and that the sign of the denominator is positive.
Implicit Construction
---------------------

Rationals will mix with integer types. If the other operand is not
rational, it will be converted to rational before the opeation is
performed.

When combined with a floating type - either complex or float - or a
decimal type, the result will be a TypeError. The reason for this is
that floating point numbers - including complex - and decimals are
already imprecise. To convert them to rational would give an
incorrect impression that the results of the operation are
precise. The proper way to add a rational to one of these types is to
convert the rational to that type explicitly before doing the
operation.
Operations
----------

The ``Rational`` class shall define all the standard mathematical
operations mentioned in the ''Python Usability'' section.

Rationals can be converted to floats by float(rational), and to
integers by int(rational). int(rational) will just do an integer
division of the numerator by the denominator.

If there is not a __decimal__ feature for objects in Python 2.5, the
rational type will provide a decimal() method that returns the value
of self converted to a decimal in the current context.
Exceptions
----------

The module will define and at times raise the following exceptions:

- DivisionByZero: divide by zero.

- OverflowError: overflow attempting to convert to a float.

- TypeError: trying to create a rational from a non-integer or
non-string type, or trying to perform an operation
with a float, complex or decimal.

- ValueError: trying to create a rational from a string value that is
not a valid represetnation of an integer or floating
point number.

Note that the decimal initializer will have to be modified to handle
rationals.
Open Issues
===========

- Should raising a rational to a non-integer rational silently produce
a float, or raise an InvalidOperation exception?

Implementation
==============

There is currently a rational module distributed with Python, and a
second rational module in the Python cvs source tree that is not
distributed. While one of these could be chosen and made to conform
to the specification, I am hoping that several people will volunteer
implementatins so that a ''best of breed'' implementation may be
chosen.
References
==========

... [#PEP-239] Adding a Rational Type to Python, Craig, Zadka
(http://www.python.org/peps/pep-0239.html)
... [#PEP-240] Adding a Rational Literal to Python, Craig, Zadka
(http://www.python.org/peps/pep-0240.html)
... [#PEP-327] Decimal Data Type, Batista
(http://www.python.org/peps/pep-0327.html)
... [#PEP-239-implicit] PEP 240 adds a new literal type to Pytbon,
PEP 239 implies that division of integers would
change to return rationals.
Copyright
=========

This document has been placed in the public domain.

...
Local Variables:
mode: indented-text
indent-tabs-mode: nil
sentence-end-double-space: t
fill-column: 70
End:

--
Mike Meyer <mw*@mired.org> http://www.mired.org/home/mwm/
Independent WWW/Perforce/FreeBSD/Unix consultant, email for more information.

[Dan Bishop]

Mike Meyer wrote:

This version includes the input from various and sundry people. Thanks to everyone who contributed.

<mike

PEP: XXX
Title: A rational number module for Python .... Implicit Construction
---------------------

When combined with a floating type - either complex or float - or a
decimal type, the result will be a TypeError. The reason for this is
that floating point numbers - including complex - and decimals are
already imprecise. To convert them to rational would give an
incorrect impression that the results of the operation are
precise. The proper way to add a rational to one of these types is to
convert the rational to that type explicitly before doing the
operation.

I disagree with raising a TypeError here. If, in mixed-type
expressions, we treat ints as a special case of rationals, it's
inconsistent for rationals to raise TypeErrors in situations where int
doesn't.

2 + 0.5 2.5 Rational(2) + 0.5

TypeError: unsupported operand types for +: 'Rational' and 'float'

[John Roth]

"Dan Bishop" <da*****@yahoo.com> wrote in message
news:11*********************@c13g2000cwb.googlegro ups.com...

Mike Meyer wrote:

This version includes the input from various and sundry people. Thanks

to everyone who contributed.

<mike

PEP: XXX
Title: A rational number module for Python

...

Implicit Construction
---------------------

When combined with a floating type - either complex or float - or a
decimal type, the result will be a TypeError. The reason for this is
that floating point numbers - including complex - and decimals are
already imprecise. To convert them to rational would give an
incorrect impression that the results of the operation are
precise. The proper way to add a rational to one of these types is to
convert the rational to that type explicitly before doing the
operation.

I disagree with raising a TypeError here. If, in mixed-type
expressions, we treat ints as a special case of rationals, it's
inconsistent for rationals to raise TypeErrors in situations where int
doesn't.

2 + 0.5 2.5 Rational(2) + 0.5

TypeError: unsupported operand types for +: 'Rational' and 'float'

I agree that the direction of coercion should be toward
the floating type, but Decimal doesn't combine with Float either.
It should be both or neither.

John Roth
John Roth

[Dan Bishop]

Mike Meyer wrote:

This version includes the input from various and sundry people. Thanks to everyone who contributed.

<mike

PEP: XXX
Title: A rational number module for Python .... Implementation
==============

There is currently a rational module distributed with Python, and a
second rational module in the Python cvs source tree that is not
distributed. While one of these could be chosen and made to conform
to the specification, I am hoping that several people will volunteer
implementatins so that a ''best of breed'' implementation may be
chosen.

I'll be the first to volunteer an implementation.

I've made the following deviations from your PEP:

* Binary operators with one Rational operand and one float or Decimal
operand will not raise a TypeError, but return a float or Decimal.
* Expressions of the form Decimal op Rational do not work. This is a
bug in the decimal module.
* The constructor only accepts ints and longs. Conversions from float
or Decimal to Rational can be made with the static methods:
- fromExactFloat: exact conversion from float to Rational
- fromExactDecimal: exact conversion from Decimal to Rational
- approxSmallestDenominator: Minimizes the result's denominator,
given a maximum allowed error.
- approxSmallestError: Minimizes the result's error, given a
maximum allowed denominator.
For example,

Rational.fromExactFloat(math.pi) Rational(884279719003555, 281474976710656) decimalPi = Decimal("3.141592653589793238462643383")
Rational.fromExactDecimal(decimalPi) Rational(3141592653589793238462643383, 1000000000000000000000000000) Rational.approxSmallestDenominator(math.pi, 0.01) Rational(22, 7) Rational.approxSmallestDenominator(math.pi, 0.001) Rational(201, 64) Rational.approxSmallestDenominator(math.pi, 0.0001) Rational(333, 106) Rational.approxSmallestError(math.pi, 10) Rational(22, 7) Rational.approxSmallestError(math.pi, 100) Rational(311, 99) Rational.approxSmallestError(math.pi, 1000)

Rational(355, 113)

Anyhow, here's my code:

from __future__ import division

import decimal
import math

def _gcf(a, b):
"Returns the greatest common factor of a and b."
a = abs(a)
b = abs(b)
while b:
a, b = b, a % b
return a

class Rational(object):
"Exact representation of rational numbers."
def __init__(self, numerator, denominator=1):
"Contructs the Rational object for numerator/denominator."
if not isinstance(numerator, (int, long)):
raise TypeError('numerator must have integer type')
if not isinstance(denominator, (int, long)):
raise TypeError('denominator must have integer type')
if not denominator:
raise ZeroDivisionError('rational construction')
factor = _gcf(numerator, denominator)
self.__n = numerator // factor
self.__d = denominator // factor
if self.__d < 0:
self.__n = -self.__n
self.__d = -self.__d
def __repr__(self):
if self.__d == 1:
return "Rational(%d)" % self.__n
else:
return "Rational(%d, %d)" % (self.__n, self.__d)
def __str__(self):
if self.__d == 1:
return str(self.__n)
else:
return "%d/%d" % (self.__n, self.__d)
def __hash__(self):
try:
return hash(float(self))
except OverflowError:
return hash(long(self))
def __float__(self):
return self.__n / self.__d
def __int__(self):
if self.__n < 0:
return -int(-self.__n // self.__d)
else:
return int(self.__n // self.__d)
def __long__(self):
return long(int(self))
def __nonzero__(self):
return bool(self.__n)
def __pos__(self):
return self
def __neg__(self):
return Rational(-self.__n, self.__d)
def __abs__(self):
if self.__n < 0:
return -self
else:
return self
def __add__(self, other):
if isinstance(other, Rational):
return Rational(self.__n * other.__d + self.__d * other.__n,
self.__d * other.__d)
elif isinstance(other, (int, long)):
return Rational(self.__n + self.__d * other, self.__d)
elif isinstance(other, (float, complex)):
return float(self) + other
elif isinstance(other, decimal.Decimal):
return self.decimal() + other
else:
return NotImplemented
__radd__ = __add__
def __sub__(self, other):
if isinstance(other, Rational):
return Rational(self.__n * other.__d - self.__d * other.__n,
self.__d * other.__d)
elif isinstance(other, (int, long)):
return Rational(self.__n - self.__d * other, self.__d)
elif isinstance(other, (float, complex)):
return float(self) - other
elif isinstance(other, decimal.Decimal):
return self.decimal() - other
else:
return NotImplemented
def __rsub__(self, other):
if isinstance(other, (int, long)):
return Rational(other * self.__d - self.__n, self.__d)
elif isinstance(other, (float, complex)):
return other - float(self)
elif isinstance(other, decimal.Decimal):
return other - self.decimal()
else:
return NotImplemented
def __mul__(self, other):
if isinstance(other, Rational):
return Rational(self.__n * other.__n, self.__d * other.__d)
elif isinstance(other, (int, long)):
return Rational(self.__n * other, self.__d)
elif isinstance(other, (float, complex)):
return float(self) * other
elif isinstance(other, decimal.Decimal):
return self.decimal() * other
else:
return NotImplemented
__rmul__ = __mul__
def __truediv__(self, other):
if isinstance(other, Rational):
return Rational(self.__n * other.__d, self.__d * other.__n)
elif isinstance(other, (int, long)):
return Rational(self.__n, self.__d * other)
elif isinstance(other, (float, complex)):
return float(self) / other
elif isinstance(other, decimal.Decimal):
return self.decimal() / other
else:
return NotImplemented
__div__ = __truediv__
def __rtruediv__(self, other):
if isinstance(other, (int, long)):
return Rational(other * self.__d, self.__n)
elif isinstance(other, (float, complex)):
return other / float(self)
elif isinstance(other, decimal.Decimal):
return other / self.decimal()
else:
return NotImplemented
__rdiv__ = __rtruediv__
def __floordiv__(self, other):
truediv = self / other
if isinstance(truediv, Rational):
return truediv.__n // truediv.__d
else:
return truediv // 1
def __rfloordiv__(self, other):
return (other / self) // 1
def __mod__(self, other):
return self - self // other * other
def __rmod__(self, other):
return other - other // self * self
def __divmod__(self, other):
return self // other, self % other
def __cmp__(self, other):
if other == 0:
return cmp(self.__n, 0)
else:
return cmp(self - other, 0)
def __pow__(self, other):
if isinstance(other, (int, long)):
if other < 0:
return Rational(self.__d ** -other, self.__n ** -other)
else:
return Rational(self.__n ** other, self.__d ** other)
else:
return float(self) ** other
def __rpow__(self, other):
return other ** float(self)
def decimal(self):
"Decimal approximation of self in the current context"
return decimal.Decimal(self.__n) / decimal.Decimal(self.__d)
@staticmethod
def fromExactFloat(x):
"Returns the exact rational equivalent of x."
mantissa, exponent = math.frexp(x)
mantissa = int(mantissa * 2 ** 53)
exponent -= 53
if exponent < 0:
return Rational(mantissa, 2 ** (-exponent))
else:
return Rational(mantissa * 2 ** exponent)
@staticmethod
def fromExactDecimal(x):
"Returns the exact rational equivalent of x."
sign, mantissa, exponent = x.as_tuple()
sign = (1, -1)[sign]
mantissa = sign * reduce(lambda a, b: 10 * a + b, mantissa)
if exponent < 0:
return Rational(mantissa, 10 ** (-exponent))
else:
return Rational(mantissa * 10 ** exponent)
@staticmethod
def approxSmallestDenominator(x, tolerance):
"Returns a rational m/n such that abs(x - m/n) < tolerance,\n" \
"minimizing n."
tolerance = abs(tolerance)
n = 1
while True:
m = int(round(x * n))
result = Rational(m, n)
if abs(result - x) < tolerance:
return result
n += 1
@staticmethod
def approxSmallestError(x, maxDenominator):
"Returns a rational m/n minimizing abs(x - m/n),\n" \
"with the constraint 1 <= n <= maxDenominator."
result = None
minError = x
for n in xrange(1, maxDenominator + 1):
m = int(round(x * n))
r = Rational(m, n)
error = abs(r - x)
if error == 0:
return r
elif error < minError:
result = r
minError = error
return result

[Dan Bishop]

Dan Bishop wrote:

Mike Meyer wrote:

This version includes the input from various and sundry people.

Thanks

to everyone who contributed.

<mike

PEP: XXX
Title: A rational number module for Python

...

Implementation
==============

There is currently a rational module distributed with Python, and a
second rational module in the Python cvs source tree that is not
distributed. While one of these could be chosen and made to conform to the specification, I am hoping that several people will volunteer implementatins so that a ''best of breed'' implementation may be
chosen.

I'll be the first to volunteer an implementation.

The new Google Groups software appears to have problems with
indentation. I'm posting my code again, with indents replaced with
instructions on how much to indent.

from __future__ import division

import decimal
import math

def _gcf(a, b):
{indent 1}"Returns the greatest common factor of a and b."
{indent 1}a = abs(a)
{indent 1}b = abs(b)
{indent 1}while b:
{indent 2}a, b = b, a % b
{indent 1}return a

class Rational(object):
{indent 1}"Exact representation of rational numbers."
{indent 1}def __init__(self, numerator, denominator=1):
{indent 2}"Contructs the Rational object for numerator/denominator."
{indent 2}if not isinstance(numerator, (int, long)):
{indent 3}raise TypeError('numerator must have integer type')
{indent 2}if not isinstance(denominator, (int, long)):
{indent 3}raise TypeError('denominator must have integer type')
{indent 2}if not denominator:
{indent 3}raise ZeroDivisionError('rational construction')
{indent 2}factor = _gcf(numerator, denominator)
{indent 2}self.__n = numerator // factor
{indent 2}self.__d = denominator // factor
{indent 2}if self.__d < 0:
{indent 3}self.__n = -self.__n
{indent 3}self.__d = -self.__d
{indent 1}def __repr__(self):
{indent 2}if self.__d == 1:
{indent 3}return "Rational(%d)" % self.__n
{indent 2}else:
{indent 3}return "Rational(%d, %d)" % (self.__n, self.__d)
{indent 1}def __str__(self):
{indent 2}if self.__d == 1:
{indent 3}return str(self.__n)
{indent 2}else:
{indent 3}return "%d/%d" % (self.__n, self.__d)
{indent 1}def __hash__(self):
{indent 2}try:
{indent 3}return hash(float(self))
{indent 2}except OverflowError:
{indent 3}return hash(long(self))
{indent 1}def __float__(self):
{indent 2}return self.__n / self.__d
{indent 1}def __int__(self):
{indent 2}if self.__n < 0:
{indent 3}return -int(-self.__n // self.__d)
{indent 2}else:
{indent 3}return int(self.__n // self.__d)
{indent 1}def __long__(self):
{indent 2}return long(int(self))
{indent 1}def __nonzero__(self):
{indent 2}return bool(self.__n)
{indent 1}def __pos__(self):
{indent 2}return self
{indent 1}def __neg__(self):
{indent 2}return Rational(-self.__n, self.__d)
{indent 1}def __abs__(self):
{indent 2}if self.__n < 0:
{indent 3}return -self
{indent 2}else:
{indent 3}return self
{indent 1}def __add__(self, other):
{indent 2}if isinstance(other, Rational):
{indent 3}return Rational(self.__n * other.__d + self.__d * other.__n,
self.__d * other.__d)
{indent 2}elif isinstance(other, (int, long)):
{indent 3}return Rational(self.__n + self.__d * other, self.__d)
{indent 2}elif isinstance(other, (float, complex)):
{indent 3}return float(self) + other
{indent 2}elif isinstance(other, decimal.Decimal):
{indent 3}return self.decimal() + other
{indent 2}else:
{indent 3}return NotImplemented
{indent 1}__radd__ = __add__
{indent 1}def __sub__(self, other):
{indent 2}if isinstance(other, Rational):
{indent 3}return Rational(self.__n * other.__d - self.__d * other.__n,
self.__d * other.__d)
{indent 2}elif isinstance(other, (int, long)):
{indent 3}return Rational(self.__n - self.__d * other, self.__d)
{indent 2}elif isinstance(other, (float, complex)):
{indent 3}return float(self) - other
{indent 2}elif isinstance(other, decimal.Decimal):
{indent 3}return self.decimal() - other
{indent 2}else:
{indent 3}return NotImplemented
{indent 1}def __rsub__(self, other):
{indent 2}if isinstance(other, (int, long)):
{indent 3}return Rational(other * self.__d - self.__n, self.__d)
{indent 2}elif isinstance(other, (float, complex)):
{indent 3}return other - float(self)
{indent 2}elif isinstance(other, decimal.Decimal):
{indent 3}return other - self.decimal()
{indent 2}else:
{indent 3}return NotImplemented
{indent 1}def __mul__(self, other):
{indent 2}if isinstance(other, Rational):
{indent 3}return Rational(self.__n * other.__n, self.__d * other.__d)
{indent 2}elif isinstance(other, (int, long)):
{indent 3}return Rational(self.__n * other, self.__d)
{indent 2}elif isinstance(other, (float, complex)):
{indent 3}return float(self) * other
{indent 2}elif isinstance(other, decimal.Decimal):
{indent 3}return self.decimal() * other
{indent 2}else:
{indent 3}return NotImplemented
{indent 1}__rmul__ = __mul__
{indent 1}def __truediv__(self, other):
{indent 2}if isinstance(other, Rational):
{indent 3}return Rational(self.__n * other.__d, self.__d * other.__n)
{indent 2}elif isinstance(other, (int, long)):
{indent 3}return Rational(self.__n, self.__d * other){indent 2}
{indent 2}elif isinstance(other, (float, complex)):
{indent 3}return float(self) / other
{indent 2}elif isinstance(other, decimal.Decimal):
{indent 3}return self.decimal() / other
{indent 2}else:
{indent 3}return NotImplemented
{indent 1}__div__ = __truediv__
{indent 1}def __rtruediv__(self, other):
{indent 2}if isinstance(other, (int, long)):
{indent 3}return Rational(other * self.__d, self.__n)
{indent 2}elif isinstance(other, (float, complex)):
{indent 3}return other / float(self)
{indent 2}elif isinstance(other, decimal.Decimal):
{indent 3}return other / self.decimal()
{indent 2}else:
{indent 3}return NotImplemented
{indent 1}__rdiv__ = __rtruediv__
{indent 1}def __floordiv__(self, other):
{indent 2}truediv = self / other
{indent 2}if isinstance(truediv, Rational):
{indent 3}return truediv.__n // truediv.__d
{indent 2}else:
{indent 3}return truediv // 1
{indent 1}def __rfloordiv__(self, other):
{indent 2}return (other / self) // 1
{indent 1}def __mod__(self, other):
{indent 2}return self - self // other * other
{indent 1}def __rmod__(self, other):
{indent 2}return other - other // self * self
{indent 1}def __divmod__(self, other):
{indent 2}return self // other, self % other
{indent 1}def __cmp__(self, other):
{indent 2}if other == 0:
{indent 3}return cmp(self.__n, 0)
{indent 2}else:
{indent 3}return cmp(self - other, 0)
{indent 1}def __pow__(self, other):
{indent 2}if isinstance(other, (int, long)):
{indent 3}if other < 0:
{indent 4}return Rational(self.__d ** -other, self.__n ** -other)
{indent 3}else:
{indent 4}return Rational(self.__n ** other, self.__d ** other)
{indent 2}else:
{indent 3}return float(self) ** other
{indent 1}def __rpow__(self, other):
{indent 2}return other ** float(self)
{indent 1}def decimal(self):
{indent 2}"Decimal approximation of self in the current context"
{indent 2}return decimal.Decimal(self.__n) / decimal.Decimal(self.__d)
{indent 1}@staticmethod
{indent 1}def fromExactFloat(x):
{indent 2}"Returns the exact rational equivalent of x."
{indent 2}mantissa, exponent = math.frexp(x)
{indent 2}mantissa = int(mantissa * 2 ** 53)
{indent 2}exponent -= 53
{indent 2}if exponent < 0:
{indent 3}return Rational(mantissa, 2 ** (-exponent))
{indent 2}else:
{indent 3}return Rational(mantissa * 2 ** exponent)
{indent 1}@staticmethod
{indent 1}def fromExactDecimal(x):
{indent 2}"Returns the exact rational equivalent of x."
{indent 2}sign, mantissa, exponent = x.as_tuple()
{indent 2}sign = (1, -1)[sign]
{indent 2}mantissa = sign * reduce(lambda a, b: 10 * a + b, mantissa)
{indent 2}if exponent < 0:
{indent 3}return Rational(mantissa, 10 ** (-exponent))
{indent 2}else:
{indent 3}return Rational(mantissa * 10 ** exponent)
{indent 1}@staticmethod
{indent 1}def approxSmallestDenominator(x, tolerance):
{indent 2}"Returns a rational m/n such that abs(x - m/n) <
tolerance,\n" \
{indent 2}"minimizing n."
{indent 2}tolerance = abs(tolerance)
{indent 2}n = 1
{indent 2}while True:
{indent 3}m = int(round(x * n))
{indent 3}result = Rational(m, n)
{indent 3}if abs(result - x) < tolerance:
{indent 4}return result
{indent 3}n += 1
{indent 1}@staticmethod
{indent 1}def approxSmallestError(x, maxDenominator):
{indent 2}"Returns a rational m/n minimizing abs(x - m/n),\n" \
{indent 2}"with the constraint 1 <= n <= maxDenominator."
{indent 2}result = None
{indent 2}minError = x
{indent 2}for n in xrange(1, maxDenominator + 1):
{indent 3}m = int(round(x * n))
{indent 3}r = Rational(m, n)
{indent 3}error = abs(r - x)
{indent 3}if error == 0:
{indent 4}return r
{indent 3}elif error < minError:
{indent 4}result = r
{indent 4}minError = error
{indent 2}return result

[Steven Bethard]

Dan Bishop wrote:

Mike Meyer wrote:

PEP: XXX

I'll be the first to volunteer an implementation.

Very cool. Thanks for the quick work!

For stdlib acceptance, I'd suggest a few cosmetic changes:

Use PEP 257[1] docstring conventions, e.g. triple-quoted strings.

Use PEP 8[2] naming conventions, e.g. name functions from_exact_float,
approx_smallest_denominator, etc.

The decimal and math modules should probably be imported as _decimal and
_math. This will keep them from showing up in the module namespace in
editors like PythonWin.

I would be inclined to name the instance variables _n and _d instead of
the double-underscore versions. There was a thread a few months back
about avoiding overuse of __x name-mangling, but I can't find it. It
also might be nice for subclasses of Rational to be able to easily
access _n and _d.

Thanks again for your work!

Steve

[1] http://www.python.org/peps/pep-0257.html
[2] http://www.python.org/peps/pep-0008.html

[John Roth]

"Steven Bethard" <st************@gmail.com> wrote in message
news:iWCzd.19458$k25.5585@attbi_s53...

Dan Bishop wrote:

Mike Meyer wrote:

PEP: XXX
I'll be the first to volunteer an implementation.

Very cool. Thanks for the quick work!

For stdlib acceptance, I'd suggest a few cosmetic changes:

Use PEP 257[1] docstring conventions, e.g. triple-quoted strings.

Use PEP 8[2] naming conventions, e.g. name functions from_exact_float,
approx_smallest_denominator, etc.

The decimal and math modules should probably be imported as _decimal and
_math. This will keep them from showing up in the module namespace in
editors like PythonWin.

I would be inclined to name the instance variables _n and _d instead of
the double-underscore versions. There was a thread a few months back
about avoiding overuse of __x name-mangling, but I can't find it. It also
might be nice for subclasses of Rational to be able to easily access _n
and _d.

I'd suggest making them public rather than either protected or
private. There's a precident with the complex module, where
the real and imaginary parts are exposed as .real and .imag.

John Roth

Thanks again for your work!

Steve

[1] http://www.python.org/peps/pep-0257.html
[2] http://www.python.org/peps/pep-0008.html

[Dan Bishop]

Steven Bethard wrote:

Dan Bishop wrote:

Mike Meyer wrote:

PEP: XXX

I'll be the first to volunteer an implementation.

Very cool. Thanks for the quick work!

For stdlib acceptance, I'd suggest a few cosmetic changes:

No problem.

"""Implementation of rational arithmetic."""

from __future__ import division

import decimal as decimal
import math as _math

def _gcf(a, b):
"""Returns the greatest common factor of a and b."""
a = abs(a)
b = abs(b)
while b:
a, b = b, a % b
return a

class Rational(object):
"""This class provides an exact representation of rational numbers.

All of the standard arithmetic operators are provided. In
mixed-type
expressions, an int or a long can be converted to a Rational
without
loss of precision, and will be done as such.

Rationals can be implicity (using binary operators) or explicity
(using float(x) or x.decimal()) converted to floats or Decimals;
this may cause a loss of precision. The reverse conversions can be
done without loss of precision, and are performed with the
from_exact_float and from_exact decimal static methods. However,
because of rounding error in the original values, this tends to
produce
"ugly" fractions. "Nicer" conversions to Rational can be made with
approx_smallest_denominator or approx_smallest_error.
"""
def __init__(self, numerator, denominator=1):
"""Contructs the Rational object for numerator/denominator."""
if not isinstance(numerator, (int, long)):
raise TypeError('numerator must have integer type')
if not isinstance(denominator, (int, long)):
raise TypeError('denominator must have integer type')
if not denominator:
raise ZeroDivisionError('rational construction')
factor = _gcf(numerator, denominator)
self._n = numerator // factor
self._d = denominator // factor
if self._d < 0:
self._n = -self._n
self._d = -self._d
def __repr__(self):
if self._d == 1:
return "Rational(%d)" % self._n
else:
return "Rational(%d, %d)" % (self._n, self._d)
def __str__(self):
if self._d == 1:
return str(self._n)
else:
return "%d/%d" % (self._n, self._d)
def __hash__(self):
try:
return hash(float(self))
except OverflowError:
return hash(long(self))
def __float__(self):
return self._n / self._d
def __int__(self):
if self._n < 0:
return -int(-self._n // self._d)
else:
return int(self._n // self._d)
def __long__(self):
return long(int(self))
def __nonzero__(self):
return bool(self._n)
def __pos__(self):
return self
def __neg__(self):
return Rational(-self._n, self._d)
def __abs__(self):
if self._n < 0:
return -self
else:
return self
def __add__(self, other):
if isinstance(other, Rational):
return Rational(self._n * other._d + self._d * other._n,
self._d * other._d)
elif isinstance(other, (int, long)):
return Rational(self._n + self._d * other, self._d)
elif isinstance(other, (float, complex)):
return float(self) + other
elif isinstance(other, _decimal.Decimal):
return self.decimal() + other
else:
return NotImplemented
__radd__ = __add__
def __sub__(self, other):
if isinstance(other, Rational):
return Rational(self._n * other._d - self._d * other._n,
self._d * other._d)
elif isinstance(other, (int, long)):
return Rational(self._n - self._d * other, self._d)
elif isinstance(other, (float, complex)):
return float(self) - other
elif isinstance(other, _decimal.Decimal):
return self.decimal() - other
else:
return NotImplemented
def __rsub__(self, other):
if isinstance(other, (int, long)):
return Rational(other * self._d - self._n, self._d)
elif isinstance(other, (float, complex)):
return other - float(self)
elif isinstance(other, _decimal.Decimal):
return other - self.decimal()
else:
return NotImplemented
def __mul__(self, other):
if isinstance(other, Rational):
return Rational(self._n * other._n, self._d * other._d)
elif isinstance(other, (int, long)):
return Rational(self._n * other, self._d)
elif isinstance(other, (float, complex)):
return float(self) * other
elif isinstance(other, _decimal.Decimal):
return self.decimal() * other
else:
return NotImplemented
__rmul__ = __mul__
def __truediv__(self, other):
if isinstance(other, Rational):
return Rational(self._n * other._d, self._d * other._n)
elif isinstance(other, (int, long)):
return Rational(self._n, self._d * other)
elif isinstance(other, (float, complex)):
return float(self) / other
elif isinstance(other, _decimal.Decimal):
return self.decimal() / other
else:
return NotImplemented
__div__ = __truediv__
def __rtruediv__(self, other):
if isinstance(other, (int, long)):
return Rational(other * self._d, self._n)
elif isinstance(other, (float, complex)):
return other / float(self)
elif isinstance(other, _decimal.Decimal):
return other / self.decimal()
else:
return NotImplemented
__rdiv__ = __rtruediv__
def __floordiv__(self, other):
truediv = self / other
if isinstance(truediv, Rational):
return truediv._n // truediv._d
else:
return truediv // 1
def __rfloordiv__(self, other):
return (other / self) // 1
def __mod__(self, other):
return self - self // other * other
def __rmod__(self, other):
return other - other // self * self
def _divmod__(self, other):
return self // other, self % other
def __cmp__(self, other):
if other == 0:
return cmp(self._n, 0)
else:
return cmp(self - other, 0)
def __pow__(self, other):
if isinstance(other, (int, long)):
if other < 0:
return Rational(self._d ** -other, self._n ** -other)
else:
return Rational(self._n ** other, self._d ** other)
else:
return float(self) ** other
def __rpow__(self, other):
return other ** float(self)
def decimal(self):
"""Return a Decimal approximation of self in the current
context."""
return _decimal.Decimal(self._n) / _decimal.Decimal(self._d)
@staticmethod
def from_exact_float(x):
"""Returns the exact Rational equivalent of x."""
mantissa, exponent = _math.frexp(x)
mantissa = int(mantissa * 2 ** 53)
exponent -= 53
if exponent < 0:
return Rational(mantissa, 2 ** (-exponent))
else:
return Rational(mantissa * 2 ** exponent)
@staticmethod
def from_exact_decimal(x):
"""Returns the exact Rational equivalent of x."""
sign, mantissa, exponent = x.as_tuple()
sign = (1, -1)[sign]
mantissa = sign * reduce(lambda a, b: 10 * a + b, mantissa)
if exponent < 0:
return Rational(mantissa, 10 ** (-exponent))
else:
return Rational(mantissa * 10 ** exponent)
@staticmethod
def approx_smallest_denominator(x, tolerance):
"""Returns a Rational approximation of x.
Minimizes the denominator given a constraint on the error.

x = the float or Decimal value to convert
tolerance = maximum absolute error allowed,
must be of the same type as x
"""
tolerance = abs(tolerance)
n = 1
while True:
m = int(round(x * n))
result = Rational(m, n)
if abs(result - x) < tolerance:
return result
n += 1
@staticmethod
def approx_smallest_error(x, maxDenominator):
"""Returns a Rational approximation of x.
Minimizes the error given a constraint on the denominator.

x = the float or Decimal value to convert
maxDenominator = maximum denominator allowed
"""
result = None
minError = x
for n in xrange(1, maxDenominator + 1):
m = int(round(x * n))
r = Rational(m, n)
error = abs(r - x)
if error == 0:
return r
elif error < minError:
result = r
minError = error
return result

def divide(x, y):
"""Same as x/y, but returns a Rational if both are ints."""
if isinstance(x, (int, long)) and isinstance(y, (int, long)):
return Rational(x, y)
else:
return x / y

[Nick Coghlan]

Mike Meyer wrote:

Regarding str() and repr() behaviour, Ka-Ping Yee proposes that repr() have
the same behaviour as str() and Tim Peters proposes that str() behave like the
to-scientific-string operation from the Spec.

This looks like a C & P leftover from the Decimal PEP :)

Otherwise, looks good.

Regards,
Nick.

--
Nick Coghlan | nc******@email.com | Brisbane, Australia
---------------------------------------------------------------
http://boredomandlaziness.skystorm.net

[Nick Coghlan]

Dan Bishop wrote:

Mike Meyer wrote:

This version includes the input from various and sundry people.

Thanks

to everyone who contributed.

<mike

PEP: XXX
Title: A rational number module for Python

...

Implicit Construction
---------------------

When combined with a floating type - either complex or float - or a
decimal type, the result will be a TypeError. The reason for this is
that floating point numbers - including complex - and decimals are
already imprecise. To convert them to rational would give an
incorrect impression that the results of the operation are
precise. The proper way to add a rational to one of these types is to
convert the rational to that type explicitly before doing the
operation.

I disagree with raising a TypeError here. If, in mixed-type
expressions, we treat ints as a special case of rationals, it's
inconsistent for rationals to raise TypeErrors in situations where int
doesn't.

2 + 0.5
2.5
Rational(2) + 0.5

TypeError: unsupported operand types for +: 'Rational' and 'float'

Mike's use of this approach was based on the discussion around PEP 327 (Decimal).

The thing with Decimal and Rational is that they're both about known precision.
For Decimal, the decision was made that any operation that might lose that
precision should never be implicit.

Getting a type error gives the programmer a choice:
1. Take the precision loss in the result, by explicitly converting the Rational
to the imprecise type
2. Explicitly convert the non-Rational input to a Rational before the operation.

Permitting implicit conversion in either direction opens the door to precision
bugs - silent errors that even rigorous unit testing may not detect.

The seemingly benign ability to convert longs to floats implicitly is already a
potential source of precision bugs:

Py> bignum = 2 ** 62
Py> bignum
4611686018427387904L
Py> bignum + 1.0
4.6116860184273879e+018
Py> float(bignum) != bignum + 1.0
False

Cheers,
Nick.

--
Nick Coghlan | nc******@email.com | Brisbane, Australia
---------------------------------------------------------------
http://boredomandlaziness.skystorm.net

[Mike Meyer]

"Dan Bishop" <da*****@yahoo.com> writes:

Mike Meyer wrote:

This version includes the input from various and sundry people. Thanks

to everyone who contributed.

<mike

PEP: XXX
Title: A rational number module for Python

...

Implementation
==============

There is currently a rational module distributed with Python, and a
second rational module in the Python cvs source tree that is not
distributed. While one of these could be chosen and made to conform
to the specification, I am hoping that several people will volunteer
implementatins so that a ''best of breed'' implementation may be
chosen.

I'll be the first to volunteer an implementation.

I've already got two implementations. Both vary from the PEP.
I've made the following deviations from your PEP:

* Binary operators with one Rational operand and one float or Decimal
operand will not raise a TypeError, but return a float or Decimal.
* Expressions of the form Decimal op Rational do not work. This is a
bug in the decimal module.
* The constructor only accepts ints and longs. Conversions from float
or Decimal to Rational can be made with the static methods:
- fromExactFloat: exact conversion from float to Rational
- fromExactDecimal: exact conversion from Decimal to Rational
- approxSmallestDenominator: Minimizes the result's denominator,
given a maximum allowed error.
- approxSmallestError: Minimizes the result's error, given a
maximum allowed denominator.
For example,

Part of finishing the PEP will be modifying the chosen contribution so
that it matches the PEP. As the PEP champion, I'll take that one (and
also write a test module) before submitting the PEP to the pep list
for inclusion and possible finalization.

If you still wish to contribute your code, please mail it to me as an
attachment.

Thanks,
<mike
--
Mike Meyer <mw*@mired.org> http://www.mired.org/home/mwm/
Independent WWW/Perforce/FreeBSD/Unix consultant, email for more information.

[Mike Meyer]

"John Roth" <ne********@jhrothjr.com> writes:

I'd suggest making them public rather than either protected or
private. There's a precident with the complex module, where
the real and imaginary parts are exposed as .real and .imag.

This isn't addressed in the PEP, and is an oversight on my part. I'm
against making them public, as Rational's should be immutable. Making
the two features public invites people to change them, meaning that
machinery has to be put in place to prevent that. That means either
making all attribute access go through __getattribute__ for new-style
classes, or making them old-style classes, which is discouraged.

If the class is reimplented in C, making them read-only attributes as
they are in complex makes sense, and should be considered at that
time.
<mike
--
Mike Meyer <mw*@mired.org> http://www.mired.org/home/mwm/
Independent WWW/Perforce/FreeBSD/Unix consultant, email for more information.

[Mike Meyer]

Nick Coghlan <nc******@iinet.net.au> writes:

Mike Meyer wrote:

Regarding str() and repr() behaviour, Ka-Ping Yee proposes that repr() have
the same behaviour as str() and Tim Peters proposes that str() behave like the
to-scientific-string operation from the Spec.

This looks like a C & P leftover from the Decimal PEP :)

Yup. Thank you. This now reads:

Regarding str() and repr() behaviour, repr() will be either
''rational(num)'' if the denominator is one, or ''rational(num,
denom)'' if the denominator is not one. str() will be either ''num''
if the denominator is one, or ''(num / denom)'' if the denominator is
not one.

Is that acceptable?

<mike
--
Mike Meyer <mw*@mired.org> http://www.mired.org/home/mwm/
Independent WWW/Perforce/FreeBSD/Unix consultant, email for more information.

[Steven Bethard]

Mike Meyer wrote:

"John Roth" <ne********@jhrothjr.com> writes:

I'd suggest making them public rather than either protected or
private. There's a precident with the complex module, where
the real and imaginary parts are exposed as .real and .imag.

This isn't addressed in the PEP, and is an oversight on my part. I'm
against making them public, as Rational's should be immutable. Making
the two features public invites people to change them, meaning that
machinery has to be put in place to prevent that. That means either
making all attribute access go through __getattribute__ for new-style
classes, or making them old-style classes, which is discouraged.

Can't you just use properties?

class Rational(object): .... def num():
.... def get(self):
.... return self._num
.... return dict(fget=get)
.... num = property(**num())
.... def denom():
.... def get(self):
.... return self._denom
.... return dict(fget=get)
.... denom = property(**denom())
.... def __init__(self, num, denom):
.... self._num = num
.... self._denom = denom
.... r = Rational(1, 2)
r.denom 2 r.num 1 r.denom = 2

Traceback (most recent call last):
File "<interactive input>", line 1, in ?
AttributeError: can't set attribute

Steve

[Nick Coghlan]

Mike Meyer wrote:

Yup. Thank you. This now reads:

Regarding str() and repr() behaviour, repr() will be either
''rational(num)'' if the denominator is one, or ''rational(num,
denom)'' if the denominator is not one. str() will be either ''num''
if the denominator is one, or ''(num / denom)'' if the denominator is
not one.

Is that acceptable?

Sounds fine to me.

On the str() front, I was wondering if Rational("x / y") should be an acceptable
string input format.

Cheers,
Nick.

--
Nick Coghlan | nc******@email.com | Brisbane, Australia
---------------------------------------------------------------
http://boredomandlaziness.skystorm.net

[Steve Holden]

Dan Bishop wrote:

Steven Bethard wrote:

Dan Bishop wrote:

Mike Meyer wrote:

PEP: XXX

I'll be the first to volunteer an implementation.

Very cool. Thanks for the quick work!

For stdlib acceptance, I'd suggest a few cosmetic changes:

No problem.

"""Implementation of rational arithmetic."""

[Yards of unusable code]

I'd also request that you change all leading tabs to four spaces!

regards
Steve
--
Steve Holden http://www.holdenweb.com/
Python Web Programming http://pydish.holdenweb.com/
Holden Web LLC [phone] [phone]

[Skip Montanaro]

Mike> ... or making them old-style classes, which is discouraged.

Since when is use of old-style classes discouraged?

Skip

[Steve Holden]

Skip Montanaro wrote:

Mike> ... or making them old-style classes, which is discouraged.

Since when is use of old-style classes discouraged?

Well, since new-style classes came along, surely? I should have thought
the obvious way to move forward was to only use old-style classes when
their incompatible-with-type-based-classes behavior is absolutely required.

Though personally I should have said "use of new-style classes is
encouraged". I agree that there's no real need to change existing code
just for the sake of it, but it would be interesting to see just how
much existing code fails when preceded by the 1.5.2--to-2.4-compatible (?)

__metaclass__ = type

guessing-not-that-much-ly y'rs - steve
--
Steve Holden http://www.holdenweb.com/
Python Web Programming http://pydish.holdenweb.com/
Holden Web LLC [phone] [phone]

[Mike Meyer]

Nick Coghlan <nc******@iinet.net.au> writes:

Mike Meyer wrote:

Yup. Thank you. This now reads:
Regarding str() and repr() behaviour, repr() will be either
''rational(num)'' if the denominator is one, or ''rational(num,
denom)'' if the denominator is not one. str() will be either ''num''
if the denominator is one, or ''(num / denom)'' if the denominator is
not one.
Is that acceptable?

Sounds fine to me.

On the str() front, I was wondering if Rational("x / y") should be an
acceptable string input format.

I don't think so, as I don't see it coming up often enough to warrant
implementing. However, Rational("x" / "y") will be an acceptable
string format as fallout from accepting floating point string
representations.

<mike
--
Mike Meyer <mw*@mired.org> http://www.mired.org/home/mwm/
Independent WWW/Perforce/FreeBSD/Unix consultant, email for more information.

[Mike Meyer]

Skip Montanaro <sk**@pobox.com> writes:

Mike> ... or making them old-style classes, which is discouraged.

Since when is use of old-style classes discouraged?

I was under the imperssion that old-style classes were going away, and
hence discouraged for new library modules.

However, a way to deal with this cleanly has been suggested by Steven
Bethard, so the point is moot for this discussion.

<mike
--
Mike Meyer <mw*@mired.org> http://www.mired.org/home/mwm/
Independent WWW/Perforce/FreeBSD/Unix consultant, email for more information.

[John Roth]

"Mike Meyer" <mw*@mired.org> wrote in message
news:86************@guru.mired.org...

Nick Coghlan <nc******@iinet.net.au> writes:

Mike Meyer wrote:

Yup. Thank you. This now reads:
Regarding str() and repr() behaviour, repr() will be either
''rational(num)'' if the denominator is one, or ''rational(num,
denom)'' if the denominator is not one. str() will be either ''num''
if the denominator is one, or ''(num / denom)'' if the denominator is
not one.
Is that acceptable?
Sounds fine to me.

On the str() front, I was wondering if Rational("x / y") should be an
acceptable string input format.

I don't think so, as I don't see it coming up often enough to warrant
implementing. However, Rational("x" / "y") will be an acceptable
string format as fallout from accepting floating point string
representations.

How would that work? I though the divide would be
evaluated before the function call, resulting in an exception
(strings don't implement the / operator).

John Roth
<mike
--
Mike Meyer <mw*@mired.org> http://www.mired.org/home/mwm/
Independent WWW/Perforce/FreeBSD/Unix consultant, email for more
information.