Binary Search for Internal Angle

Robert P. Munafo, 2012 Apr 6

If you know an internal angle and want to find its mu-atom, you can locate it by getting the internal angles of its two larger neighbors. You get the internal angles of those, and their larger neighbors and so on, by an iterative binary search procedure.

This algorithm is also described on the Wikipedia Stern-Brocot tree page under the heading "Mediants and binary search".

Here is an example. Suppose you want to locate the mu-atom whose internal angle is 7/30. The first step is to write down the obvious: 7/30 lies between 0/1 and 1/1 (the two internal angles of the cusp):

0/1 _7/30 1/1

If 0/1 and 1/1 were actually the two larger neighbors of 7/30, we'd be done, but they are not. So the next step is to find the inner neighbor (also called common smaller neighbor) of 0/1 and 1/1. This is done through Farey addition; the inner neighbor is 1/2:

0/1 1/2 1/1

Next, determine where 7/30 lies in the sequence. Since 7/30 is 0.23333333... and 1/2 is 0.5, 7/30 lies between 0/1 and 1/2:

0/1 _7/30 1/2 1/1

Now 0/1 and 1/2 are the candidate larger neighbors. Find their inner neighbor with Farey addition again, then we do the math to find out that 7/30 lies between 0/1 and 1/3:

0/1 _7/30 1/3 1/2 1/1

Continuing: Farey addition on 0/1 and 1/3 shows that their inner neighbor is 1/4, which is higher than 7/30:

0/1 _7/30 1/4 1/3 1/2 1/1

Farey addition on 0/1 and 1/4 shows that their inner neighbor is 1/5, which is lower than 7/30:

0/1 1/5 _7/30 1/4 1/3 1/2 1/1

Farey addition on 1/5 and 1/4 shows that their inner neighbor is 2/9, which is lower than 7/30:

0/1 1/5 2/9 _7/30 1/4 1/3 1/2 1/1

Farey addition on 2/9 and 1/4 shows that their inner neighbor is 3/13, which is lower than 7/30:

0/1 1/5 2/9 3/13 _7/30 1/4 1/3 1/2 1/1

Farey addition on 3/13 and 1/4 shows that their inner neighbor is 4/17, which is higher than 7/30:

0/1 1/5 2/9 3/13 _7/30 4/17 1/4 1/3 1/2 1/1

And finally (!) Farey addition on 3/13 and 4/17 shows that their inner neighbor is (3+4)/(13+17) = 7/30.

0/1 1/5 2/9 3/13 7/30 4/17 1/4 1/3 1/2 1/1

Now we have all the larger neighbors we need, and we can get each of their larger neighbors by going back up the chain: R2.7/30a is the largest mu-atom between R2.3/13a and R2.4/17a, and R2.4/17a lies between R2.3/13a and R2.1/4a, and R2.3/13a lies between R2.2/9a and R2.1/4a, and so on.

revisions: 20010123 oldest on record; 20120406 add Stern-Brocot tree link

Mu-ency main page — index — recent changes — DEMZ

This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2012 Apr 16.

s.27