When answering a question on Stackoverflow I got curious about how to find the optimal $\frac pq$ approximation for a real number, $r$, where $p$ and $q$ are integers that are limited by the integer type's number of bits – or a lower limit, like $\sqrt{2^{bits-1}-1}$ which would allow multiplication of two of these fractions without risking overflow. In the original question OP chose this method:
$$p = 100000r$$
$$q = 100000$$
This results in larger errors than necessary when converted back and compared to the original $r$. I know the errors are unnecessarily large because I've found better approximations when testing alternative methods myself.
My question is twofold:
- Is there a way to find the optimal $\frac pq$ pair without using a numerical convergence algorithm (which is what I'm working on right now)? I'm hoping that there's a method that makes a calculation that results in $\le 4$ combinations of $\frac pq$ to try out to find the best approximation.
- If there isn't, how should I design the algorithm to make sure I always find the optimal fractional approximation while keeping the complexity (number of iterations) reasonably low?
My current algorithm starts with $p$ or $q$ at the maximum allowed for the $int$ type used and I'm testing against known approximations for $\pi$, such as $\frac{1068966896}{340262731}$ which is the best approximation when the integer type is an $int_{32}$, given that the numerator can be negative and $p$ must therefore be in the range $±2^{31}-1$, i.e. $[-2147483647, +2147483647]$.
If we take $r = \pi$ as an example and the $int$ type is an $int_{16}$, the algorithm will start with these values:
$$p = 2^{15}-1 = 32767$$
$$q = \left\lceil\frac{2^{15}-1}{\pi}\right\rceil = 10431$$
It will then repeatedly decrease either $p$ or $q$ depending on which one that gives the lowest error when converted back and compared to $r$. It also saves the best result so far:
if $\left\lvert \frac pq – r \right\rvert \lt e_{low}$ save the $\frac pq$ pair and the new $e_{low}$.
This goes on until either $p$ or $q$ reaches $0$. The $\frac pq$ combination that gave the smallest error, $e_{low}$, becomes he result after applying the $gcd$.
This seems to work but I don't know math enough to know that it actually does for any upper integer limit that I impose. It has worked with the limits I have tested though. It's also extremely slow. When trying $int_{64}$ approximations it became clear that I needed shortcuts. It just takes too many iterations to be of any practical use. I added a $gcd$ shortcut and changed the $e_{low}$ comparison to include equality with $e_{low}$:
$$\left\lvert\frac pq – r \right\rvert \le e_{low}$$
When this condition was met I used the $\gcd(p,q)$ to skip ahead. This skipping made it a lot faster but it also missed some optimal solutions so I added something to get out of a possible local minimum: If $gcd \gt 2$ I simply multiplied both $p$ and $q$ with $2$. This improved things a lot – but it was still a bit slow and it still missed optimal solutions. I then tried multiplying with $3$ for even $gcd$s and $2$ for odd $gcd$s but there was no improvement in the result that I could see. It was obviously a bit slower though.
I realize that I'm just guessing and need some pointers in the right direction.
I'm limited by having studied high school math 30+ years ago – and I haven't used it much since then – so don't worry about overexplaining things. This limitation has likely made me incapable of recognizing possible solutions to this very problem when I searched for it…
Best Answer
A best approximation of a real number $r$ is a rational fraction $a/b$ with $b>0$ such that for every rational fraction $c/d$ with $d \le b$ and $c/d \ne a/b$, $$\left| r - \frac{a}{b}\right| < \left|r - \frac{c}{d}\right|$$
Theorem: Every best approximation of a number $r$ is either a convergent or an intermediate fraction of the continued fraction representing $r$ (if you include a "$-1$'th order convergent $1/0$).
For example: if $r = \pi$, the continued fraction representation starts $3 + 1/(7 + 1/(15 + 1/(1 + ...)))$. The first few convergents are $$\frac{1}{0}, \frac{3}{1}, \frac{22}{7}, \frac{333}{106}, \frac{355}{113}$$ The intermediate fractions between $1/0$ and $22/7$ are $$\frac{4}{1}, \frac{7}{2}, \frac{10}{3}, \frac{13}{4}, \frac{16}{5}, \frac{19}{6}$$ The intermediate fractions between $3/1$ and $333/106$ are $$ \frac{25}{8}, \frac{47}{15}, \frac{69}{22}, \frac{91}{29}, \frac{113}{36}, \ldots, \frac{311}{99}$$
The first few best approximations of $\pi$ are $$\frac{3}{1}, \frac{13}{4}, \frac{16}{5}, \frac{19}{6}, \frac{22}{7}, \frac{179}{57}, \frac{201}{64}, \frac{223}{71}, \frac{245}{78}, \frac{267}{85}, \frac{289}{92}, \frac{311}{99}, \frac{333}{106}, \frac{355}{113}$$