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.