Euclid/Stern-Broot algorithms

For the benefit of those who would like but have difficulties to implant
tree navigation in tones and by procrastination to resume my web pages
writing.

There exist a unique simple mathematical structure that appears
superficially as several distincts objets (Stern-Brocot tree, Euclid tree,
binary rank tree, modular matrix 2x2 tree) or very close objects like Farey
series, continued fractions and Euclid algorithm.

Navigation for tones in this structure is very easy.

There are two essential algorithms : to go up and to go down. In my
convention, like in nature, root is low and leaves are high. I show yet my
logarithmic representation of Stern-Brocot subtree in first octave.

http://www.aei.ca/~plamothe/pix/stern-brocot.gif

[To go up]

In basic approach, for going up in Stern-Brocot tree, starting with 1/1
value, we have to keep trace of current ratio x/y and precedent adjacent
left a/b and right c/d ratios. To go right, for example, is to put value
x/y in left a/b and value (x+c)/(y+d) in current x/y.

Knowing isomorphism of Stern-Brocot and modular matrix trees it's possible to
clarify algorithm. Current x/y is identified with matrix (c,d)(a,b) were
(c,d) and (a,b) are the left and right descending columns of the matrix.

Starting with identity matrix (1,0)(0,1) then to go right is to add left
column value in right one, and to go left is to add right column value in
left one. Is'nt cute ? At end, adding rows gives ratio in Stern-Brocot tree
and adding columns gives ratio in Euclid tree.

Example :

What is the ratio of rank 565 (1000110101 binary form) in Stern-Brocot tree
and then in Euclid tree ?

In rank 1000110101, the first 1 represents starting identity matrix and,
subsequently, 0 represents "to go left" and 1 "to go right".

1 (1,0)(0,1)
0 (1,1)(0,1)
0 (1,2)(0,1)
0 (1,3)(0,1)
1 (1,3)(1,4)
1 (1,3)(2,7)
0 (3,10)(2,7)
1 (3,10)(5,17)
0 (8,27)(5,17)
1 (8,27)(13,44)

Adding rows gives 21/71 in Stern-Brocot tree.
Adding colums gives 57/35 in Euclid tree.

If we want restriction at particular subtree like first octave, a final
operation has to be added representing restriction. Adding rows represents
starting at root 1/1 for all tree. Here, (8a+13b)/(27a+44b) represents
value of rank 565 in subtree of root a/b. It's a multiplication of the
matrix by vector (a,b). Thus, ratio of rank 565 in first octave is
(8*3+13*2)/(27*3+44*2) = 50/169.

To go up in Euclid tree only is yet simpler. I give only example here.

1 1/1
0 1/2
0 1/3
0 1/4
1 5/4
1 9/4
0 9/13
1 22/13
0 22/35
1 57/35

[To go down]

If we ask what is the rank of 21/71 in Stern-Brocot tree, we can't directly
go down for precedent adjacent left and right ratios are unknown. We can,
in the basic manner, start with 1/1 and go up, comparing 21/71 and current
value to know if we go left or right. But rows have to be added for
comparison.

Knowing Euclid and Stern-Brocot are transposed trees, we can do an almost
magic
go down in Euclid tree. Transposed trees implies that ranks 1000110101 and
1101011000 have their values permuted in Stern-Brocot and Euclid. For
transposition, first 1 is fix and others are exchanged, last becoming first.

Algorithm is so easy than I give example first :

21 21 21 21 13 5 5 2 2 1
71 50 29 8 8 8 3 3 1 1

0 0 0 1 1 0 1 0 1 (1)

Rank in Euclid tree has to be read right to left 1101011000 and
transposition becomes thus only transfert of last 1 in first place. Answer
for rank in Stern-Brocot is 1000110101 or 565 in decimal.

It's derived from Euclid algorithm for GCD. It's why I name Euclid tree the
transposed Stern-Brocot tree as representing all ways followed by his
algorithm << Greater value is replace with difference >>. Since starting
fraction is reduced, the final values are (1 1). If fraction was not
reduced, double GCD would be obtained.

At end, values lesser than 1 are represented by 0, and the others by 1.

[What about continued fractions ?]

Continued fractions calculation is strictly equivalent to a going up in
Stern-Brocot tree with stops only when direction (left/right) is changing
(where are best approximations). However multiplication has to be used in
algorithm.

Rank in Stern-Brocot tree and continued fraction [a b c d ..]
representation are strictly equivalent but better evidence occurs with
little modification on traditional formalism. I add the last 1 in
calculation so the last value in [] is diminuished by 1 compared with
traditional.

[a b c ... d] = a + 1/(b + 1/(c + 1 ... /(d + 1)))
^

By example, to clarify possible ambiguouness for first values we have :

[a b 1] = a + 1/((b + 1)/(1 + 1)) = (2ab + a + 2)/(2b + 1)
[a b] = a + 1/(b + 1) = (ab + a + 1)/(b + 1)
[1 b] = 1 + 1/(b + 1) = (b + 2)/(b + 1)
[0 b] = 0 + 1/(b + 1) = 1/(b + 1)
[0 1] = 0 + 1/(1 + 1) = 1/2
[a] = (a + 1)/1
[1] = 2/1
[0] = 1/1

Now, comparing rank in Stern-Brocot tree and adjusted formalism for
continued fractions, we see that values in [] are alternatively the number
of successive 1 and successive 0 in corresponding branch of Stern-Brocot
tree :

[03] [021] [0111] [012] [12] [111] [21] [3]

[02] [011] [11] [2]

[01] [1]

[0]

1 [0] = 1/1
10 [01] = 1/2
11 [1] = 2/1
100 [02] = 1/3
101 [011] = 2/3
110 [11] = 3/2
111 [2] = 3/1
1000 [03] = 1/4
1001 [021] = 2/5

11111110001111100 [6 3 5 2] = 322/51
10000001110000011 [0 6 3 5 2] = 51/322

** RULES **

1. First 1 is ignored
2. [0 x ..] = 1/[x ..]
3. Don't forget to add last 1 in calculation

With our example, rank 565 == 1000110101 == [3 2 1 1 1 1] = 21/71

Question : Give the continued fraction of 57/35
which has rank 565 in Euclid tree ?

By simple transposition of [3 2 1 1 1 1] the answer is [1 1 1 1 2 3].

Pierre Lamothe