Velocity Reviews > A Revised Rational Proposal

# A Revised Rational Proposal

Mike Meyer
Guest
Posts: n/a

 12-26-2004
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 <(E-Mail Removed)>
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 <(E-Mail Removed)> http://www.mired.org/home/mwm/
Independent WWW/Perforce/FreeBSD/Unix consultant, email for more information.

Dan Bishop
Guest
Posts: n/a

 12-26-2004
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
Guest
Posts: n/a

 12-26-2004

"Dan Bishop" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) 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
Guest
Posts: n/a

 12-26-2004

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
Guest
Posts: n/a

 12-26-2004
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
Guest
Posts: n/a

 12-26-2004
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
Guest
Posts: n/a

 12-26-2004

"Steven Bethard" <(E-Mail Removed)> 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
Guest
Posts: n/a

 12-26-2004

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
Guest
Posts: n/a

 12-27-2004

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 | http://www.velocityreviews.com/forums/(E-Mail Removed) | Brisbane, Australia
---------------------------------------------------------------
http://boredomandlaziness.skystorm.net

Nick Coghlan
Guest
Posts: n/a

 12-27-2004
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 | (E-Mail Removed) | Brisbane, Australia
---------------------------------------------------------------
http://boredomandlaziness.skystorm.net

 Thread Tools

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post opalpa@gmail.com opalinski from opalpaweb Java 2 03-16-2006 07:12 PM Mike Meyer Python 21 12-23-2004 07:17 AM Jp Calderone Python 1 12-18-2004 07:19 PM newtohtml@att.net HTML 1 07-19-2004 01:36 PM TechGeekPro MCSE 26 06-29-2004 06:01 AM

Advertisments