Float compression [Re: floating point math results question]
François Pinard
pinard at iro.umontreal.ca
Sun Jan 27 13:24:43 EST 2002
[Jonathan Hogg]
> > I may send you the one I have, just ask! :-)
> I posted with the sure and certain knowledge that someone somewhere has
> implemented a rational class for Python, probably multiple versions ;-)
Since my module is about 140 lines, let me post it here!
def Fraction(num, den=1, tolerance=0):
"""\
Return the _simplest_ fraction approximating NUM/DEN, given that the
approximation error may not exceed TOLERANCE. The returned fraction
has a special type which may be used in later numeric computations.
"""
if type(0.) in (type(num), type(den)):
num, den = num/den, 1L
while long(num) != num:
num, den = 2.*num, 2L*den
num = long(num)
elif den < 0:
num = -num
den = -den
d = gcd(abs(num), den)
value = SimplifiedFraction(num/d, den/d)
if tolerance > 0:
value = ContinuedFraction(value, tolerance).simplify()
return value
class SimplifiedFraction:
triples = 0 # set to 1 for a:b:c printing
def __init__(self, num, den):
self.num = num
self.den = den
def __repr__(self):
num = self.num
den = self.den
if den == 1:
return '%.f' % num
if self.triples:
if num > 0 and num > den:
return '%.f:%.f:%.f' % (num / den, num % den, den)
if num < 0 and -num > den:
return '-%.f:%.f:%.f' % (-num / den, -num % den, den)
return '%.f:%.f' % (num, den)
def __coerce__(self, other):
if isinstance(other, SimplifiedFraction):
return self, other
if type(other) in (type(0), type(0L)):
return self, SimplifiedFraction(other, 1)
if type(other) is type(0.):
return float(self), other
def __int__(self):
if self.num < 0:
return -(-self.num / self.den)
return self.num / self.den
def __float__(self):
return float(self.num) / float(self.den)
def __neg__(self): return SimplifiedFraction(-self.num, self.den)
def __pos__(self): return self
def __abs__(self): return SimplifiedFraction(abs(self.num), self.den)
def __cmp__(self, other):
d = gcd(self.den, other.den)
if d == 1:
return cmp(self.num*other.den, other.num*self.den)
return cmp(self.num*(other.den/d), other.num*(self.den/d))
def __add__(self, other):
d1 = gcd(self.den, other.den)
if d1 == 1:
return SimplifiedFraction(self.num*other.den + other.num*self.den,
self.den*other.den)
t = self.num*(other.den/d1) + other.num*(self.den/d1)
d2 = gcd(t, d1)
return SimplifiedFraction(t/d2, (self.den/d1) * (other.den/d2))
def __sub__(self, other):
d1 = gcd(self.den, other.den)
if d1 == 1:
return SimplifiedFraction(self.num*other.den - other.num*self.den,
self.den*other.den)
t = self.num*(other.den/d1) - other.num*(self.den/d1)
d2 = gcd(t, d1)
return SimplifiedFraction(t/d2, (self.den/d1) * (other.den/d2))
def __mul__(self, other):
d1 = gcd(self.num, other.den)
d2 = gcd(self.den, other.num)
return SimplifiedFraction((self.num/d1) * (other.num/d2),
(self.den/d2) * (other.den/d1))
def __div__(self, other):
d1 = gcd(self.num, other.num)
d2 = gcd(self.den, other.den)
return SimplifiedFraction((self.num/d1) * (other.den/d2),
(self.den/d2) * (other.num/d1))
def __radd__(self, other): return other.__add__(self)
def __rsub__(self, other): return other.__sub__(self)
def __rmul__(self, other): return other.__mul__(self)
def __rdiv__(self, other): return other.__div__(self)
def gcd(a, b):
while b:
a, b = b, a % b
return a
class ContinuedFraction:
def __init__(self, value, tolerance):
integer = int(value)
residual = value - integer
self.integers = [integer]
while residual != 0 and abs(value - self.simplify()) > tolerance:
residual = 1 / residual
integer = int(residual)
residual = residual - integer
self.integers.insert(0, integer)
def __repr__(self):
import string
text = map(str, self.integers)
text.reverse()
return string.join(text, '+1/(') + ')' * (len(self.integers) - 1)
def simplify(self):
num, den = 1, 0
for integer in self.integers:
num, den = integer * num + den, num
# gcd is not necessary. Tim says: for adjacent pairs a:b, c:d in
# a cf expansion, a*d - b*c alternates between +1 and -1, which
# is an easy inductive proof (provided you start with two for
# which this is true, as is the case for the usual starting pair
# 0/1 and 1/0). So anything dividing both a and b (or c and d)
# divides a*d - b*c = 1 too, so they're relatively prime.
return SimplifiedFraction(num, den)
--
François Pinard http://www.iro.umontreal.ca/~pinard
More information about the Python-list
mailing list