Best rational approximation with numerator/denominator less than 255 An old problem: I have rational numbers which I want to approximate with the best fraction where both the numerator and denominator are written on eight bits, so between $0$ and $255$. Is there an algorithmic way to find it? If not, what can I do ?
 A: The simplest answer to this is to use the Stern-Brocot tree, which can be thought of as a nice visual way to look at the Continued Fraction expansion.
Basically, there will be three terms you will need to look at, which I will call $L$, $R$, and $F$. $F$ is the current fraction, and $L$ and $R$ are the left and right "parents" of the current fraction in the tree. You will also need $B$, the current "best" rational you have found.
To begin this process, initialize $L = 1/0$, $R = 0/1$, ignoring for now that they aren't really fractions. Also initialize $F = 1/1$ and $B = \infty$. Then the basic routine to approximate a real $x$ is this:

*

*For your real $x$, see if you have $x < F$ or $x > F$.

*If you have $x < F$, then replace $L$ with $F$, and replace $F$ with $\text{mediant}(R,F)$.

*If you have $x > F$, then replace $R$ with $F$, and replace $F$ with $\text{mediant}(L,F)$.

*Check if your new value of $F$ is a better approximation than your current best $B$. If so, update $B$ with the value of the new $F$.

The "mediant" of two fractions $a/b$ and $c/d$ is just $(a+c)/(b+d)$, so you add their numerators and denominators individually.
And that's it. You do the above until you have gotten to an $F$ that has a larger denominator than your max.
If you look visually at the Stern-Brocot tree (https://upload.wikimedia.org/wikipedia/commons/thumb/3/37/SternBrocotTree.svg/400px-SternBrocotTree.svg.png), what you are doing is just traversing it, going left or right based on whether your current rational is less than or greater than the target. This gives you a series of approximations to your real $x$ with increasing rational complexity.
Doing it the above way gives you all the "semiconvergents," which generalize the convergents (continued fraction truncations). They contain all the best rational approximations with less than some given denominator. As you continue the above algorithm, you will tend to get closer and closer to your rational, although you may have some points where the error temporarily gets worse as you bounce toward the next convergent. However, as long as you are always storing the best rational you've found so far, you'll easily be able to determine once you've gotten the best one possible.
Some info here, along with additional theorems:  https://en.wikipedia.org/wiki/Continued_fraction#Semiconvergents
