Continued fraction calculator

How it works

A continued fraction writes a number as $a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \dotsb}}$, shortened to $[a_0; a_1, a_2, \dots]$. For a fraction the terms are the quotients of Euclid’s algorithm, so the expansion ends: $\frac{415}{93} = [4; 2, 6, 7]$. Cutting it off early gives the convergents $\frac{h_i}{k_i}$, the best approximations with denominators of their size, such as $\frac{22}{7}$ and $\frac{355}{113}$ for $\pi$.

A square root $\sqrt n$ of a non-square has an infinite but periodic expansion, found with whole numbers only: $\sqrt{23} = [4; \overline{1, 3, 1, 8}]$. The convergent just before the end of the first period solves Pell’s equation $x^2 - n y^2 = \pm 1$, for example $24^2 - 23 \cdot 5^2 = 1$.

In cryptography, continued fractions break RSA with a small private exponent: Wiener’s attack finds $d$ among the convergents of $e/N$ when $d < N^{1/4}/3$. They also appear in the classical post-processing of Shor’s quantum factoring algorithm.