|
|
Continued Fractions
Posted:
May 20, 2005 11:36 AM
|
|
# K. Urner, 4D Solutions, May 20, 2005
# Math Forum readers using web interface: check plain-text
# view for proper indentation
"""
Python (2.4 or greater) for doing continued fractions (CFs).
Small changes would make it compatible w/ earlier versions.
Non-recursive algorithms are available, but
these provide good practice w/ recursion concept.
Simple Rationals class (Rat) permits returning a
CF in (p/q) format.
Reference:
http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/cfINTRO.html#genCF
Background reading:
http://mathforum.org/kb/message.jspa?messageID=3773030&tstart=0
"""
class Rat(object):
"""
Rational Number (a.k.a. fraction p/q with p,q integers)
Simple version w/ add, multiply only
"""
def __init__(self,a,b):
"""
Constructor: force lowest terms
>>> v = Rat(10,20)
>>> v
(1/2)
"""
lowest = self._gcd(a,b)
self.a = long(a//lowest)
self.b = long(b//lowest)
@staticmethod
def _gcd(a,b):
"""
Euclid's Algorithm
>>> Rat._gcd(10,20)
10
"""
while b:
a,b = b, a % b
return a
@staticmethod
def _lcm(a,b):
"""
Lowest common multiple (uses Euclid's)
>>> Rat._lcm(4,5)
20
"""
return (a*b)//Rat._gcd(a,b)
def __repr__(self):
"""
Represent a fraction as "(a/b)"
"""
return "(%s/%s)" % (self.a, self.b)
def __add__(self, other):
"""
Add self and other fraction, returning a fraction
>>> v = Rat(4,5)
>>> z = Rat(2,4)
>>> z + v
(13/10)
"""
comdenom = self._lcm(self.b, other.b)
numa = self.a * comdenom//self.b
numb = other.a * comdenom//other.b
return Rat(numa+numb, comdenom)
def __mul__(self,other):
"""
Multiply self and other fraction, returning a fraction
>>> v = Rat(4,5)
>>> z = Rat(2,4)
>>> z * v
(2/5)
"""
return Rat(self.a * other.a, self.b * other.b)
def cf1(terms):
"""
Recursive approach to continued fractions, returns floating point
>>> cf1([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1])
1.6180340557275543
"""
if len(terms)==1:
return terms.pop()
else:
return terms.pop() + 1.0/cf1(terms)
def cf2(terms):
"""
Recursive approach to continued fractions, returns Rat object
>>> cf2([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1])
(5895288053236081/3643488239550833)
>>> cf2([1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2])
(7688125463612451/5436325649927203)
>>> (7688125463612451/5436325649927203)
1.4142135623746899
>>> 1.4142135623746899**2
2.0000000000045106
"""
if len(terms)==1:
return terms.pop()
else:
return Rat(terms.pop(0),1) + Rat(1,cf1(terms))
|
|
