[Batista, Facundo]
> To convert a Decimal to Rational, [...]
Hi, people. I am not closely following this thread and do not know if this
has been discussed before. Sorry if I'm repeating known arguments...
Decimal to Rational is easy. The interesting problem is how to best
convert a float to Rational. For example, do we want pi (3.1415926...)
converted as 3, 22/7 or 355/113? This pretty much depends of the error
we are ready to tolerate. We do not always want a hairy Rational.
Given a tolerance, the question is to find the "simplest" Rational
corresponding to a float. I once needed to solve that particular
problem, and gave myself a Rational type merely (I called it Fraction).
Let me append it here, in case it could be useful to your project. If
you provide the constructor with a float and no tolerance, it should yield
the best possible Rational for the float representation on that machine.
--
François Pinard http://pinard.progiciels-bpi.ca
#!/usr/bin/env python
# Copyright ï 2000 Progiciels Bourbeau-Pinard inc.
# Franïois Pinard <[EMAIL PROTECTED]>, 2000.
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)
--
http://mail.python.org/mailman/listinfo/python-list
