Precision of semi-exact redundant continued fraction arithmetic for VLSI

Oskar Mencer; Martin Morf; Michael J. Flynn

doi:10.1117/12.367651

2 November 1999 Precision of semi-exact redundant continued fraction arithmetic for VLSI

Oskar Mencer, Martin Morf, Michael J. Flynn

Proceedings Volume 3807, Advanced Signal Processing Algorithms, Architectures, and Implementations IX; (1999) https://doi.org/10.1117/12.367651
Event: SPIE's International Symposium on Optical Science, Engineering, and Instrumentation, 1999, Denver, CO, United States

Abstract

Continued fractions (CFs) enable straightforward representation of elementary functions and rational approximations. We improve the positional algebraic algorithm, which computes homographic functions such as y equals ax+b/cx+d, given redundant continued fractions x,y, and integers a,b,c,d. The improved algorithm for the linear fractional transformation produces exact results, given regular continued fraction input. In case the input is in redundant continued fraction form, our improved linear algorithm increases the percentage of exact results with 12-bit state registers from 78% to 98%. The maximal error of non-exact results is improved from approximately 1 to 2^-8. Indeed, by detecting a small number of cases, we can add a final correction step to improve the guaranteed accuracy of non-exact results. We refer to the fact that a few results may not be exact as 'Semi- Exact' arithmetic. We detail the adjustments to the positional algebraic algorithm concerning register overflow, the virtual singularities that occur during the computation, and the errors due to non-regular, redundant CF inputs.

Citation Download Citation

Oskar Mencer, Martin Morf, and Michael J. Flynn "Precision of semi-exact redundant continued fraction arithmetic for VLSI", Proc. SPIE 3807, Advanced Signal Processing Algorithms, Architectures, and Implementations IX, (2 November 1999); https://doi.org/10.1117/12.367651

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available