"""Rational numbers. rational -------- A function to construct rational numbers, with signature rational(n, d=1). Unless both n and d are integers, longs, or rationals, the result is undefined (although the result of "print rational(1.5)" may be "3.0/2.0" this should not be relied on). The resulting value is of a numeric type with the semantics of an unboundedly precise rational number, as described in PEP 239. gcd --- A function for computing the greatest common denominator. Extensions to PEP 239 --------------------- * A hash function has been added, which guarantees that n/1 hashes to the same value as n (handy for dictionaries). * The numerator has a default (0), to match other numeric types. * The invert operator (~) inverts the fraction. * Ints and longs can be coerced to rationals; otherwise, rationals are coerced to floats. * Includes 1/0, -1/0, and 0/0 as infinity, negative infinity, and NaN values. All NaN's are equal to each other, but not less than or greater than or equal to anything else. All infinities (of the same sign) are equal. * The attributes can be referred to by num and den as well as numerator and denominator. Differences from PEP 239 ------------------------ * The type returned by rational is rational, not RationalType. * The .trim method may not or may not be the same as defined in the PEP. * Because rational literals (PEP 240) are not implemented, the repr for rational numbers is rational(num, den). Open issues in PEP 239 ---------------------- * The type name is rational, not rat. * Rational numbers are not usable as sequence indices. * Shift operators are allowed, but mask operators are not (nor are bitwise logical operators). * Ints are not unified with rationals. Other issues ------------ * There is no facility to convert strings ("1/2") to rationals. * Infinite/NaN arithmetic should match IEEE floats, but may not. * Because of the way cmp(x,y) works in python 2.2, it will return incorrect values (e.g., cmp(2, rational(0/0)) == -1). However, the direct comparison operators will all work properly. Example ------- >>> from rational import rational >>> r = rational(2, 3) >>> r /= 10 >>> print r 1/15 """ # rational.py version 0.1 # Written 24 June 2003 by andi payn <payn@myrealbox.com> # This work is released under the LGPL, version 2.1 or later def gcd(m, n): "Returns the greatest common denominator of its arguments." if m % n == 0: return n else: return gcd(n, m % n) class rational(object): """An unboundedly-precise rational type, as described in PEP 239. rational(num, den) -> rational number Create a rational number from a numerator and an optional denominator, equal to (numerator / denominator), where denominator defaults to 1. The result is only defined for exact types (integers, longs, and rationals); for inexact types the results will often be surprising (e.g., rational(1.5) may be "3.0/2.0" but rational(1.1) may be "2.47697979505e+15/2.25179981369e+15"). """ def __init__(self, num=0, den=1): if isinstance(num, rational) and isinstance(den, rational): self.num, self.den = num.num * den.den, num.den * den.num elif isinstance(num, rational): self.num, self.den = num.num, num.den * den elif isinstance(den, rational): self.num, self.den = num * den.den, den.num else: self.num, self.den = num, den self.__simplify_() def __simplify_(self): if self.den == 0: self.num = cmp(self.num, 0) else: g = gcd(self.num, self.den) self.num /= g self.den /= g return self def __getattr__(self, name): if name == 'numerator': return self.num elif name == 'denominator': return self.den def __setattr__(self, name, value): if name == 'numerator': name = 'num' elif name == 'denominator': name = 'den' self.__dict__[name] = value def __str__(self): if self.den == 1: return str(self.num) else: return str(self.num) + "/" + str(self.den) def __repr__(self): return "rational(" + str(self.num) + "," + str(self.den) + ")" def __pos__(self): return self def __neg__(self): return rational(-self.num, self.den) def __add__(self, other): if not isinstance(other, rational): other = rational(other) if self.isinfinity() and other.isinfinity(): return rational(self.num + other.num, 0) return rational(self.num*other.den + self.den*other.num, self.den*other.den) __radd__ = __add__ def __iadd__(self, other): self = self + other; return self def __sub__(self, other): return self + -other def __rsub__(self, other): return -self + other def __isub__(self, other): self = self - other; return self def __invert__(self): return rational(self.den, self.num) def __mul__(self, other): if not isinstance(other, rational): other = rational(other) return rational(self.num*other.num, self.den*other.den) __rmul__ = __mul__ def __imul__(self, other): self = self * other; return self def __div__(self, other): if not isinstance(other, rational): other = rational(other) return self * ~other __truediv__ = __div__ def __rdiv__(self, other): return ~self * other __rtruediv__ = __rdiv__ def __idiv__(self, other): self = self / other; return self __itruediv__ = __idiv__ def __floordiv__(self, other): return int(self/other) def __rfloordiv__(self, other): return int(other/self) def __ifloordiv__(self, other): self = self // other; return self def __mod__(self, other): if other == 0: return rational(1,0) return self - int(self/other) * other def __rmod__(self, other): return other.__mod__(self) def __imod__(self, other): self = self % mod; return self def __divmod__(self, other): return self//other, self%other def __rdivmod__(self, other): return divmod(other, self) def __lshift__(self, other): return rational(self.num << other, self.den) def __ilshift__(self, other): self = self << other; return self def __rshift__(self, other): return rational(self.num, self.den << other) def __irshift__(self, other): self = self >> other; return self def __pow__(self, other, modulo=None): if isinstance(other, rational): if (other.den != 1): return pow(float(self), float(other), modulo) else: other = int(other) if modulo: return rational(self.num ** other, self.den ** other) % modulo return rational(self.num ** other, self.den ** other) def __rpow__(self, other, modulo=None): if (self.den == 1): return pow(other, int(self), modulo) else: return pow(other, float(self), modulo) def __ipow__(self, other, modulo=None): self = self.__pow__(other, modulo); return self def __cmp__(self, other): if not isinstance(other, rational): other = rational(other) if self.isnan() and not other.isnan(): return NotImplemented elif not self.isnan() and other.isnan(): return NotImplemented else: return self.num * other.den - other.num * self.den def __eq__(self, other): return self.__cmp__(other) == 0 def __ne__(self, other): return self.__cmp__(other) != 0 def __lt__(self, other): if not isinstance(other, rational): other = rational(other) if self.isnan() or other.isnan(): return 0 else: return self.__cmp__(other) < 0 def __gt__(self, other): if not isinstance(other, rational): other = rational(other) if self.isnan() or other.isnan(): return 0 else: return self.__cmp__(other) > 0 def __le__(self, other): if not isinstance(other, rational): other = rational(other) if self.isnan() and other.isnan(): return 1 elif self.isnan() or other.isnan(): return 0 else: return self.__cmp__(other) < 0 def __ge__(self, other): if not isinstance(other, rational): other = rational(other) if self.isnan() and other.isnan(): return 1 elif self.isnan() or other.isnan(): return 0 else: return self.__cmp__(other) > 0 def __nonzero__(self): return self.num != 0 or self.den == 0 def isinfinity(self): return self.num != 0 and self.den == 0 def isnan(self): return self.num == 0 and self.den == 0 def __float__(self): if self.den == 0: return float(1e30000) * self.num else: return float(self.num) / self.den def __int__(self): return int(self.num//self.den) def __long__(self): return long(self.num//self.den) def __coerce__(self, other): if isinstance(other, rational): return self, other elif isinstance(other, (int, long)): return self, rational(other) elif isinstance(other, type(None)): return self, None else: if self.den == 0: return int(self).__coerce__(other) else: return float(self).__coerce__(other) def __abs__(self): return rational(abs(self.num), self.den) def __hash__(self): return hash(self.num * self.den + self.den - 1) def __oct__(self): if self.den == 1: return oct(self.num) else: return oct(self.num) + "/" + oct(self.den) def __hex__(self): if self.den == 1: return hex(self.num) else: return hex(self.num) + "/" + hex(self.den) def issimpler(self, other): return self.num <= other.num and self.den <= other.den and self != other # This algorithm is borrowed from Scheme's "rationalize" function. def __simplest_(self, other): if int(self) >= self: return rational(int(self)) elif int(self) == int(other): rat = (~(other-int(other))).__simplest_(~(self-int(self))) return rational(rat.den + int(self) * rat.num, rat.num) else: return rational(int(self) + 1, 1) def __find_ratio_between_(self, other): if other < self: return other.__find_ratio_between_(self) elif other == self: return other elif self < 0: return -(other.__find_ratio_between_(-self)) else: return self.__simplest_(other) def trim(self, max_den): return int(self) + (self-int(self)).__find_ratio_between_(rational(1, max_den))