Continued fraction convergents

Continued fraction convergents is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

This task has been flagged for clarification. Code on this page in its current state may be flagged incorrect once this task has been clarified. See this page's Talk page for discussion.

Given a positive real number, if we truncate its continued fraction representation at a certain depth, we obtain a rational approximation to the real number. The sequence of successively better such approximations is its convergent sequence.

Problem:

• Given a positive rational number ${\frac {m}{n}}$, specified by two positive integers $m,n$, output its entire sequence of convergents.
• Given a quadratic real number ${\frac {b{\sqrt {a}}+m}{n}}>0$, specified by integers $a,b,m,n$, where $a$ is not a perfect square, output the first $k$ convergents when given a positive number $k$.

The output format can be whatever is necessary to represent rational numbers, but it probably should be a 2-tuple of integers.

For example, given $a=2,b=1,m=0,n=1$, since

$${\sqrt {2}}=1+{\cfrac {1}{2+{\cfrac {1}{2+{\cfrac {1}{2+\ddots }}}}}}$$

the program should output $(1,1),(3,2),(7,5),(17/12),(41/29),\dots$.

A simple check is to do this for the golden ratio ${\frac {{\sqrt {5}}+1}{2}}$, that is, $a=5,b=1,m=1,n=2$, which should output $(1,1),(2,1),(3,2),(5,3),(8,5),\dots$.

Wren

Library: Wren-rat

Well, the task seems reasonably clear now to me.

The following is loosely based on the Python code here. If a large number of terms were required for quadratic real numbers, then one might need to use 'arbitrary precision' arithmetic to avoid round-off errors when converting between floats and rationals.

import "./rat" for Rat

var cfcRat = Fn.new { |m, n|
    var p = [0, 1]
    var q = [1, 0]
    var s = []
    var r = Rat.new(m, n)
    var rem = r
    while (true) {
        var whole = rem.truncate
        var frac  = rem.fraction
        var pn = whole * p[-1] + p[-2]
        var qn = whole * q[-1] + q[-2]
        var sn = pn / qn
        p.add(pn)
        q.add(qn)
        s.add(sn)
        if (r == sn) break
        rem = frac.inverse
    }
    return s
}

var cfcQuad = Fn.new { |a, b, m, n, k|
    var p = [0, 1]
    var q = [1, 0]
    var s = []
    var r = (a.sqrt * b + m) / n
    var rem = r
    for (i in 1..k) {
        var whole = rem.truncate
        var frac  = rem.fraction
        var pn = whole * p[-1] + p[-2]
        var qn = whole * q[-1] + q[-2]
        var sn = Rat.new(pn, qn)
        p.add(pn)
        q.add(qn)
        s.add(sn)
        rem = 1 / frac
    }
    return s
}

System.print("The continued fraction convergents for the following (maximum 8 terms) are:")
System.print("415/93  = %(cfcRat.call(415, 93))")
System.print("649/200 = %(cfcRat.call(649, 200))")
System.print("√2      = %(cfcQuad.call(2, 1, 0, 1, 8))") 
System.print("√5      = %(cfcQuad.call(5, 1, 0, 1, 8))")
System.print("phi     = %(cfcQuad.call(5, 1, 1, 2, 8))")

Output:

The continued fraction convergents for the following (maximum 8 terms) are:
415/93  = [4/1, 9/2, 58/13, 415/93]
649/200 = [3/1, 13/4, 159/49, 649/200]
√2      = [1/1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408]
√5      = [2/1, 9/4, 38/17, 161/72, 682/305, 2889/1292, 12238/5473, 51841/23184]
phi     = [1/1, 2/1, 3/2, 5/3, 8/5, 13/8, 21/13, 34/21]