Introduction
Every real number has a continued fraction expansion: x = a0 + 1/(a1 + 1/(a2 + 1/(a3 + ...))). For rational numbers the expansion terminates. For irrationals it goes on forever, and the partial quotients a0, a1, a2, ... encode the number with remarkable efficiency. This calculator computes the continued fraction expansion of any real number you enter, lists the convergents p_k/q_k that successively approximate it, and identifies the best rational approximation at each step. The famous approximation 355/113 for pi is not an accident: it is a convergent of pi's continued fraction. Paste a number and see its expansion appear instantly.
What this tool does
- Compute the continued fraction expansion [a0; a1, a2, a3, ...] of any real number using the Euclidean algorithm, with a configurable term limit from 3 to 50
- List all convergents p_k/q_k alongside their decimal values, showing how each fraction gets closer to the input
- Identify the best rational approximation: the convergent with the smallest denominator that is within a given tolerance of the input
- Handle rational numbers (expansion terminates) and irrational numbers (expansion continues up to the term limit, with floating-point precision as the limiting factor)
- Display each partial quotient a_k in a table alongside its convergent, so you can trace the recurrence step by step
- Run entirely in your browser with no server communication
How this tool works
The tool takes a real number x and a maximum term count (default 20). It computes the continued fraction expansion by repeatedly applying the same steps as the Euclidean algorithm: take the floor of x to get a_k, subtract it to get the fractional part, invert the fractional part to get the next x, and repeat. If the fractional part becomes zero, the number is rational and the expansion terminates. If it does not terminate within the term limit, the tool reports as many terms as it can compute before floating-point precision runs out.
The convergents p_k/q_k are computed using the standard recurrence: p_(-1) = 1, p_0 = a_0, and p_k = a_k * p_(k-1) + p_(k-2) for k >= 1. Similarly q_(-1) = 0, q_0 = 1, and q_k = a_k * q_(k-1) + q_(k-2). Each convergent p_k/q_k is a fraction in lowest terms, and the convergents alternate between being above and below x, converging to it.
The tool displays a table with columns k, a_k, p_k/q_k, and the decimal value of each convergent. For example, with x = 3.141592653589793 (pi as a float64), the expansion begins [3; 7, 15, 1, 292, 1, 1, 1, 2, ...]. The convergents are 3/1, 22/7, 333/106, 355/113, 103993/33102, and so on. The convergent 355/113 = 3.14159292... matches pi to 6 decimal places with a denominator of only 113, which is why it was known to Zu Chongzhi in the 5th century.
The best rational approximation is the convergent that achieves the closest match to x relative to its denominator size. By a theorem of Lagrange, every convergent p_k/q_k satisfies |x - p_k/q_k| < 1/(q_k * q_(k+1)), and no fraction with a smaller denominator is closer to x. This is the best approximation property, and it is what makes continued fractions the natural tool for rational approximation.
How continued fractions work (Euler, Khinchin)
Continued fractions have been studied since Euclid's algorithm, but their theory was developed systematically by Leonhard Euler in his *Introductio in Analysin Infinitorum* (1748) and later by Joseph-Louis Lagrange. The modern reference is A. Ya. Khinchin's *Continued Fractions* (University of Chicago Press, 1964), which covers the metric theory, and Hardy and Wright's *An Introduction to the Theory of Numbers* (Chapter X), which covers the arithmetic properties.
A simple continued fraction [a0; a1, a2, ...] has integer partial quotients with a0 any integer and a_k >= 1 for k >= 1. Every irrational number has a unique infinite simple continued fraction, and every rational number has a unique finite one (with the last partial quotient greater than 1). The convergents satisfy the recurrence p_k = a_k * p_(k-1) + p_(k-2) and q_k = a_k * q_(k-1) + q_(k-2), with initial conditions p_(-1) = 1, p_0 = a_0, q_(-1) = 0, q_0 = 1.
The key theorem is the best approximation property: if p/q is a convergent of x, then |x - p/q| < 1/q^2, and no fraction a/b with 0 < b <= q is closer to x. This means continued fractions produce the tightest rational approximations for a given denominator bound, unlike decimal truncation which is wasteful. The approximation 355/113 for pi, discovered independently by Zu Chongzhi (5th century) and later in Europe, is a direct consequence of the large partial quotient 292 in pi's expansion: a large a_k produces an next convergent that is an exceptionally good approximation.
Continued fractions have several applications in cryptography and number theory. Wiener's attack on RSA (Wiener 1990) exploits the fact that if the private exponent d < n^(1/4), then d appears as a denominator of a convergent of the continued fraction of e/n. This is because e/n approximates k/d (for some k related to the key generation), and the best rational approximation property guarantees that the convergent recovers d. The attack runs in polynomial time and breaks RSA with small private exponents. See Wiener 1990 for the original paper.
The CFRAC algorithm (Continued FRACtion factoring method), developed by Lehmer and Powers in 1931 and improved by Morrison and Brillhart in 1975, uses the continued fraction expansion of sqrt(n) to find factors of n. It was the fastest general-purpose factoring algorithm before the quadratic sieve. Pell's equation x^2 - Dy^2 = 1 is also solved using the continued fraction expansion of sqrt(D): the fundamental solution is the convergent p_k/q_k where k is the period of the expansion.
How to use this tool
- Enter a real number x in the input field. You can enter integers, decimals, or expressions like 3.141592653589793
- Optionally adjust the maximum number of terms (3 to 50). The default of 20 is enough for most numbers
- Click Compute. The tool applies the Euclidean algorithm to extract partial quotients a0, a1, a2, ...
- Read the continued fraction expansion displayed as [a0; a1, a2, ...]. If the number is rational, the expansion terminates; if irrational, it continues to the term limit
- Check the convergents table: each row shows k, a_k, the convergent p_k/q_k, and its decimal value. Watch how the decimal values converge to x
- Note the best rational approximation badge, which highlights the convergent that is closest to x relative to its denominator size
Real-world examples
The continued fraction of pi
Input: x = 3.141592653589793. Expansion: [3; 7, 15, 1, 292, 1, 1, 1, 2, ...]. Convergents: 3/1 = 3.0, 22/7 = 3.142857..., 333/106 = 3.141509..., 355/113 = 3.14159292..., 103993/33102 = 3.14159265301... The large partial quotient 292 causes 355/113 to be an exceptionally good approximation: it matches pi to 6 decimal places with denominator 113. This convergent was known to Zu Chongzhi in 5th-century China, centuries before its rediscovery in Europe.
A rational number: 355/113
Input: x = 355/113 = 3.14159292... Expansion: [3; 7, 15, 1]. The expansion terminates after 4 terms because 355/113 is rational. The convergents are 3/1, 22/7, 333/106, 355/113. The last convergent equals the input exactly. This shows that the continued fraction of a rational number p/q is exactly the sequence of quotients produced by the Euclidean algorithm applied to p and q.
The golden ratio and its slow convergence
Input: x = 1.618033988749895 (the golden ratio phi). Expansion: [1; 1, 1, 1, 1, 1, 1, ...]. All partial quotients after a0 are 1. The convergents are 1/1, 2/1, 3/2, 5/3, 8/5, 13/8, 21/13, ... which are ratios of consecutive Fibonacci numbers. The golden ratio has the slowest-converging continued fraction of any irrational number, because the partial quotients are all 1 (the smallest possible value). This is why phi is the hardest irrational to approximate by rationals.
Wiener's attack on RSA with small d
Suppose an RSA key has n = 160523347, e = 60728973. The private exponent d is small. The continued fraction of e/n = 60728973/160523347 is [0; 2, 1, 1, 2, 1, 5, ...]. The convergent 5/13 gives d = 13. Verification: e * d = 60728973 * 13 = 789476649, and 789476649 mod phi(n) should be 1 if d is correct. This is how Wiener's attack recovers a small private exponent in polynomial time by examining the convergents of e/n.
Approximating sqrt(2)
Input: x = 1.4142135623730951 (sqrt(2)). Expansion: [1; 2, 2, 2, 2, 2, ...]. The partial quotients are all 2 after a0. Convergents: 1/1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408. The convergent 577/408 = 1.414215686... matches sqrt(2) to 5 decimal places. The periodic expansion [1; 2, 2, 2, ...] reflects the fact that sqrt(2) is a quadratic irrational, and by Lagrange's theorem, a number has a periodic continued fraction if and only if it is a quadratic irrational.
Comparison with similar methods
| Method | Complexity | Typical use |
|---|---|---|
| Continued fraction convergents | O(k) for k terms, best approximation | Optimal rational approximation, this tool |
| Decimal truncation | O(1), wasteful | Simple but not optimal, denominator is a power of 10 |
| Stern-Brocot tree search | O(log q) per step | Finds best approximation with denominator <= q |
| Dirichlet approximation theorem | Existence only | Guarantees |x - p/q| < 1/q^2 exists for any x |
| Padé approximants | O(n^3) for order n | Approximating functions, not individual numbers |
Limitations or considerations
The tool uses JavaScript floating-point numbers (IEEE 754 double precision, about 15 to 16 significant digits) for the input. For irrational numbers, the continued fraction expansion is only accurate up to the point where floating-point error accumulates. After about 15 to 20 terms for most numbers, the partial quotients become unreliable because the fractional part is dominated by rounding error. For exact computation of continued fractions of algebraic numbers, you would need arbitrary-precision arithmetic and symbolic computation, which this tool does not provide.
The tool does not compute continued fractions of quadratic irrationals symbolically. It cannot detect periodicity in the expansion (which would identify the number as a quadratic irrational by Lagrange's theorem). For that, you would need a computer algebra system like SageMath or Mathematica.
The Wiener's attack example is illustrative only. The tool computes the continued fraction of e/n, but it does not automatically test each convergent to see if it yields a valid private exponent. A full implementation of Wiener's attack would check each convergent k/d by computing phi(n) = (ed - 1) / k and verifying that n factors as pq with (p-1)(q-1) = phi(n). See the RSA Encrypt / Decrypt tool for RSA operations.
The tool does not solve Pell's equation. While the continued fraction of sqrt(D) gives the fundamental solution to x^2 - Dy^2 = 1, extracting that solution requires detecting the period of the expansion, which needs symbolic arithmetic. For gcd computation (which underlies the Euclidean algorithm that produces continued fractions), use the GCD / LCM Calculator.
Frequently asked questions
What is a continued fraction?
A continued fraction expresses a real number x as a0 + 1/(a1 + 1/(a2 + 1/(a3 + ...))) where a0 is an integer and a1, a2, ... are positive integers called partial quotients. Rational numbers have finite expansions; irrational numbers have infinite expansions. The expansion is unique (with the convention that the last partial quotient of a rational is greater than 1).
Why is 355/113 such a good approximation to pi?
Because 355/113 is a convergent of pi's continued fraction, and the preceding partial quotient is 292, which is unusually large. A large partial quotient a_k means the next convergent p_k/q_k is especially close to x: the error is less than 1/(q_k * q_(k+1)), and q_(k+1) = a_(k+1) * q_k + q_(k-1) is large when a_(k+1) is large. The convergent 355/113 matches pi to 6 decimal places with a denominator of only 113.
What is the best approximation property of convergents?
If p/q is a convergent of x, then |x - p/q| < 1/q^2. Moreover, no fraction a/b with 0 < b <= q is closer to x than p/q. This means convergents are the best rational approximations to x for their denominator size. This theorem is due to Lagrange and is proved in Hardy and Wright, Chapter X. It is why continued fractions outperform decimal truncation for rational approximation.
How does Wiener's attack on RSA use continued fractions?
Wiener (1990) observed that if the RSA private exponent d < n^(1/4), then k/d is a convergent of the continued fraction of e/n. This is because e/n approximates k/d with error less than 1/(2d^2), and the best approximation property guarantees the convergent recovers d. The attack checks each convergent of e/n, tests whether it yields a valid d, and recovers the private key in polynomial time. This is why RSA implementations must use d >= n^(1/4), typically d close to phi(n).
What is the connection between continued fractions and the Euclidean algorithm?
The continued fraction expansion of a rational number p/q produces exactly the same sequence of quotients as the Euclidean algorithm applied to p and q. Each step of the Euclidean algorithm divides and takes the remainder; the quotient is a partial quotient of the continued fraction, and the process repeats with the remainder. For irrational numbers, the process is the same but never terminates, producing an infinite continued fraction.
Can continued fractions be used for factoring?
Yes. The CFRAC algorithm (Lehmer and Powers, 1931; Morrison and Brillhart, 1975) uses the continued fraction expansion of sqrt(n) to generate relations that lead to a factorization of n. It was the fastest general-purpose factoring algorithm before the quadratic sieve. The idea is that the convergents of sqrt(n) produce values x^2 mod n that are smooth (have only small prime factors), and combining enough smooth relations via linear algebra yields a factor. This tool does not implement CFRAC.
Conclusion
Continued fractions are the most efficient way to represent real numbers as sequences of integers, and their convergents are the best rational approximations available. This calculator makes the expansion and the convergent table visible, so you can see why 355/113 approximates pi so well and how the recurrence builds each fraction. The same mathematics underlies Wiener's attack on RSA, the CFRAC factoring algorithm, and the solution of Pell's equation. To explore the number-theoretic building blocks, see the Euler's Totient Calculator and the Prime Factorization tool. To see RSA in action (and understand why small private exponents are dangerous), try the RSA Encrypt / Decrypt tool. For gcd computation, which is the algorithm behind continued fraction expansion, use the GCD / LCM Calculator.