Stern-Brocot Tree

Binary Encoding, a Second Look

As we have seen, Algorithm 1 finds L-R encoding for any (positive) rational number m/n. However, intermediate fractions generated by the algorithm are not quite those one would expect from the manner in which the encoding has been defined. With m/n = 4/7, the algorithm generates successively, 4/7, 4/3, 1/3, 1/2, 1/1.

On the other hand,

tLRLL = [0/1, 1/0]LRLL = [0/1, 1/1]RLL = [1/2, 1/1]LL = [1/2, 2/3] = [1/2, 3/5].

In terms of single numbers, the sequence is 1/1, 1/2, 2/3, 3/5, 4/7, and we as well may wonder why does the whole thing really work. Of course a proof is a proof and, since we have one, we know that the algorithm works. In what follows, I establish a geometric interpretation for the algorithm which puts the L-R encoding and the algorithm back into the scope of our intuition.

Two identities f(RS) = f(S) + 1 and 1/f(LS) = 1/f(S) + 1 form a basis for our derivation. Given a fraction m/n and its (unique) encoding S, we obtain another fraction f(RS) through the first formula. f(RS) is uniquely determined by m/n which enables us to define a function fR as fR(m/n) = m/n+1 = (m+n)/n. It all may appear as a vacuous manipulation of mathematical symbols; for, obviously, m/n+1 is a function of m/n. The point was of course not in affirming a trivial mathematical fact but in pointing out that this trivial mathematical fact underlies the algorithm at hand. From the second formula we derive another function fL as fL(m/n) = m/(n+m). An easily proven formula fR(1 - fL) = 1 may also be observed on the tree.

In the diagram below, red lines trace the action of fR, the blue lines that of fL. Starting with row #1, there are three lines emanating from every fraction on the tree: two (one red, one blue) point to the next row, one line points to the row above. Because of the latter property, for every fraction m/n, there is a unique way upwards that connects it to the fraction 1/1. For example, for m/n = 4/7 we get successively, 4/7, 4/3, 1/3, 1/2, 1/1 which, of course, is the sequence that has been generated by the algorithm.

This also shows that 4/7 = fLfRfLfL(1/1).

One more observation will prove helpful. For a given row, all red lines from its terms downwards end on the right half of the row below. Likewise, all the blue lines connect fractions in one row to the left-hand side fractions of the next row. We have already observed how the two halves of a row (of numerators) are formed from the previous row. Bearing in mind that in the Stern-Brocot tree, sequences of denominators are obtained by reversing the order of the sequences of numerators, we see that, extended to the tree of fractions our old observation confirms the new one: to obtain the right half of a row, apply function fR to the fractions of the previous row. To obtain the left half, apply function fL.

Let's compare 4/7 = fLfRfLfL(1/1) with f(LRLL) = 4/7 which is obtained from tLRLL = [1/2, 3/5]. In the latter, we first multiply by the leftmost L, then by R, then twice by L. 4/7 = fLfRfLfL(1/1) suggests that carrying operations in the reverse order is more relevant to the algorithm. The important observation is that, while in tLRLL factors L and R applied on the right, in fLfRfLfL(1/1) fL and fR appear on the left. What's the mystery?

Extend definition of fR and fL columnwise to the tree (or the matrix) case: fR[x1/y2, y1/x2] = [fR(x1/y2), fR(y1/x2)]. Similarly, fL[x1/y2, y1/x2] = [fL(x1/y2), fL(y1/x2)]. Thus, for example, fL[0/1,1/0] = [0/1,1/1]. Furthermore, fLfRfLfL[0/1, 1/0] = fLfRfL[0/1, 1/1] = fLfR[0/1, 1/2] = fL[1/1, 3/2] = [1/2, 3/5] which, as we know, reduces to the expected 4/7. Written a little differently, tLRLL = fLfRfLfLt which clearly relates the two ways of deriving L-R encoding. With a small additional effort we can simplify this expression. Recollect, that t2 = I, the identity matrix. Then tLRLL = tLttRttLttLtt = (tLt)(tRt)(tLt)(tLt)t. May it be that tLt = fL and tRt = fR? This is indeed the case. From the definition, fR[x1/y2, y1/x2] = [fR(x1/y2), fR(y1/x2)], fR[x1/y2, y1/x2] = [fR(x1/y2), fR(y1/x2)], the matrix representation of fR is [1/0,1/1] while the representation of fL is [1/1, 0/1]. In other words, fR = L while fL = R. By simple inspection we also verify that tLt = R and tRt = L. Thus all parts fit nicely together: tLRLL = RLRRt.

As a result, we got two binary encodings complementary to each other. Consider the "left-side" one (namely RLRRt, as opposed to the "right-side" encoding tLRLL.) Replacing R with 0 and L with 1 gives a binary string 0100 which converts to the decimal 4. A glance at the last row of the tree above reveals that 4/7 is located in the last row of the tree in the fifth position. Should we decide to start counting from 0, the position of 4/7 would become 4th. So let's go for it. Start counting from 0. Every time we prepend a 0 to a given binary string the string goes to the left in the next row. When we prepend 1, the string goes to the right. So we see, that in any row, binary encoding of fractions in the left half of the row starts with 0. The encodings in the right half start with 1. The net result of this observation is that encodings of the fractions in any given row are given by consecutive binary numbers: (for row #3)

How do we get 4/3? First, 4/3 is located in the third row. Therefore we shall need 3 binary digits to represent this fraction. Second, it's the fourth fraction in the row. (The first is the 0th!) Thus its binary encoding is 100 which converts to LRR for the "left-side" encoding or into its complementary RLL "right-side" encoding.

Problem: Find the fraction in the 10-th position of the 4-th row of the Stern-Brocot tree. (Remember to start counting from 0.)

Solution: Using for binary digits, 10th position is represented by 1010 which converts to LRLR for the "left-hand" encoding and to RLRL for the "right-hand" encoding. LRLR[0/1, 1/0] = LRL[0/1, 1/1] = LR[1/1, 2/1] = L[1/2, 2/3] = [3/2, 5/3]. Which boils down to 8/5.

Problem: Find location on the tree of a fraction whose "right-side" encoding is LRLLRLRR.

Solution: Its "left-side" encoding is RLRRLRLL which converts to 010010112 = 7510. Therefore, the corresponding fraction is located in the row #8, position 75 where the count starts from 0.

Copyright © 1966-2016 Alexander Bogomolny