A rational proposal

[François Pinard]

[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
-------------- next part --------------
#!/usr/bin/env python
# Copyright ? 2000 Progiciels Bourbeau-Pinard inc.
# Fran?ois Pinard <pinard at iro.umontreal.ca>, 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)