Welcome, guest | Sign In | My Account | Store | Cart

A class representing a continued fraction.

Python, 81 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
"""
Continued fractions.
"""

from decimal import Decimal
from fractions import Fraction


class CFraction(list):
    """
    A continued fraction, represented as a list of integer terms.
    """

    def __init__(self, value, maxterms=15, cutoff=1e-10):
        if isinstance(value, (int, float, Decimal)):
            value = Decimal(value)
            remainder = int(value)
            self.append(remainder)

            while len(self) < maxterms:
                value -= remainder
                if value > cutoff:
                    value = Decimal(1) / value
                    remainder = int(value)
                    self.append(remainder)
                else:
                    break
        elif isinstance(value, (list, tuple)):
            self.extend(value)
        else:
            raise ValueError("CFraction requires number or list")

    def fraction(self, terms=None):
        "Convert to a Fraction."

        if terms is None or terms >= len(self):
            terms = len(self) - 1

        frac = Fraction(1, self[terms])
        for t in reversed(self[1:terms]):
            frac = 1 / (frac + t)

        frac += self[0]
        return frac

    def __float__(self):
        return float(self.fraction())

    def __str__(self):
        return "[%s]" % ", ".join([str(x) for x in self])

if __name__ == "__main__":
    from math import e, pi, sqrt

    numbers = {
        "phi": (1 + sqrt(5)) / 2,
        "pi": pi,
        "e": e,
    }

    print "Continued fractions of well-known numbers"
    for name, value in numbers.items():
        print "   %-8s  %r" % (name, CFraction(value))

    for name, value in numbers.items():
        print
        print "Approximations to", name
        cf = CFraction(value)
        for t in xrange(len(cf)):
            print "   ", cf.fraction(t)

    print
    print "Some irrational square roots"
    for n in 2, 3, 5, 6, 7, 8:
        print "   ", "sqrt(%d)  %r" % (n, CFraction(sqrt(n)))

    print
    print "Decimals from 0.1 to 0.9"
    for n in xrange(1, 10):
        cf = CFraction(n / 10.0)
        print "   ", float(cf), cf