A Revised Rational Proposal

[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