Get the best rational approximations for any real number in builtin Python

Question

Best rational approximations is a technical term and not subjective. The best rational approximations are the convergents of a value plus it's semi convergents that are closer to the original value than the previous convergents.

Hi everyone,

I've written some quick code in Python that is my tool for exploring various aspects of music theory, number theory, and my obsession with OEIS. It's currently written to spit out a list of the ratio's themselves. It would be quite easy to tweak to your needs. This may also help anyone exploring the logic of infinite continued fractions and convergents. I use the decimal module here for precision. It's written so you can paste any value you want into the input field - that can easily be tweaked to accept any real number from code. Phasers to stun. I call it my approximilator.

(Python 3)

import decimal
import math

D = decimal.Decimal

def contFrac(x, k):
    """Cont Frac from Real value"""
    cf = []
    q = math.floor(x)
    cf.append(q)
    x = x - q
    i = 0

    while x != 0 and i < k:
        q = math.floor(1 / x)
        if q > k:
            break
        cf.append(q)
        x = 1/x - q
        i += 1

    return cf

def bestra(clist, app):
    """Best Rational Approximation from Cont. Frac"""
    hn0, kn0 = 0, 1
    hn1, kn1 = 1, 0
    """Best Rational Approx Init"""
    ran, rad = 0, 0
    conlist, ralist, finallist = [], [], []

    for n in clist:
        for i in range(1, n+1):
            ran = (hn0 + (i*hn1))
            rad = (kn0 + (i*kn1))
            try:
                if D.copy_abs(app-D(ran/rad)) < D.copy_abs(app-D(hn1/kn1)):
                    ralist.append({'ratio': f'{ran}/{rad}', 'denom' : rad})
            except:
                pass
        hn2 = (n*hn1)+hn0
        kn2 = (n*kn1)+kn0
        conlist.append({'ratio': f'{hn2}/{kn2}', 'denom': kn2})
        hn0, kn0 = hn1, kn1
        hn1, kn1 = hn2, kn2

    for x in sorted(conlist+ralist, key = lambda i: i['denom']):
        finallist.append(x['ratio'])

    return list(dict.fromkeys(finallist))


if __name__ == "__main__":
    value = D(input('Input value to approximate: '))
    prec = len(str(value))*2
    decimal.getcontext().prec = prec
    vc = contFrac(value, prec)
    print(bestra(vc, value))

Some output for Pi to entice:

'3/1', '13/4', '16/5', '19/6', '22/7', '179/57', '201/64', '223/71', '245/78', '267/85', '289/92', '311/99', '333/106', '355/113', '52163/16604', '52518/16717', '52873/16830', '53228/16943', '53583/17056', '53938/17169', '54293/17282', '54648/17395', '55003/17508', '55358/17621', '55713/17734', '56068/17847', '56423/17960'

Answer 1

PEP-8 Guidelines

Follow the PEP-8 Style Guidelines, such as:

• 1 space around operators (1 / x instead of 1/x)
• snake_case for identifiers & functions (cont_frac instead of contFrac)

Import As

The preferred method of creating an alias for an import is:

from decimal import Decimal as D

Since you are only using the floor function from math, you could also:

from math import floor

Docstrings

"""Docstrings""" exist to help a user with the usage of a function. There are usually in triple quotes, because they should be multi-line strings, with enough information to be useful to the caller, without needing the caller to read the source code.

def continue_fraction(x, k):
    """
    Construct a continued fraction from a real value

    Parameters:
        x (float): Real value to determine continued fraction of
        k (int): A loop limit representing accuracy somehow

    Returns:
        List[Int]: List of continued fraction values
    """

A """docstring""" is the first statement of a module, class, function or method, if it is a string. In particular,

    """Best Rational Approx Init"""

is not a """docstring""", because it is not the first statement. It should be a comment.

    # Best Rational Approx Init

Comments are used to document the source code, for someone reading the source code. In contrast, """Docstrings""" are used to provide help to the user of the item, so they do not have to read the source code. It is displayed using the help() command:

>>> help(continue_fraction)

Don't use docstrings as comments, or vise-versa.

Superfluous Parenthesis

        ran = (hn0 + (i*hn1))
        rad = (kn0 + (i*kn1))

should be written as

        ran = hn0 + i * hn1
        rad = kn0 + i * kn1

Named Tuple

Consider using a named tuple, instead of using dictionaries for fixed content items.

from collections import namedtuple

fraction = namedtuple("fraction", "ratio, denom")

...

        ...
        ralist.append(fraction(f'{ran}/{rad}', rad))
        ...

    for x in sorted(conlist + ralist, key=lambda i: i.denom):
        finallist.append(x.ratio)

Collection

Why are you maintaining ralist separate from conlist, when you later add the two lists together and sort them?? Why not just maintain a single list?

List Comprehension

List appending is inefficient:

    finallist = []
    for x in sorted(conlist + ralist, key=lambda i: i.denom):
        finallist.append(x.ratio)

due to repeated reallocations of the list as the list size grows. It is better to construct and initialize the list in one operation:

    finallist = [ x.ration for x in sorted(conlist + ralist, key=lambda i: i.denom) ]

Useless

This operation:

return list(dict.fromkeys(finallist))

takes a list, turns it into a dictionary with each list item as a key (all the dictionary values are None), and then constructs a list from just the dictionary's keys. Uhm. As long as the dictionary is kept in insertion order, which it is because you are using f'' strings so must be using Python 3.6 or later, this is indistinguishable from:

return finallist

Apparently the goal here was to remove duplicates. A comment would have helped; it is not obvious.

Meaningful Function and Variable Names

What is contFrac and bestra? It would be way clearer to use continued_fraction and best_rational_approximation, especially if you are writing this for "anyone exploring the logic of infinite continued fractions".

conlist, ralist, clist, app, ran and rad are equally obscure.

Answer 2

Revised version per answer:

import decimal
from math import floor
from decimal import Decimal as D
from collections import namedtuple

def continued_fraction(x, k):
    cf = []
    q = floor(x)
    cf.append(q)
    x = x - q
    i = 0

    while x != 0 and i < k:
        q = floor(1 / x)
        if q > k:
            break
        cf.append(q)
        x = 1 / x - q
        i += 1

    return cf

def best_rational_approximation(clist, app):
    hn0, kn0 = 0, 1
    hn1, kn1 = 1, 0
    ran, rad = 0, 0
    conlist, finallist = [], []
    fraction = namedtuple("fraction", "ratio, numer, denom")
    for n in clist:
        for i in range(1, n + 1):
            ran = hn0 + (i * hn1)
            rad = kn0 + (i * kn1)
            try:
                if D.copy_abs(app-D(ran/rad)) < D.copy_abs(app-D(hn1/kn1)):
                    conlist.append(fraction(f'{ran}/{rad}', ran, rad))
            except:
                pass
        hn2 = (n * hn1) + hn0
        kn2 = (n * kn1) + kn0
        conlist.append(fraction(f'{hn2}/{kn2}', hn2, kn2))
        hn0, kn0 = hn1, kn1
        hn1, kn1 = hn2, kn2
    #Change x.ratio to x.denom or x.numer for numerators or denominators   
    finallist = [ x.ratio for x in sorted(conlist, key=lambda i: i.denom) ]
    return list(dict.fromkeys(finallist))


if __name__ == "__main__":
    value = D(input('Input value to approximate: '))
    prec = len(str(value))*2
    decimal.getcontext().prec = prec
    vc = continued_fraction(value, prec)
    print(best_rational_approximation(vc, value))
~