Re: continued fractions

Thank you for replying! I think this is the first reply I've had on
these concepts.

anton@xxxxxxxxxxxxxxxxxxxxxxxxxx (Anton Ertl) wrote:

Jonah Thomas <jethomas5@xxxxxxxxx> writes:
Second point. The Forth */ does not round. Its division truncates.

Or floors. You can approximate a rounding */ as follows:

: */r ( n1 n2 n3 -- n4 )
>r m* r@ 2/ m+ r> fm/mod nip ;

There will still be a little bias if the divisor is odd, though. You
could correct for that by adding (or, for negative divisors,
subtracting) 1 about half of the time.

Yes, you can make a rounding version of */ . I've never heard of anybody
using one. I wrote one in Forth a long time ago and never used it except
for testing. It improved the result on average by half a bit. It was
written in Forth which at that time was considerably slower than */
written in assembler.

I'd expect the difference to be somewhat less important for 32-bit or
64-bit systems than for 16-bit. While you will on average use smaller
numbers more often than larger numbers, still you have the opportunity
to use larger numbers for which half a bit improvement is less important
than usual.

I claim that continued-fraction results will be less optimal for */ than
they would be for arithmetic that rounds, and so other solutions might
be better for */ . I gave some examples that I say give better results
for pi in 16-bits with */ .

Even for arithmetic that rounds, the continued fraction method is
designed to find the rational approximation which comes closest to the
actual value. I do not yet have a proof or a disproof of the idea that
some other rational approximation might give the best 16-bit value more
often, or the best 32-bit value etc. While a rational approximation that
is significantly worse than the best one cannot give good results, the
pattern of rounding errors might possibly be better for something that
isn't the continued-fraction best -- or possibly it's provable that this
can't happen.
.

Relevant Pages

  • Re: calculate approx of decimal number ?..
    ... > How to calculate the approximation of a given decimal number, ... It's called "rounding" and you can find different methods of ... > of standard math library functions like say floor, ceil etc. ...
    (comp.lang.cpp)
  • Re: Rational approximation of exponential function
    ... >>Taylor series, or am totaly wrong? ... > theory does not handles time delay systems very well. ... > error in the expressions due to approximation would go to zero, provided the rational approximation converges. ...
    (sci.math)
  • Re: Comparing two notions of computable number
    ... 1) a real number a is computable iff there exists a Turing machine ... which for given rational number eps produces a rational approximation ... Definition 2 seems to be Turing's original definition. ...
    (comp.theory)
  • Re: Polynomial fitting routines?
    ... >>> I'm looking for an algorithm that will fit a polynomial to ... > I actually derived the integrals in Eq. ... rational approximation is stuffed under the heading "Padé ...
    (comp.lang.fortran)