ContinuedFractions.py

#!/usr/bin/env python
# encoding: utf-8

'''
Created on Dec 14, 2011
@author: pablocelayes

'''

def rational_to_contfrac (x, y):
    '''
    Converts a rational x/y fraction into
    a list of partial quotients [a0, ..., an]
    '''
    a = x//y
    if a * y == x:
        return [a]
    else:
        pquotients = rational_to_contfrac(y, x - a * y)
        pquotients.insert(0, a)
        return pquotients

#TODO: efficient method that calculates convergents on-the-go, without doing partial quotients first
def convergents_from_contfrac(frac):
    '''
    computes the list of convergents
    using the list of partial quotients
    '''
    convs = [];
    for i in range(len(frac)):
        convs.append(contfrac_to_rational(frac[0:i]))
    return convs

def contfrac_to_rational (frac):
    '''Converts a finite continued fraction [a0, ..., an]
     to an x/y rational.
     '''
    if len(frac) == 0:
        return (0,1)
    elif len(frac) == 1:
        return (frac[0], 1)
    else:
        remainder = frac[1:len(frac)]
        (num, denom) = contfrac_to_rational(remainder)
        # fraction is now frac[0] + 1/(num/denom), which is
        # frac[0] + denom/num.
        return (frac[0] * num + denom, num)

def test1():
    '''
    Verify that the basic continued-fraction manipulation stuff works.
    '''
    testnums = [(1, 1), (1, 2), (5, 15), (27, 73), (73, 27)]
    for r in testnums:
        (num, denom) = r
        print('rational number:')
        print(r)

        contfrac = rational_to_contfrac (num, denom)
        print('continued fraction:')
        print(contfrac)

        print('convergents:')
        print(convergents_from_contfrac(contfrac))
        print('***********************************')

if __name__ == "__main__":
    test1()