Convergents of a Continued Fraction

[Albert Chan]

(03-13-2022 11:41 PM)Thomas Klemm Wrote:  With \(u{'}\), \(v{'}\) and \(w{'}\) we denote the successors:

\(
\begin{align}
u{'} &= \frac{h_{n}}{k_{n − 1}} =& a_n w{'} + \frac{w}{v} \\
\\
v{'} &= \frac{k_{n}}{k_{n − 1}} =& a_n + \frac{1}{v} \\
\\
w{'} &= \frac{h_{n − 1}}{k_{n − 1}} =& \frac{u}{v} \\
\end{align}
\)

So we only need to keep track of the three values \(v\), \(w\), and \(w{'}\) on the stack.
The sequence \(w, w{'}, w{''}, \cdots\) are the convergents of the continued fraction.

Assuming {u,v,w} start out finite. (i.e. a₁ ≠ 0)

This is what happen if we have double-zero CF coeffs, a_n = a_n+1 = 0, n>1

w' = u/v
u' = w/v
v' = 1/v

w'' = u'/v' = (w/v) / (1/v) = w
u'' = w'/v' = (u/v) / (1/v) = u
v'' = 1/v' = 1/(1/v) = v

0 + 1/(0 + 1/CF) = 1/(1/CF) = CF

{u'',v'',w''} = {u,v,w}, matching expectation.