Convergents of a Continued Fraction

[Albert Chan]

(03-13-2022 11:41 PM)Thomas Klemm Wrote:  For example, here are the convergents for \([0;1,5,2,2]\).

\(
\begin{matrix}
n & −2 & −1 & 0 & 1 & 2 & 3 & 4 \\
a_n & & & 0 & 1 & 5 & 2 & 2 \\
h_n & 0 & 1 & 0 & 1 & 5 & 11 & 27 \\
k_n & 1 & 0 & 1 & 1 & 6 & 13 & 32 \\
\end{matrix}
\)

Just a visual explanation why OP setup only need to track 3 values on the stack.

Scaling the entries does not change convergent ratios.
h(n)/k(n) = w(n)/1, and we don't need to store denominator 1

Code:

a(n)      0 1    5    2     2
h(n) 0  1 0 1    5
k(n) 1  0 1 1    6

            1/6  5/6  11/6   11/13
            ---  ---  ---- = -----
            1/6  1    13/6     1
       
                 5/13 11/13  27/13   27/32
                 ---- -----  ----- = -----
                 6/13   1    32/13     1

But, there is a cost. Convergent integer ratio is lost, only its value remained.
Also, a1≠0 is required, because we can't scale denominator of 0 to 1.
Also, we can't start with a0 alone, because k(-1)=0, unable to scale to 1