Decimals -> Fraction strings, my solution

[François Pinard]

kain at cableadmin.com (Scott) writes:

> I've come up with one solution to my problem.  Its probably quite
> inefficient, but it does what I need for now.  Feel free to
> tear it apart and/or give any advice on how to better implement it.

OK, taken!  As a kind of rest, I tried to do it as well, as I was teased
by the fact your solution limits the denominator to be 2**N * 5**M.

> This code will take either a number or a string (ie '0.5') and return
> a string of the fraction (ie '1/2').  Here it is:

The code below defines `fraction(VALUE, TOLERANCE)', and return a string
representing the "simplest" fraction approximating VALUE, a float, with
an error not exceeding TOLERANCE, also a float which should not be too
close to zero (or else, the task may become impossible to achieve).

The value of `pi' was approximated by 3 in old times.  We often used 22:7
in school, probably you did that as well.  I later learned that 355:113
was a more precise approximation, and an easy one to remember.  We can
find all these values with `fraction'!   See:


>>> fraction(3.14159265359, 1)
'3:1'
>>> fraction(3.14159265359, 0.1)
'22:7'
>>> fraction(3.14159265359, 0.01)
'22:7'
>>> fraction(3.14159265359, 0.001)
'333:106'
>>> fraction(3.14159265359, 0.0001)
'333:106'
>>> fraction(3.14159265359, 0.00001)
'355:113'
>>> fraction(3.14159265359, 0.000001)
'355:113'
>>> fraction(3.14159265359, 0.0000001)
'103993:33102'
>>> fraction(3.14159265359, 0.00000001)
'103993:33102'
>>> fraction(3.14159265359, 0.000000001)
'103993:33102'
>>> fraction(3.14159265359, 0.0000000001)
'312689:99532'
>>> fraction(3.14159265359, 0.00000000001)
'833719:265381'

Here is the code, which is rather short, after all.  You may even delete
`__repr__' to make it shorter, but it makes debugging fun.  For example:

>>> ContinuedFraction(3.14159265359, 0.00000000001)
3+1/(7+1/(15+1/(1+1/(292+1/(1+1/(1+1/(1+1/(2))))))))

I do not think GCD is necessary, but I did not prove this to myself.
Also, the continued fraction may sometimes start with `0+' which can be
simplified out, but it was not worth doing in this given application.



def fraction(value, tolerance=0):
    return '%d:%d' % ContinuedFraction(value, tolerance).eval()

class ContinuedFraction:

    def __init__(self, value, tolerance):
        integer = int(value)
        residual = value - integer
        self.integers = [integer]
        while residual != 0 and abs(value - float(self)) > tolerance:
            residual = 1.0 / 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 __float__(self):
        num, den = self.eval()
        return float(num) / float(den)

    def eval(self):
        num, den = 1, 0
        for integer in self.integers:
            num, den = integer * num + den, num
        return num, den

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