A Revised Rational Proposal

[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