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.or g>
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.pytho n 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.1000000000000 001 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("%.2 f" % 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 InvalidOperatio n 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.or g> 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******** *************@c 13g2000cwb.goog legroups.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
- fromExactDecima l: exact conversion from Decimal to Rational
- approxSmallestD enominator: Minimizes the result's denominator,
given a maximum allowed error.
- approxSmallestE rror: Minimizes the result's error, given a
maximum allowed denominator.
For example,

Rational.fromEx actFloat(math.p i) Rational(884279 719003555, 281474976710656 ) decimalPi = Decimal("3.1415 926535897932384 62643383")
Rational.fromEx actDecimal(deci malPi) Rational(314159 265358979323846 2643383, 100000000000000 0000000000000) Rational.approx SmallestDenomin ator(math.pi, 0.01) Rational(22, 7) Rational.approx SmallestDenomin ator(math.pi, 0.001) Rational(201, 64) Rational.approx SmallestDenomin ator(math.pi, 0.0001) Rational(333, 106) Rational.approx SmallestError(m ath.pi, 10) Rational(22, 7) Rational.approx SmallestError(m ath.pi, 100) Rational(311, 99) Rational.approx SmallestError(m ath.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(nume rator, (int, long)):
raise TypeError('nume rator must have integer type')
if not isinstance(deno minator, (int, long)):
raise TypeError('deno minator must have integer type')
if not denominator:
raise ZeroDivisionErr or('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__(sel f):
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(othe r, Rational):
return Rational(self._ _n * other.__d + self.__d * other.__n,
self.__d * other.__d)
elif isinstance(othe r, (int, long)):
return Rational(self._ _n + self.__d * other, self.__d)
elif isinstance(othe r, (float, complex)):
return float(self) + other
elif isinstance(othe r, decimal.Decimal ):
return self.decimal() + other
else:
return NotImplemented
__radd__ = __add__
def __sub__(self, other):
if isinstance(othe r, Rational):
return Rational(self._ _n * other.__d - self.__d * other.__n,
self.__d * other.__d)
elif isinstance(othe r, (int, long)):
return Rational(self._ _n - self.__d * other, self.__d)
elif isinstance(othe r, (float, complex)):
return float(self) - other
elif isinstance(othe r, decimal.Decimal ):
return self.decimal() - other
else:
return NotImplemented
def __rsub__(self, other):
if isinstance(othe r, (int, long)):
return Rational(other * self.__d - self.__n, self.__d)
elif isinstance(othe r, (float, complex)):
return other - float(self)
elif isinstance(othe r, decimal.Decimal ):
return other - self.decimal()
else:
return NotImplemented
def __mul__(self, other):
if isinstance(othe r, Rational):
return Rational(self._ _n * other.__n, self.__d * other.__d)
elif isinstance(othe r, (int, long)):
return Rational(self._ _n * other, self.__d)
elif isinstance(othe r, (float, complex)):
return float(self) * other
elif isinstance(othe r, decimal.Decimal ):
return self.decimal() * other
else:
return NotImplemented
__rmul__ = __mul__
def __truediv__(sel f, other):
if isinstance(othe r, Rational):
return Rational(self._ _n * other.__d, self.__d * other.__n)
elif isinstance(othe r, (int, long)):
return Rational(self._ _n, self.__d * other)
elif isinstance(othe r, (float, complex)):
return float(self) / other
elif isinstance(othe r, decimal.Decimal ):
return self.decimal() / other
else:
return NotImplemented
__div__ = __truediv__
def __rtruediv__(se lf, other):
if isinstance(othe r, (int, long)):
return Rational(other * self.__d, self.__n)
elif isinstance(othe r, (float, complex)):
return other / float(self)
elif isinstance(othe r, decimal.Decimal ):
return other / self.decimal()
else:
return NotImplemented
__rdiv__ = __rtruediv__
def __floordiv__(se lf, other):
truediv = self / other
if isinstance(true div, Rational):
return truediv.__n // truediv.__d
else:
return truediv // 1
def __rfloordiv__(s elf, 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(othe r, (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(mantis sa, 2 ** (-exponent))
else:
return Rational(mantis sa * 2 ** exponent)
@staticmethod
def fromExactDecima l(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(mantis sa, 10 ** (-exponent))
else:
return Rational(mantis sa * 10 ** exponent)
@staticmethod
def approxSmallestD enominator(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 approxSmallestE rror(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(nume rator, (int, long)):
{indent 3}raise TypeError('nume rator must have integer type')
{indent 2}if not isinstance(deno minator, (int, long)):
{indent 3}raise TypeError('deno minator must have integer type')
{indent 2}if not denominator:
{indent 3}raise ZeroDivisionErr or('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__(sel f):
{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(othe r, Rational):
{indent 3}return Rational(self._ _n * other.__d + self.__d * other.__n,
self.__d * other.__d)
{indent 2}elif isinstance(othe r, (int, long)):
{indent 3}return Rational(self._ _n + self.__d * other, self.__d)
{indent 2}elif isinstance(othe r, (float, complex)):
{indent 3}return float(self) + other
{indent 2}elif isinstance(othe r, 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(othe r, Rational):
{indent 3}return Rational(self._ _n * other.__d - self.__d * other.__n,
self.__d * other.__d)
{indent 2}elif isinstance(othe r, (int, long)):
{indent 3}return Rational(self._ _n - self.__d * other, self.__d)
{indent 2}elif isinstance(othe r, (float, complex)):
{indent 3}return float(self) - other
{indent 2}elif isinstance(othe r, 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(othe r, (int, long)):
{indent 3}return Rational(other * self.__d - self.__n, self.__d)
{indent 2}elif isinstance(othe r, (float, complex)):
{indent 3}return other - float(self)
{indent 2}elif isinstance(othe r, 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(othe r, Rational):
{indent 3}return Rational(self._ _n * other.__n, self.__d * other.__d)
{indent 2}elif isinstance(othe r, (int, long)):
{indent 3}return Rational(self._ _n * other, self.__d)
{indent 2}elif isinstance(othe r, (float, complex)):
{indent 3}return float(self) * other
{indent 2}elif isinstance(othe r, decimal.Decimal ):
{indent 3}return self.decimal() * other
{indent 2}else:
{indent 3}return NotImplemented
{indent 1}__rmul__ = __mul__
{indent 1}def __truediv__(sel f, other):
{indent 2}if isinstance(othe r, Rational):
{indent 3}return Rational(self._ _n * other.__d, self.__d * other.__n)
{indent 2}elif isinstance(othe r, (int, long)):
{indent 3}return Rational(self._ _n, self.__d * other){indent 2}
{indent 2}elif isinstance(othe r, (float, complex)):
{indent 3}return float(self) / other
{indent 2}elif isinstance(othe r, decimal.Decimal ):
{indent 3}return self.decimal() / other
{indent 2}else:
{indent 3}return NotImplemented
{indent 1}__div__ = __truediv__
{indent 1}def __rtruediv__(se lf, other):
{indent 2}if isinstance(othe r, (int, long)):
{indent 3}return Rational(other * self.__d, self.__n)
{indent 2}elif isinstance(othe r, (float, complex)):
{indent 3}return other / float(self)
{indent 2}elif isinstance(othe r, decimal.Decimal ):
{indent 3}return other / self.decimal()
{indent 2}else:
{indent 3}return NotImplemented
{indent 1}__rdiv__ = __rtruediv__
{indent 1}def __floordiv__(se lf, other):
{indent 2}truediv = self / other
{indent 2}if isinstance(true div, Rational):
{indent 3}return truediv.__n // truediv.__d
{indent 2}else:
{indent 3}return truediv // 1
{indent 1}def __rfloordiv__(s elf, 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(othe r, (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(mantis sa, 2 ** (-exponent))
{indent 2}else:
{indent 3}return Rational(mantis sa * 2 ** exponent)
{indent 1}@staticmethod
{indent 1}def fromExactDecima l(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(mantis sa, 10 ** (-exponent))
{indent 2}else:
{indent 3}return Rational(mantis sa * 10 ** exponent)
{indent 1}@staticmethod
{indent 1}def approxSmallestD enominator(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 approxSmallestE rror(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_floa t,
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.1945 8$k25.5585@attb i_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_floa t,
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.

"""Implementati on 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_floa t 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):
"""Contruct s the Rational object for numerator/denominator."""
if not isinstance(nume rator, (int, long)):
raise TypeError('nume rator must have integer type')
if not isinstance(deno minator, (int, long)):
raise TypeError('deno minator must have integer type')
if not denominator:
raise ZeroDivisionErr or('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__(sel f):
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(othe r, Rational):
return Rational(self._ n * other._d + self._d * other._n,
self._d * other._d)
elif isinstance(othe r, (int, long)):
return Rational(self._ n + self._d * other, self._d)
elif isinstance(othe r, (float, complex)):
return float(self) + other
elif isinstance(othe r, _decimal.Decima l):
return self.decimal() + other
else:
return NotImplemented
__radd__ = __add__
def __sub__(self, other):
if isinstance(othe r, Rational):
return Rational(self._ n * other._d - self._d * other._n,
self._d * other._d)
elif isinstance(othe r, (int, long)):
return Rational(self._ n - self._d * other, self._d)
elif isinstance(othe r, (float, complex)):
return float(self) - other
elif isinstance(othe r, _decimal.Decima l):
return self.decimal() - other
else:
return NotImplemented
def __rsub__(self, other):
if isinstance(othe r, (int, long)):
return Rational(other * self._d - self._n, self._d)
elif isinstance(othe r, (float, complex)):
return other - float(self)
elif isinstance(othe r, _decimal.Decima l):
return other - self.decimal()
else:
return NotImplemented
def __mul__(self, other):
if isinstance(othe r, Rational):
return Rational(self._ n * other._n, self._d * other._d)
elif isinstance(othe r, (int, long)):
return Rational(self._ n * other, self._d)
elif isinstance(othe r, (float, complex)):
return float(self) * other
elif isinstance(othe r, _decimal.Decima l):
return self.decimal() * other
else:
return NotImplemented
__rmul__ = __mul__
def __truediv__(sel f, other):
if isinstance(othe r, Rational):
return Rational(self._ n * other._d, self._d * other._n)
elif isinstance(othe r, (int, long)):
return Rational(self._ n, self._d * other)
elif isinstance(othe r, (float, complex)):
return float(self) / other
elif isinstance(othe r, _decimal.Decima l):
return self.decimal() / other
else:
return NotImplemented
__div__ = __truediv__
def __rtruediv__(se lf, other):
if isinstance(othe r, (int, long)):
return Rational(other * self._d, self._n)
elif isinstance(othe r, (float, complex)):
return other / float(self)
elif isinstance(othe r, _decimal.Decima l):
return other / self.decimal()
else:
return NotImplemented
__rdiv__ = __rtruediv__
def __floordiv__(se lf, other):
truediv = self / other
if isinstance(true div, Rational):
return truediv._n // truediv._d
else:
return truediv // 1
def __rfloordiv__(s elf, 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(othe r, (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.Decima l(self._n) / _decimal.Decima l(self._d)
@staticmethod
def from_exact_floa t(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(mantis sa, 2 ** (-exponent))
else:
return Rational(mantis sa * 2 ** exponent)
@staticmethod
def from_exact_deci mal(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(mantis sa, 10 ** (-exponent))
else:
return Rational(mantis sa * 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
461168601842738 7904L
Py> bignum + 1.0
4.6116860184273 879e+018
Py> float(bignum) != bignum + 1.0
False

Cheers,
Nick.

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