Search code examples
pythonfractionscontinued-fractions

Convert fraction to continued fraction

How would I convert a fraction to a continued fraction in Python? I tried looking around and found people using the Fraction module to do things similar to my problem, but I did not manage to modify them. An example with an image I found:

example

So if the input is 181 101, then the output should be 1 1 3 1 4 4. Thanks ahead!

Solution

  • Ok, let's start with some mathematics. The rationale behind that is simple. For the fraction n/d, the euclidian division is n = d * q + r with r < d

    We simply have n/d = (d * q + r) / d = q + r/d with r < d

    Now we iterate with 1/(r/d) = d/r to get your continued fraction

    It will lead to a finished sequence of q, because the denominator of the sequence of fractions constitute a stricly decreasing integer sequence which will reach 0 in at most d operations.

    A possible Python implementation could be:

    def cf(n, d):
    """Return the terms of the continued fraction when n is the numerator
and d the divisor as a list"""
    if d == 0: return []         # Ok it is finished
    q = n//d                     # compute the integer quotient
    r = n - q*d                  # the rest
    return [q] + cf(d, r)        # and recurse...

    We get as expected:

    >>> cf(181, 101)
[1, 1, 3, 1, 4, 4]