Continuous fraction (was Re: Decimals to fraction strings)

[Huaiyu Zhu]

Seeing that the thread of fractional representation does not die, I wrote a
little program that will convert between fractions and floats to given
precision (within machine range).  It contains its own test.

"""
Convert between float, continuous fraction and fractions
The optional variable num_term holds the max number of terms.
Todo: Need precision-checking. list[20:] is probably meaningless
"""

def to_float(list):
	"Convert to float from continuous fraction"
	x = 0.
	for i in range(1,len(list)+1):
		x = 1./(list[-i] + x)
	return	1./x

def to_contfrac(x, num_term=20):
	"""Convert to continuous fraction from float
	"""
	list = []
	for i in range(num_term):
		a = int(x)
		list.append(a)
		x = x - a
		if abs(x) < 1e-9: break
		x = 1./x
	return list

def to_frac(list, num_term=4):
	"Convert to fraction from continuous fraction"
	list = list[:num_term]
	x, y = 0, 1L
	for i in range(1,len(list)+1):
		x = x + list[-i]*y
		x, y = y, x
	return	y, x

def test(x, num_term):
	a = to_contfrac(x, num_term);
	print a,  to_float(a)
	for n in range(1, num_term):
		b = to_frac(a, n)
		print "%25s	 %.16f" % (b, b[0]/float(b[1]))
	print "-"*40
	
if __name__ == "__main__":
	test(0.6667, 7)
	from math import pi
	test(pi, 16)

-- 
Huaiyu Zhu                               hzhu at knowledgetrack.com
KnowledgeTrack Corporation               Tel: 925 738 1907
7020 Koll Center Parkway, Suite 110      Fax: 925 738 1039
Pleasanton, CA 94566