# Continued Fractions

# 1 Concept

\[x = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \cdots}}}\]

Often written

\[x = [a_0; a_1, a_2, a_3, \ldots]\]

\(a_0\) can be any integer, the other \(a_i\) are positive integers.

Rationals have a terminating expansion (implicitly the next term would be \(\infty\)).

Terminating expansions represent rational numbers.

# 2 Conversion

\[\begin{aligned} x_0 &\gets x \\ a_n &\gets \left\lfloor x_n \right\rfloor \\ x_{n+1} &\gets \frac{1}{x_n - a_n} \end{aligned}\]

# 3 Arithmetic

See:

Bill Gosper, “Continued Fraction Arithmetic”, unpublished, circa 1978 – https://perl.plover.com/yak/cftalk/INFO/gosper.txt

which also introduces continued logarithms, which have different space/time tradeoffs.