Best Rational Approximation Continued Fraction Question

Hi Guys,

As part of the documentation for a numerical library that runs on
microcontrollers, I'm preparing a brief set of pages for microcontroller
software developers to choose the best rational approximation to a real
number subject to constraints on the numerator and denominator. Many of
these inexpensive CPUs have integer multiplication and division
instructions, and multiplying by an integer then dividing by a second
integer is a quick way to approximate.

The pages so far are here:

http://www.dtashley.com/tempposts/sci_math_20071004.pdf

All references below are with respect to these pages in the .PDF file cited
above.

The procedure for finding the enclosing Farey neighbors to a given rational
or irrational number is iron-clad (Algorithm 2.1 and Theorem 2.3).

However, what is the simplest method for determining which of the two Farey
neighbors is closer?

Let's assume that the number to be approximated is rational but with a
denominator too large. In F_{255} and approximating 1/PI, one would rapidly
determine that the following inequality gives the two Farey neighbors.

7/22 < 10000000000 / 31415926536 < 78/245.

It ends up that 78/245 is closer to the middle term than 7/22.

But is there a cheaper way to know this than to numerically evaluate
(10000000000 / 31415926536 - 7/22) and (78/245 - 10000000000 / 31415926536)
and compare to see which difference is smaller?

In other words, is there anything in the continued fraction partial
quotients and convergents that gives this information? A more elegant way?

I think it is provable that for all of the convergents of a number, no
rational number with a smaller denominator is closer. But I'm not sure what
results are possible when one has identified the two Farey neighbors and
wants an elegant way to know which is closer. I have a feeling it would
rely on the higher-order partial quotients and convergents ... if it is
possible at all.

Please feel free to correspond directly as well as post. My mail server
will require that you reply to an automatic reply it sends (anti-SPAM).

Thanks.
--
David T. Ashley (dta@xxxxxxxx)
http://www.e3ft.com (Consulting Home Page)
http://www.dtashley.com (Personal Home Page)
http://gpl.e3ft.com (GPL Publications and Projects)


.

Relevant Pages

  • Re: I want!
    ... Called the "Babylonian method" and it jbexes by trial and error. ... approximation. ... Start with an arbitrary positive start value r (the closer to the ... Repeat steps 2 and 3. ...
    (uk.rec.sheds)
  • Re: I want!
    ... Called the "Babylonian method" and it jbexes by trial and error. ... approximation. ... Start with an arbitrary positive start value r (the closer to the ... Repeat steps 2 and 3. ...
    (uk.rec.sheds)
  • Re: i need help, im stuck
    ... ln+ a = b/r ... This is as close to closed form as you're going to get. ... closer and closer to the answer you seek. ... Then given an approximation a_k, ...
    (sci.stat.math)
  • Re: i need help, im stuck
    ... ln+ a = b/r ... This is as close to closed form as you're going to get. ... closer and closer to the answer you seek. ... Then given an approximation a_k, ...
    (sci.stat.math)