Report Number: CSL-TR-99-784
Institution: Stanford University, Computer Systems Laboratory
Title: The M-log-Fraction Transform (MFT) for Computer Arithmetic
Author: Mencer, Oskar
Author: Flynn, Michael J.
Author: Morf, Martin
Date: July 1999
Abstract: State-of-the-art continued fraction(CF) arithmetic enables us to compute rational functions so that input and output values are represented as simple continued fractions. The main problem of previous work is the conversion between simple continued fractions and binary numbers. The M-log-Fraction Transform(MFT), introduced in this work, enables us to instantly convert between binary numbers and M-log-Fractions. Conversion is related to the distance between the '1's of the binary number. Applying M-log-Fractions to continued fraction arithmetic algorithms reduces the complexity of the CF algorithm to shift-and-add structures, and more specifically, digit-serial arithmetic algorithms for (homographic) rational functions. We show two applications of the MFT: (1) a high radix rational arithmetic unit computing (ax+b)/(cx+d) in a shift-and-add structure. (2) the evaluation of rational approximations (or continued fraction approximations) in a multiplication-based structure. In (1) we obtain algebraic formulations of the entire computation, including the next-digit-selection function. For high radix operation, we can therefore partition the selection table into arithmetic blocks, making high radix implementations feasible. (2) overlaps the final division of a rational approximation with the multiply-add iterations. The MFT bridges the gap between continued fractions and the binary number representation, enabling the design of a new class of efficient rational arithmetic units and efficient evaluation of rational approximations.
http://i.stanford.edu/pub/cstr/reports/csl/tr/99/784/CSL-TR-99-784.pdf