| Binary Search for Internal Angle |
Robert P. Munafo, 2001 Jan 23.
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 common smaller neighbor of 0/1 and 1/1. This is done through Farey addition; the common smaller 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 get 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.
This work is licensed under a
Creative Commons Attribution 2.5 License
.