Arithmetic Algorithms based on Logarithmic Continued Fractions
==============================================================
Oskar Mencer
In general, rational approximations converge faster, over a larger interval,
than polynomial approximations. Continued fractions are equivalent to
rational approximations.
M-log-fractions, introduced in this talk, efficiently connect continued
fractions and binary numbers. Two applications of the continued fraction
algorithm to arithmetic algoritms are:
(1) Designing an SRT-division-like arithmetic unit (digit-recurrence)
capable of computing x/y, but also composite functions such as
(ax+b)/(cx+d), or any other homographic function.
(2) Area-efficient evaluation of arbitrary rational functions or
approximations without explicit division.
All proposed algorithms can be described as "most-significant-digit-first",
or online algorithms. Given our M-log-fraction, we discuss the design of
digit-serial arithmetic units for rational functions. The insights from the
M-log-fractions simplify the design of higher radix arithmetic units
for rational functions, especially SRT-division.