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
(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.