# 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.