Fotools
en

Rational approximation/continued fraction expansion

Enter real number

Quick example:

Calculation result

After entering the numbers, click Start Calculation

Algorithm description:

1. Continued Fraction:
Any real number x can be expressed as a continued fraction:
x = a₀ + 1/(a₁ + 1/(a₂ + 1/(a₃ + ...)))
Abbreviated as: x = [a₀; a₁, a₂, a₃, ...]
  • a₀ = ⌊x⌋ (integer part of x)
  • If x is not an integer, let x₁ = 1/(x - a₀) and continue with a₁ = ⌊x₁⌋
  • Repeat this process to get a₂, a₃, ...
  • The continued fraction expansion of rational numbers is finite
  • The continued fraction expansion of irrational numbers is infinite
2. Convergents:
The fraction obtained by intercepting the first n terms of a continued fraction is called the n-th asymptotic fraction, recorded as pn/qn:
  • p-1 = 1, q-1 = 0
  • p0 = a₀, q0 = 1
  • Recursion formula: pn = an·p(n-1) + p(n-2)
  • Recursion formula: qn = an·q(n-1) + q(n-2)
  • An asymptotic fraction is the best rational approximation to the original number
3. Best rational approximation:
  • For a given real number x and an upper denominator bound Q, find the fraction p/q (q ≤ Q) such that |x - p/q| is minimized
  • Asymptotic fractions of continued fractions give all the best rational approximations
  • If p/q is an asymptotic fraction of x, then for all q' < q, |x - p/q| < |x - p'/q'|
4. Continued fractions of special numbers:
  • Golden Ratio φ:[1; 1, 1, 1, 1, ...] (All 1, slowest convergence)
  • √2:[1; 2, 2, 2, 2, ...] (periodic continued fraction)
  • e:[2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, ...] (Regularly)
  • π:[3; 7, 15, 1, 292, 1, ...] (no obvious pattern)

Algorithm complexity:

  • Time complexity:O(n)，where n is the number of terms to expand
  • Space complexity:O(n)，All coefficients and asymptotic fractions need to be stored
  • Numerical stability:Use high-precision floating point numbers or large integers to avoid loss of precision

Application scenarios:

  • Numerical calculation:Use simple fractions to approximate complex irrational numbers (e.g. π ≈ 22/7, 355/113)
  • Music Theory:Interval harmony is related to the simplicity of continued fraction expansions
  • astronomy:Rational approximation for calculating the period of planetary motion
  • Number theory:Diophantine approximation, solution of Pell equation
  • Computer Graphics:Bresenham straight line algorithm, etc.