[ gzip'ed postscript, Acrobat Reader PDF]
Rational arithmetic is about division of two numbers, division of polynomials and/or division of digits. Continued fractions(CFs) enable the development of divide-add structures for digits of rational numbers. Continued fraction arithmetic deals with computing rational functions where input and output values are represented as simple continued fractions. The basic remaining problems of previous work are threefold: choosing the optimal CF-digit representation, converting between simple continued fractions and binary numbers, and error control.
The M-log-Fraction Transform(MFT), introduced in this work, solves all three problems. Instant conversion is shown to be 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 implementation of the CF algorithm to shift-and-add structures, or more specifically, digit-serial arithmetic algorithms for computing rational functions. A multiplication-based scheme can be used to evaluate higher-degree rational approximations.
This thesis demonstrates two applications of the MFT:
(1) a rational arithmetic unit computing functions such as (ax+b)/(cx+d) in a shift-and-add-based 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 the efficient evaluation of rational approximations.
[ gzip'ed postscript, Acrobat Reader PDF]
oskar@stanford.edu