Continued Fraction, Closest Neighbours

Question

For setting the proper divisor/multiplier registers in a phase locked loop, I use a continued fraction expansion, which I stop if either the numerator or denominator of the fraction becomes larger than 4095. This really works well. My question is: Does any algorithm/strategy exist, that gives me the next lower and/or higher value?

Example: with registers of size 32, to approximate pi, I find 22/7 = 3.1429. The next lower would be 25/8 = 3.1250 The next higher would be 19/6 = 3.1667 I currently solve this by an exhaustive search, the following is equivalent matlab/octave code. The actual c-code implementation is more efficient, but this is just a short way to express the principle.

lo = unique((1:31)./floor((1:31)/pi));
hi = unique((1:31)./ceil((1:31)/pi));
rats(lo(2))
rats(hi(end-1))

So to repeat my question in a slightly other way: How to avoid the exhaustive search to find these values?

Typically what I see is that for values up to 4096, is that the closest values are I multiply the best value up to 4096. Eg for pi ~ 22/7 = 4092/1302 Then the answers seems to be in a lot of cases

lo = round(pi*(1302+1))/(1302+1)
hi = round(pi*(1302-1))/(1302-1)

But is this not always the case.

Edit: The original message used unique(sort(...)). Since unique already sorts this was redundant.

Answer 1

Use the Stern Brocot Tree.

for any fraction $\frac{p}{q}$, compute the two (lower and higher) closest ancestors $\frac{p_l}{q_l}$ and $\frac{p_h}{q_h}$.

The next lower will be $$\frac{kp+p_l}{kq+q_l} $$ with the largest $k$ (could be $0$) such that numerator and denominator are in the right bound (lower than 4096). The same for the next higher. So $k=\min((4096-p_l)/p,(4096-q_l)/q)$

If your implementation is correct, computing the closest ancestors takes as long as finding the Bezout coefficient of $p$ and $q$.

---

Complete example : $\frac{17}{7}$

To find the closest lower ancestor, find the Bezout coefficients using the Euclidean Algorithm

You'll find that $$17\times 5-7\times 12=1$$

Hence $\frac{12}{5}$ is the closest lower ancestor and $\frac{17-12}{7-5}=\frac{5}{2}$ is the closest upper ancestor.

Now $k=\min((4096-12)/17,(4096-5)/7)=240$.

Hence $\frac{240\times17+12}{240\times 7+5}=\frac{4092}{1685}$ is the lower closest.