Precision of Semi-Exact Redundant Continued Fraction Arithmetic for VLSI
[SPIE '99 (Arithmetic session), July 1999]

Oskar Mencer, Martin Morf, Michael J. Flynn,

abstract.

Continued fractions (CFs) enable straightforward representation of elementary 
functions and rational approximations. We improve the positional algebraic 
algorithm, which computes homographic functions such as $y=\frac{ax+b}{cx+d}$,
given redundant continued fractions $x,y$, and integers $a,b,c,d$. 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 \emph{percentage of exact results} with 12-bit state registers from 78\% 
to 98\%. The maximal error of non-exact results is improved from $\sim~1$ to 
$2^{-8}$. 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.