Report Number: CSL-TR-00-791
Institution: Stanford University, Computer Systems Laboratory
Title: Precision of Semi-Exact Redundant Continued Fraction
Author: Mencer, Oskar
Author: Morf, Martin
Author: Flynn, Michael J.
Date: February 2000
Abstract: Continued fractions (CFs) enable straightforward
representation of elementary functions and rational
approximations. We improve the positional algebraic
algorithm, which computes homographic functions.
The improved algorithm for the linear fractional
transformation produces exact results, given regular
continued fraction input. In case the input is in
redundant continued fraction form, our improved linear
algorithm increases the percentage of exact results
with 12-bit state registers from 78% to 98%. The
maximal error of non-exact results is improved.
Indeed, by detecting a small number of cases, we can
add a final correction step to improve the guaranteed
accuracy of non-exact results. We refer to the fact
that a few results may not be exact as "Semi-Exact"
arithmetic. We detail the adjustments to the positional
algebraic algorithm concerning register overflow, the
virtual singularities that occur during the computation,
and the errors due to non-regular, redundant CF inputs.