sidef-scripts/Math/stern_brocot_encoding_matrix_form.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# Date: 10 February 2018
# https://github.com/trizen

# Encode a given fraction into a string of L's and R's,
# indicating the turning points in the Stern-Brocot tree.

# The decoding function takes a string of L's and R's and
# constructs the fraction by navigating the Stern-Brocot tree.

# See also:
#   https://www.youtube.com/watch?v=qPeD87HJ0UA
#   https://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree

func stern_brocot_encode (Number r) {
    var (m, n) = r.abs.nude

    var e = ''

    while (m != n) {
        if (m < n) {
            e += 'L'
            n -= m
        }
        else {
            e += 'R'
            m -= n
        }
    }

    return e
}

func stern_brocot_decode (String e) {
    var (a, b, c, d) = (1, 0, 0, 1)

    e.each { |t|
        if (t == 'L') {
            a += b
            c += d
        }
        else {
            b += a
            d += c
        }
    }

    return [[a,b],[c,d]]
}

func matrix2rat (Array A) {
    (A[0][0] + A[0][1]) / (A[1][0] + A[1][1])
}

say stern_brocot_decode(stern_brocot_encode(5/7))       # [[3, 2], [4, 3]]
say stern_brocot_decode(stern_brocot_encode(43/97))     # [[4, 39], [9, 88]]
say stern_brocot_decode(stern_brocot_encode(97/43))     # [[88, 9], [39, 4]]

say ''

say stern_brocot_encode(3/11)       # LLLRL
say stern_brocot_encode(19/8)       # RRLLRL

say ''

say stern_brocot_decode('LLLRL')        # [[2, 1], [7, 4]]
say stern_brocot_decode('RRLLRL')       # [[12, 7], [5, 3]]

say ''

say stern_brocot_decode('LRLRLRLRLRLRLRLRLRLRLRLRLRLRLR')       # [[514229, 832040], [832040, 1346269]]
say stern_brocot_decode('RLRLRLRLRLRLRLRLRLRLRLRLRLRLRL')       # [[1346269, 832040], [832040, 514229]]

say ''

say stern_brocot_decode('RLLRR')                    # [[3, 7], [2, 5]]
say stern_brocot_decode('RLLRRLL')                  # [[17, 7], [12, 5]]
say stern_brocot_decode('RLLRRLLRR')                # [[17, 41], [12, 29]]
say stern_brocot_decode('RLLRRLLRRLL')              # [[99, 41], [70, 29]]
say stern_brocot_decode('RLLRRLLRRLLRR')            # [[99, 239], [70, 169]]
say stern_brocot_decode('RLLRRLLRRLLRRLL')          # [[577, 239], [408, 169]]
say stern_brocot_decode('RLLRRLLRRLLRRLLRR')        # [[577, 1393], [408, 985]]

say ''

say matrix2rat(stern_brocot_decode('RLLRRLLRRLLRRLLRRLL'))      # 1.414213...