Continued fraction

O(log min(a, b))

A continued fraction expresses a/b as a₀ + 1/(a₁ + 1/(a₂ + …)). To find the terms, take the integer part q = ⌊a/b⌋, subtract it, invert the remainder, and repeat — which is precisely the sequence of quotients Euclid's algorithm produces while computing gcd(a, b). So the expansion always terminates for a rational number, and its length is the number of division steps. Continued fractions give the best rational approximations to a number (truncating early yields the convergents) and reveal structure that decimals hide. Each cell is one term aᵢ; the step shows the division a = q·b + r that produced it.

Sequence
Press ▶ to run
Edit the input and press Play

How it works

  1. Take the whole part q = ⌊a/b⌋ as the next term.
  2. Replace a/b with b/(a mod b).
  3. Repeat until the remainder is 0.
  4. The terms are [a₀; a₁, a₂, …].

Pseudocode

1continuedFraction(a, b):            # O(log min(a,b))2  while b ≠ 0:3    q ← ⌊a / b⌋                      # next term4    emit q5    a, b ← b, a mod b                # same step as gcd