Mathematics · Number Theory
Continued Fraction Calculator
Converts a real number into its continued fraction representation and computes successive convergents.
Calculator
Formula
x is the real number being represented. a_0 = \lfloor x \rfloor is the integer part (floor). Each subsequent term a_k = \lfloor 1/(x_{k-1} - a_{k-1}) \rfloor is computed by taking the floor of the reciprocal of the fractional remainder. The convergents p_k/q_k are the best rational approximations to x obtainable with denominator \leq q_k, computed via the recurrences p_k = a_k p_{k-1} + p_{k-2} and q_k = a_k q_{k-1} + q_{k-2}.
Source: Hardy, G.H. & Wright, E.M. — An Introduction to the Theory of Numbers, Oxford University Press (6th ed., 2008), Chapters 10–11.
How it works
A simple continued fraction is an expression of the form x = a₀ + 1/(a₁ + 1/(a₂ + 1/(a₃ + ⋯))), where each aₖ is a non-negative integer called a partial quotient. The algorithm is closely related to the Euclidean algorithm: at each step, take the floor of the current value to get the next partial quotient, then invert the fractional remainder and repeat. Every rational number terminates after a finite number of steps, while every irrational number produces an infinite sequence. Quadratic irrationals (like √2 or the golden ratio φ) are the only irrationals with eventually periodic continued fractions — a theorem due to Lagrange.
The convergents p_k/q_k are the rational fractions obtained by truncating the expansion at each step. They satisfy the recurrences p_k = a_k·p_{k-1} + p_{k-2} and q_k = a_k·q_{k-1} + q_{k-2}, with seeds p₋₁ = 1, p₀ = a₀, q₋₁ = 0, q₀ = 1. Convergents alternate above and below x, approaching it with remarkable efficiency: the error |x − p_k/q_k| < 1/q_k², and no fraction with denominator ≤ q_k can approximate x more closely than p_k/q_k. This property makes continued fractions optimal in a precise mathematical sense.
Practical applications include the design of gear ratios in mechanical engineering (finding integer ratios close to a target), musical temperament theory (approximating irrational frequency ratios with small integers), calendar design (approximating the tropical year), the LLL lattice reduction algorithm used in cryptanalysis, and fast implementations of arbitrary-precision arithmetic. The Stern–Brocot tree and Farey sequences are both deeply connected to continued fraction theory.
Worked example
Let us compute the continued fraction expansion of π ≈ 3.14159265358979 to 7 terms.
Step 1: a₀ = ⌊3.14159265⌋ = 3. Remainder: 3.14159265 − 3 = 0.14159265. Reciprocal: 1/0.14159265 ≈ 7.06251.
Step 2: a₁ = ⌊7.06251⌋ = 7. Remainder: 0.06251. Reciprocal: ≈ 15.9966.
Step 3: a₂ = ⌊15.9966⌋ = 15. Remainder: 0.9966. Reciprocal: ≈ 1.00341.
Step 4: a₃ = ⌊1.00341⌋ = 1. Remainder: 0.00341. Reciprocal: ≈ 292.63.
Step 5: a₄ = ⌊292.63⌋ = 292. (This large term explains why 355/113 is such an extraordinarily good approximation.)
The expansion is [3; 7, 15, 1, 292, 1, 1, …].
Computing convergents via the recurrence:
- k=0: p₀/q₀ = 3/1 — error 0.14159
- k=1: p₁ = 7·3+1 = 22, q₁ = 7·1+0 = 7 → 22/7 — error 0.00126
- k=2: p₂ = 15·22+3 = 333, q₂ = 15·7+1 = 106 → 333/106 — error 8.32×10⁻⁵
- k=3: p₃ = 1·333+22 = 355, q₃ = 1·106+7 = 113 → 355/113 — error 2.67×10⁻⁷
The convergent 355/113 approximates π to within 0.000000085, making it the best rational approximation to π with denominator under 30,000 — a fact known to Chinese mathematician Zu Chongzhi in the 5th century CE.
Limitations & notes
Floating-point arithmetic introduces rounding errors that accumulate during repeated reciprocal operations, so very long expansions (beyond 15–18 terms) may be unreliable for irrational inputs given as decimals. For exact symbolic computation of algebraic numbers, a computer algebra system using exact rational or algebraic arithmetic is preferable. The calculator handles only simple continued fractions (all numerators equal 1); generalized continued fractions with arbitrary numerators are not covered. For rational inputs, the algorithm terminates exactly, but the representation is non-unique — every rational number has exactly two finite simple continued fraction representations (one ending in 1 and one not). This calculator returns the canonical form where the last partial quotient is greater than 1 whenever possible. Very large or very small inputs may exhaust the 64-bit floating-point range before producing a meaningful expansion.
Frequently asked questions
What is a continued fraction and why is it useful?
A continued fraction represents a number as a tower of integer floors and reciprocals. Unlike decimal expansions, continued fractions reveal the deep structure of a number: periodic expansions identify quadratic irrationals, and the convergents give the best possible rational approximations at each denominator size, which is valuable in engineering, music theory, and cryptography.
How do I find the continued fraction of a fraction like 355/113?
Apply the Euclidean algorithm: 355 = 3·113 + 16, so a₀ = 3. Then 113 = 7·16 + 1, so a₁ = 7. Then 16 = 16·1 + 0, so a₂ = 16. The result is [3; 7, 16], which matches π's convergent 355/113 — the last term incremented by 1 due to the two-representation rule.
What are convergents and how accurate are they?
Convergents are the rational fractions formed by truncating the continued fraction at each step. The k-th convergent p_k/q_k satisfies |x − p_k/q_k| < 1/(q_k·q_{k+1}), and no fraction with a smaller denominator can be closer to x. This makes them the gold standard for rational approximation.
Why does π have 292 as a partial quotient?
The partial quotient 292 appears at position k=4 of π's expansion. A large partial quotient means the previous convergent (355/113) is an exceptionally good approximation — the next convergent barely improves on it because 292 is so large. This is why 355/113 approximates π to 6 decimal places despite having a denominator under 1,000.
Do irrational numbers always have infinite continued fractions?
Yes. A real number has a finite simple continued fraction if and only if it is rational. Irrational numbers always produce infinite sequences of partial quotients. Moreover, a number has an eventually periodic continued fraction if and only if it is a quadratic irrational — a root of a quadratic equation with integer coefficients, such as √2 = [1; 2, 2, 2, …] or φ = [1; 1, 1, 1, …].
Last updated: 2025-01-15 · Formula verified against primary sources.