4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I really like this question. I am not aware of any algorithms, but there is a clear solution for fractions with a denominator of $2^i$: since the prime factors of the denominator are all 2, you can just remove any on bits up to your given confidence. $\endgroup$ – Kittsil Aug 7 '15 at 3:27
  • $\begingroup$ Derp...I should I have thought of that. Still what about denominators that are more general? I'm reading Bishop's foundations of constructive analysis right now and it offers a slightly different method for which this wouldn't be the case so I'm still quite interested in the general question. $\endgroup$ – Jake Aug 7 '15 at 3:37
  • $\begingroup$ I don't know of any. It's a great question, and I look forward to the general answer. $\endgroup$ – Kittsil Aug 7 '15 at 4:06
  • 1
    $\begingroup$ So you could get it into any base you wanted by binary searching over the numerators of for base for the closest value in that base. So that gives an algorithm for converting to an arbitrary base at the very least. So that's some progress. $\endgroup$ – Jake Aug 7 '15 at 4:57
3
$\begingroup$

A brute force solution is to trace the line ay=bx in integer coordinates from the origin to (a,b). Any pair with a smaller number of bits will be along that line segment. This method allows finding either the minimum distance or the smallest (x,y) within the error bounds. It requires o(a+b) steps, and there's plenty of redundancy possible, since eg both (x,y) and (kx,ky) might be found for k >1.

Tracing the line refers to iteratively moving either up or right according to which move minimizes distance to the line; it's a common method for graphics.

$\endgroup$
  • $\begingroup$ As you approach $(a,b)$, the maximum error decreases. If you know the acceptable error beforehand, it would be easy to derive the geometric formula for when steps are guaranteed to start falling within that range. $\endgroup$ – Kittsil Aug 7 '15 at 16:51
  • $\begingroup$ Good point, your vertical distance from the true line is <1 all the way up. $\endgroup$ – KWillets Aug 7 '15 at 19:37
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Neat! I'm wondering how this might relate to the homographic function/continued fraction implementation of real numbers! $\endgroup$ – Jake Aug 7 '15 at 5:38
  • 1
    $\begingroup$ I liked this answer but it wasn't a true answer to my question where as the other one was. I was torn on which one to accept! $\endgroup$ – Jake Aug 8 '15 at 3:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.