#!/usr/bin/python """Simple continued-fraction manipulation program. Potentially useful for gear ratios and the like, maybe. Or calculating As a command-line program, you give a rational number on the command line (as a numerator and denominator) and it gives you back a continued fraction expression and a set of rational approximations derived from it. If instead you give a single number, it will be converted to a fraction. This module represents a continued fraction X + 1/(Y + 1/(Z + 1/W)) etc. as the list [X, Y, Z, W], and the rational X/Y as the tuple (X, Y). ## Examples ## An inch is 2.54 centimeters, but did you know that that means 28 centimeters are within half a percent of 11 inches? kragen@inexorable:~/devel/netbook-misc-devel$ ./contfrac.py 2.54 254 / 100 = 2 + 1/(1 + 1/(1 + 1/(5 + 1/(1 + 1/(3.0))))) Rational approximations: 3/1 = 3.0 5/2 = 2.5 28/11 = 2.54545454545 33/13 = 2.53846153846 127/50 = 2.54 What simple fraction is 0.11765 a five-digit approximation of? 2/17. kragen@inexorable:~/devel/netbook-misc-devel$ ./contfrac.py 0.11765 11765 / 100000 = 0 + 1/(8 + 1/(2 + 1/(1176.0))) Rational approximations: 1/8 = 0.125 2/17 = 0.117647058824 2353/20000 = 0.11765 """ def py_contfrac(contfrac): "Return a string of Python to evalute a continued fraction numerically." if len(contfrac) == 1: return '%d.0' % contfrac[0] return '%d + 1/(%s)' % (contfrac[0], py_contfrac(contfrac[1:])) def contfrac_list(num, denom): "Convert a numerator and denominator into a continued fraction." div, mod = divmod(num, denom) if mod == 0: return [div] return [div] + contfrac_list(denom, mod) def rational(contfrac): "Convert a continued fraction into a numerator and denominator." if len(contfrac) == 1: return contfrac[0], 1 else: num, denom = rational(contfrac[1:]) return num * contfrac[0] + denom, num def approximations(contfrac): "Convert a continued fraction into a list of rational approximations." for ii in range(1, len(contfrac)): yield rational(contfrac[:ii+1]) def decimal_to_rational(decimal_string): # How many decimal places do we have? dotpos = decimal_string.find('.') if dotpos == -1: return int(decimal_string), 1 else: decimals = len(decimal_string) - 1 - dotpos denom = 10**decimals return int(0.5 + denom * float(decimal_string)), denom # Unit tests: def ok(a, b): assert a == b, (a, b) # The last approximation should be the rational number itself. ok(list(approximations(contfrac_list(3, 2)))[-1], rational(contfrac_list(3, 2))) ok(contfrac_list(1, 2), [0, 2]) ok(contfrac_list(3, 2), [1, 2]) ok(contfrac_list(2, 3), [0, 1, 2]) # The `rational` function should return the original number (in lowest terms.) ok(rational(contfrac_list(2, 3)), (2, 3)) ok(decimal_to_rational('3.14'), (314, 100)) if __name__ == '__main__': import sys if len(sys.argv) == 3: num, denom = int(sys.argv[1]), int(sys.argv[2]) elif len(sys.argv) == 2: num, denom = decimal_to_rational(sys.argv[1]) else: print __doc__ sys.exit(1) print "%s / %s =" % (num, denom) frac = contfrac_list(num, denom) ex = py_contfrac(frac) print " ", ex print "Rational approximations:" for num, denom in approximations(frac): print " %s/%s = %s" % (num, denom, float(num)/denom)