debugMinor
"Compressing" rationals given error bounds
Viewed 0 times
errorcompressingboundsrationalsgiven
Problem
I'm working on implementing some exact real arithmetic operations for fun. I've got the rough outline of how I want to do things as well and have figured out how to write most of the important algorithms (though I have not properly implemented them just yet).
Going against the "pre-mature optimization is bad, m'kay" philosophy I am wondering about a few things. So reducing fractions is one way to reduce the size of rationals, sure, but it isn't perfect. If you knew you only had to be within a certain range you could do better by changing the value. For instance say I need to add $1$ and $\frac{1}{8}$ to with in $\frac{1}{2}$. I don't need to full precision, I can just return 0 in fact. More beneficially say I had something like $\frac{2^{16}+1}{2^{32}}$, if I only need say something like $\frac{1}{2^{15}}$ precision, I can approximate this rational as $\frac{2^{16}}{2^{32}}$ and then reduce that to $\frac{1}{2^{16}}$.
This are some contrived cases but I think there is a generally useful optimization to be done here. Are there algorithms which, given an error bound, can find the smallest (in bits) rational number within the specified bounds of another given rational number?
Most of my algorithms tend to produce rationals with power of two denominators so I am particularly interested in that case.
Going against the "pre-mature optimization is bad, m'kay" philosophy I am wondering about a few things. So reducing fractions is one way to reduce the size of rationals, sure, but it isn't perfect. If you knew you only had to be within a certain range you could do better by changing the value. For instance say I need to add $1$ and $\frac{1}{8}$ to with in $\frac{1}{2}$. I don't need to full precision, I can just return 0 in fact. More beneficially say I had something like $\frac{2^{16}+1}{2^{32}}$, if I only need say something like $\frac{1}{2^{15}}$ precision, I can approximate this rational as $\frac{2^{16}}{2^{32}}$ and then reduce that to $\frac{1}{2^{16}}$.
This are some contrived cases but I think there is a generally useful optimization to be done here. Are there algorithms which, given an error bound, can find the smallest (in bits) rational number within the specified bounds of another given rational number?
Most of my algorithms tend to produce rationals with power of two denominators so I am particularly interested in that case.
Solution
Continued fractions are an efficient way to enumerate rational numbers that are a good approximation of your number $x$. In particular, given a real number $x$, you can generate a sequence of truncated continued fractions $a_i/b_i$, where each rational number $a_i/b_i$ is a better approximation to $x$ than any other fraction whose denominator is $\le b_i$. So, a reasonably good algorithm for your problem is to compute the sequence of truncated continued fractions, and keep the last one whose denominator is smaller than your bound. This doesn't find the best rational approximation for a given number of bits, but it does give you a best rational approximation for a given upper bound on the size of the denominator.
To compare to KWillets' excellent answer: KWillets' method takes something like $\Theta(a+b)$ steps, but finds the optimal solution (measured by bits). Continued fractions takes something like $\Theta(\lg b)$ steps, but isn't guaranteed to find the optimal answer (measured by number of bits); it's only guaranteed to find the optimal answer if you measure by the size of the denominator. KWillets' method seems better if $a,b$ are not too large. However, if they are very large, then a continued fractions-based method might become more attractive.
To compare to KWillets' excellent answer: KWillets' method takes something like $\Theta(a+b)$ steps, but finds the optimal solution (measured by bits). Continued fractions takes something like $\Theta(\lg b)$ steps, but isn't guaranteed to find the optimal answer (measured by number of bits); it's only guaranteed to find the optimal answer if you measure by the size of the denominator. KWillets' method seems better if $a,b$ are not too large. However, if they are very large, then a continued fractions-based method might become more attractive.
Context
StackExchange Computer Science Q#45076, answer score: 4
Revisions (0)
No revisions yet.