Decimals -> Fraction strings, my solution

[François Pinard]

"Tim Peters" <tim_one at email.msn.com> écrit:

> > ...
> >             residual = 1.0 / residual

> Note that this step can introduce a small error on each iteration, due
> to the vagaries of floating-point arithmetic.  To do this with complete
> accuracy requires sticking to rational arithmetic throughout.

I understand, Tim.  I revised my suggested solution according to this
remark, to get what follows.  A bit sadly, the code gets much longer,
and more intricate.  I'm not fully satisfied, yet it seems to work!

>>> Fraction(math.pi, tolerance=1e-5)
355:113

At least, doing this, I learned many useful things about Python. :-)



def Fraction(num, den=1, tolerance=0):
    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
        return SimplifiedFraction(num, den)

-- 
François Pinard   http://www.iro.umontreal.ca/~pinard