Decimals -> Fraction strings, my solution

[Michael Hudson]

=?ISO-8859-1?Q?Fran=E7ois_Pinard?= <pinard at iro.umontreal.ca> writes:

> 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.

You have the right approach (continued fractions), but you're
implementation is more complex than it needs to be.  As it happens,
I've just handed in a computer project on continued fractions so,
after a bit of translation (I originally wrote this stuff in lisp),
here it is.

# copied from /usr/lib/gcc-lib/i686-pc-linux-gnu/2.95.2/include/float.h
epsilon = 2.2204460492503131e-16

def cfrac(x,err=0.0):
    result = []
    err = err + epsilon
    while 1:
        a,b = divmod(x, 1.0)
        result.append( int(a) )
        if not b:
            return result
        err = err / (b * (b + err))
        if err > b:
            return result
        x = 1 / b

def converge(partials):
    p_1, q_1, p, q = 0, 1, 1, 0
    result = []
    for a in partials:
        p_1, q_1, p, q = p,q, a*p+p_1, a*q+q_1
        result.append( (p,q) )
    return result

Justifying all that requires significant time with a pencil, so I'll
leave that as an excercise for the reader.  However:

>>> cfrac.converge(cfrac.cfrac(math.pi))
[(3, 1), (22, 7), (333, 106), (355, 113), (103993, 33102), (104348,
33215), (208341, 66317), (312689, 99532), (833719, 265381), (1146408,
364913), (4272943, 1360120), (5419351, 1725033)]

Same numbers as before, but rather less effort to get them, I think.

Also:

>>> cfrac.converge(cfrac.cfrac(float("0.3333333333333333333333")))
[(0, 1), (1, 3)]

continued-fractions-are-almost-like-magic-ly y'rs
Michael

-- 
81. In computing, turning the obvious into the useful is a living
    definition of the word "frustration".
     -- Alan Perlis, http://www.cs.yale.edu/~perlis-alan/quotes.html