"""
Python (2.4 or greater) for doing continued fractions (CFs).
Small changes would make it compatible w/ earlier versions of Python.

by K. Urner, 4D Solutions, May 20, 2005
modified June 15, 2005 to add more methods (e.g. __pow__, __div__),
fixed a bug wherein cf2 called cf1, improved handling of signs per
thread: http://mathforum.org/kb/message.jspa?messageID=3805813&tstart=0

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

"""

from types import LongType, IntType

inttypes = [IntType, LongType]  # group ints and longs for type checking

class Rat(object):
    """
    Rational Number (a.k.a. fraction p/q with p,q integers)
    Accepts integers, longs or rationals as p,q
    """
    def __init__(self,p,q):
        """
        Constructor: force lowest terms

        >>> v = Rat(10,20)
        >>> v
        (1/2)

        Allow incoming numerator and/or denominator to be
        themselves rational numbers
        """
        if type(p)==type(self) and type(q) in inttypes:
           a = p.a * q
           b = p.b
        if type(p) in inttypes and type(q)==type(self):
           a = p * q.b
           b = q.a
        if type(p)==type(self) and type(q)==type(self):
           a = p.a * q.b
           b = p.b * q.a
        if type(p) in inttypes and type(q) in inttypes:
           a = p
           b = q
           
        lowest = self._gcd(a,b)
        self.a = long(a//lowest)
        self.b = long(b//lowest)

        if self.b==0:
            raise ValueError
        
        if self.a < 0 and self.b < 0:
            self.a = -self.a
            self.b = -self.b
        if self.b < 0 and self.a >= 0:
            self.a = - self.a
            self.b = abs(self.b)
            
    @staticmethod    
    def _gcd(a,b):
        """
        Euclid's Algorithm

        >>> Rat._gcd(10,20)
        10
        """
        while b:
            a,b = b, a % b
        return abs(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 __neg__(self):
        """
        Negate self by changing the sign of the numerator

        >>> v = Rat(4,5)
        >>> z = -v
        >>> z
        (-4/5)        
        """        
        return Rat(-self.a, self.b)

    def __sub__(self, other):
        """
        Subtract other from self, by adding the negated other

        >>> v = Rat(4,5)
        >>> z = Rat(2,4)
        >>> v - z
        (3/10)
        """
        return self + (-other)

    def __pow__(self, val):
        """
        Raise self to a power.  A negative power involves taking
        the reciprocal, then powering

        >>> v = Rat(4,5)
        >>> z = v**(-2)
        >>> z
        (25/16)
        """
        if val < 0:
            return Rat(self.b**abs(val), self.a**abs(val))
        else:
            return Rat(self.a**abs(val), self.b**abs(val))

    def __div__(self, other):
        """
        Divide self by other fraction, returning a fraction

        >>> v = Rat(4,5)
        >>> z = Rat(2,4)
        >>> v / z
        (8/5)
        """
        return self * other**(-1)
        
        

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])
    (4181/2584)

    >>> cf2([1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2])
    (665857/470832)

    >>> (665857./470832)
    1.4142135623746899

    >>> 1.4142135623746899**2
    2.0000000000045106
    """
    if len(terms)==1:
        return terms.pop()
    else:
        return Rat(terms.pop(0),1) + Rat(1, cf2(terms))