The M-log-Fraction Transform (MFT) for Rational Arithmetic
[submitted to Transaction on Computers]

Oskar Mencer, Michael J. Flynn, Martin Morf

abstract.

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
rational functions. A multiplication-based scheme can be used to evaluate 
higher order rational approximations.

We show two applications of the MFT:

(1) a 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.

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.