Smallest denominator for given accuracy

The following table gives the best rational approximations to π, e, and φ (golden ratio) for a given accuracy goal. Here “best” means the fraction with the smallest denominator that meets the accuracy requirement.

\begin{tabular}{llll} \hline Error bound & \(\pi\) & e & \(\phi\)\\ \hline 10\textsuperscript{-2} & 22/7 & 19/7 & 13/8\\ 10\textsuperscript{-3} & 333/106 & 87/32 & 89/55\\ 10\textsuperscript{-4} & 333/106 & 193/71 & 144/89\\ 10\textsuperscript{-5} & 355/113 & 1264/465 & 377/233\\ 10\textsuperscript{-6} & 355/113 & 2721/1001 & 1597/987\\ 10\textsuperscript{-7} & 103993/33102 & 23225/8544 & 4181/2584\\ 10\textsuperscript{-8} & 103993/33102 & 23225/8544 & 10946/6765\\ 10\textsuperscript{-9} & 103993/33102 & 49171/18089 & 46368/28657\\ 10\textsuperscript{-10} & 312689/99532 & 517656/190435 & 121393/75025\\ \hline \end{tabular}

I found these fractions using Mathematica’s Convergents function.

For any irrational number, the “convergents” of its continued fraction representation give a sequence of rational approximations, each the most accurate possible given the size of its denominator. The convergents of a continued fraction are like the partial sums of a series, the intermediate steps you get in evaluating the limit. More on that here.

Notice there are some repeated entries in the approximations for π. For example, the best approximation for π after the familiar 22/7 is 333/106 = 3.141509…. The fraction with the smallest denominator that gives you at least 3 decimal places actually gives you 4 decimal place. Buy one get one free.

There’s only one repeated row in the e column and none in the φ column. So it may seem there are no interesting patterns in the approximations to φ. But there are. It’s just that our presentation conceals them.

For one thing, all the numerators and denominators in the φ column are Fibonacci numbers. In fact, each fraction contains consecutive Fibonacci numbers: each numerator is the successor of the denominator in the Fibonacci series. There are no repeated rows because these ratios converge slowly to φ.

We don’t see the pattern in the convergents for φ clearly in the table because we pick out the ones that meet our accuracy goals. If we showed all the convergents we’d see that the nth convergent is the ratio of the (n+1)st and nth Fibonacci numbers.

In a sense made precise here, φ is the hardest irrational number to approximate with rational numbers. The bottom row of the table above gives the 8th convergent for π, the 15th convergent for e, and the 25th convergent for φ.

Related posts

3 thoughts on “Smallest denominator for given accuracy

  1. Some of those table entries don’t look quite right: for example, for the π column, I think the next entry after `22/7` should be `201/64` (which is within `1e-3` of π, but has smaller denominator than `333/106`). Similarly, the π entry for `10^-7` should be `75948/24175`. Those numbers are semiconvergents rather than convergents – to find the “best” approximation within given bounds, it’s necessary to take those semiconvergents into account.

  2. Here’s what I get for the table, via Python:

    Tolerance           π                   e                   φ                   
    --------------------------------------------------------------------------------
    1/100               22/7                19/7                13/8                
    1/1000              201/64              87/32               55/34               
    1/10000             333/106             193/71              144/89              
    1/100000            355/113             1071/394            377/233             
    1/1000000           355/113             2721/1001           1597/987            
    1/10000000          75948/24175         15062/5541          4181/2584           
    1/100000000         100798/32085        23225/8544          10946/6765          
    1/1000000000        103993/33102        49171/18089         46368/28657         
    1/10000000000       312689/99532        419314/154257       121393/75025      
    

    And here’s the script that produced the above table:

    from fractions import Fraction
    from decimal import Decimal
    
    from simplefractions import simplest_in_interval
    
    def interval_from_digits(digits):
        """
        Given a truncated decimal expansion of an irrational number,
        return an interval containing that number.
    
        Example
        -------
        >>> interval_from_digits("3.141")
        (Fraction(3141, 1000), Fraction(1571, 500))
        """
        lower = Fraction(digits)
        max_truncation_error = Fraction(f"1e{Decimal(digits).as_tuple().exponent}")
        upper = lower + max_truncation_error
        return lower, upper
    
    def best_approximation(interval, tolerance):
        """
        Given a small interval containing a target irrational number and a
        tolerance, find the simplest fraction that approximates that irrational to
        within the given tolerance.
    
        Raises ValueError if the interval is not small enough to determine
        the simplest fraction uniquely.
        """
        lower, upper = interval
    
        # Get the best candidate in a slightly-too-wide interval
        best_candidate = simplest_in_interval(lower - tolerance, upper + tolerance)
    
        # Double check that it falls in the slightly-too-narrow interval
        if not upper - tolerance <= best_candidate <= lower + tolerance:
            raise ValueError("interval is too wide")
        return best_candidate
    
    
    # Values we're interested in, to 50 places after the point (truncated,
    # not rounded).
    pi_digits = "3.14159265358979323846264338327950288419716939937510"
    e_digits = "2.71828182845904523536028747135266249775724709369995"
    phi_digits = "1.61803398874989484820458683436563811772030917980576"
    
    # Containing intervals
    pi_interval = interval_from_digits(pi_digits)
    e_interval = interval_from_digits(e_digits)
    phi_interval = interval_from_digits(phi_digits)
    
    # Table of best approximations
    print(f"{'Tolerance':20}{'π':20}{'e':20}{'φ':20}")
    print("-"*80)
    for places in range(2, 11):
        tolerance = Fraction(f"1e{-places}")
        print(
            f"{str(tolerance):20}"
            f"{str(best_approximation(pi_interval, tolerance)):20}"
            f"{str(best_approximation(e_interval, tolerance)):20}"
            f"{str(best_approximation(phi_interval, tolerance)):20}"
        )
    

    The “simplefractions” package is a tiny package that I wrote a while ago for almost exactly this purpose; it’s available on PyPI.

Leave a Reply

Your email address will not be published.