Continued Fractions: Best Rational Approximations (2D)

What Are Continued Fractions

A continued fraction is a representation of a real number as the sum of an integer and a series of fractions, each having 1 as its numerator. For example, the golden ratio φ can be expressed as [1; 1, 1, 1, ...], which means 1 + 1/(1 + 1/(1 + 1/...)). This form is particularly useful for finding rational approximations to irrational numbers.

Continued fractions provide a sequence of increasingly accurate rational approximations called convergents. These are the best possible rational approximations given a certain number of terms in the continued fraction.

How Continued Fractions Work

To find the continued fraction representation of a real number, you repeatedly take the integer part and then invert the fractional part. For instance, to represent √2, you start with [1; 2, 2, 2, ...], where each term is derived from the previous step's fractional part.

The Stern-Brocot tree provides a way to generate all possible rational approximations of a real number in a systematic manner. Each node in the tree represents a fraction that can be used as an approximation.

Why They Matter

Continued fractions are crucial in various fields, including number theory and cryptography. They help in understanding the structure of real numbers and provide efficient algorithms for computing with them.

In practical applications, continued fractions can be used to approximate irrational constants like π or e with high precision using simple rational numbers.

Real-World Examples

Continued fractions have been used in the design of digital filters and control systems. They also play a role in solving Diophantine equations, which are polynomial equations where only integer solutions are sought.

In cryptography, continued fractions can be used to factor large integers, although modern methods often use more efficient algorithms.

Frequently asked questions

Try it live

Everything above runs in your browser — open Continued Fractions: Best Rational Approximations (2D) and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.