BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CSL-TR-00-791
       ENTRY:: February 14, 2000 
ORGANIZATION:: Stanford University, Computer Systems Laboratory
       TITLE:: Precision of Semi-Exact Redundant Continued Fraction
Arithmetic for VLSI
        TYPE:: Technical Report
      AUTHOR:: Mencer, Oskar
      AUTHOR:: Morf, Martin
      AUTHOR:: Flynn, Michael J. 
        DATE:: February 2000 
       PAGES:: 20
    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.
       NOTES:: [Adminitrivia ]
         END:: STAN//CSL-TR-00-791