Continued Fraction to Fraction Malfunction

Question

I've been working on Project euler Problem 57 (Love the site!). For this problem a conversion is required between a finite continued fraction and a normal fraction. I devised an algorithm that basically takes the inverse of the last number in a list, add it to the next-to-last and continues until the final fraction remains. For problem 67 it worked maverlously, but this time it stops working after the second iteration (I have to perform the algorithm on multiple continued fractions).

This is the piece of code (I used an external module, namely sympy):

import time
from sympy import *
from sympy import fraction, Rational, Symbol

def cont_fract_to_fraction(cont_frac_list):
    a=cont_frac_list[-1]
    b=cont_frac_list[-2]
    new_reduced=Rational(b,1)+ Rational(1,a)
    cont_frac_list[-2]=new_reduced
    del cont_frac_list[-1]
    if len(cont_frac_list)==1:
        print cont_frac_list #To check
        return cont_frac_list
    else:
        cont_fract_to_fraction(cont_frac_list)

def numerator_higher_denominator(fraction):
    num=str(fraction[0])
    den=str(fraction[1])
    if len(num)>len(den):
        return 1
    else:
        return 0

start=time.time()

tally=0

for k in xrange (1, 101):
    sqrt_eval=[1]
    for x in xrange (1, k+2):
        sqrt_eval.append(2)
    sqrt_eval=cont_fract_to_fraction(sqrt_eval)
    print sqrt_eval ##To double check
    #fraction_result=fraction(soln[0]) To introduce later
    #tally+=numerator_higher_denominator(fraction_result) To introduce later

elapsed=time.time()-start

print "Solution: ", tally, "Solved in: ", elapsed

I basically test just to see if it gets all the final fraction and the print from the function, before the return, gives the answer, but the print after I assigned the value to sqrt_eval prints None. Here is a test run:

###Test run####
[3/2] #--> function print
[3/2] #--> sqrt_eval print
[7/5]
None
[17/12]
None
[41/29]
None
[99/70]
None
[239/169]
None
[577/408]
None
[1393/985]
None
[3363/2378]
None
[8119/5741]
None
[19601/13860]
None

I've been searching thouroughly for an answer and can't quite find one. Help me debug this, if you can, without altering the code much.

Answer 1

The fractions module makes short work of this problem:

>>> from fractions import Fraction
>>> def normal_fraction(continued_fraction):
         n = Fraction(0)
         for d in continued_fraction[:0:-1]:
             n = 1 / (d + n)
         return continued_fraction[0] + n

>>> cf = [3,7,15,1,292,1,1,1,2,1,3,1]
>>> normal_fraction(cf)
Fraction(5419351, 1725033)
>>> float(_)
3.1415926535898153

If you like functional programming and concise code, the above logic can be expressed in a one-liner using reduce():

>>> cf[0] + reduce(lambda d, n: 1 / (d + n), cf[:0:-1], Fraction(0))
Fraction(5419351, 1725033)

And here is a version that doesn't use Fraction. It will work even on very old versions of Python:

def normal_fraction(continued_fraction):
    n, d = 0, 1
    for a in continued_fraction[:0:-1]:
        n, d = d, a*d + n
    return continued_fraction[0]*d + n, d

Answer 2

This doesn't answer your question, but there are some formulas on Wikipedia that might let you compute this more efficiently.