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.

• Graipher: list(dict.fromkeys(finallist)) is different from finallist if it has duplicates. But that is not the best way to get rid of duplicates.
• FodderOverflow: Solid, any suggestions to remove duplicates?
• AJNeufeld: I see. w3schools recommends that as the way to remove duplicates. Using itertools.groupby() to removed duplicates should be faster for large already sorted datasets. See especially the unique_justseen() recipe.
• FodderOverflow: unique_justseen(), excellent. Thanks for your time , I appreciate it.

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))
~