Bit fiddling calculating fraction

[Dik T. Winter]

>
> That is one of the possible terms. The classic book on continued fractions
> is by O. Perron, but I do not know whether it has been translated in English.

I find that there is an excellent article about the subject on Wikipedia:
<http://en.wikipedia.org/wiki/Continued_fraction>

 

[David T. Ashley]

I
looked at it closely ... and I realized that you could make a stronger
statement. You can say specifically that the number of interest is
bracketed on the left and right by the convergent and a specific one of
the
intermediate fractions (but either can be on the left). This appears in
the
documents I cited:

Given successive convergents h[n-2]/k[n-2], h[n-1]/k[n-1] and h[n]/k[n],
We have h[n] = a[n] * h[n-1] + h[n-2] and similar for k[n], where a[n]
is the n-th term in the expression of the continued fraction. When
we use integers in the range a[n]/2 .. a[n] rather than a[n] itself,
we get the fractions that are also "best". (Note: when a[n] is even
there are some rules that state whether a[n]/2 also can be used.)
What you can state is that h[n-1]/k[n-1] is on one side while the
next intermediate fractions and the next convergent are on the other side.

I'm fairly sure you are correct with the statements above. It would require
a lot of thinking for me to be sure (and "big project soon due").

In any case, if you look at this:

http://www.dtashley.com/howtos/2007/01/best_rational_approximation/book_c4_c5.pdf

and if you look at the page containing Equation 5.71, I give the specific
formula and I also mention Dave Eppstein.

Interesting and surprising that some mathematical heavyweights (i.e. you)
apprently hang out at comp.lang.c.

Toodles, Dave.

 

[David T. Ashley]

I
looked at it closely ... and I realized that you could make a stronger
statement. You can say specifically that the number of interest is
bracketed on the left and right by the convergent and a specific one of
the
intermediate fractions (but either can be on the left). This appears
in the
documents I cited:

Given successive convergents h[n-2]/k[n-2], h[n-1]/k[n-1] and h[n]/k[n],
We have h[n] = a[n] * h[n-1] + h[n-2] and similar for k[n], where a[n]
is the n-th term in the expression of the continued fraction. When
we use integers in the range a[n]/2 .. a[n] rather than a[n] itself,
we get the fractions that are also "best". (Note: when a[n] is even
there are some rules that state whether a[n]/2 also can be used.)
What you can state is that h[n-1]/k[n-1] is on one side while the
next intermediate fractions and the next convergent are on the other
side.

I'm fairly sure you are correct with the statements above. It would
require a lot of thinking for me to be sure (and "big project soon due").

In any case, if you look at this:

http://www.dtashley.com/howtos/2007/01/best_rational_approximation/book_c4_c5.pdf

and if you look at the page containing Equation 5.71, I give the specific
formula and I also mention Dave Eppstein.

Interesting and surprising that some mathematical heavyweights (i.e. you)
apprently hang out at comp.lang.c.

Toodles, Dave.

Also, the version control information on that chapter (second-to-last page
of the .PDF) indicates that this was last changed in April of 2003.
However, the reference to Eppstein and his program ... which apparently has
been on the Internet for a long time unchanged ... is probably much older.
I'm too lazy to trace through the version control archives to figure out
when I found Eppstein's program and realized it was equivalent.