Analysis of the lookup table size for square-rooting

Author

Parhami, Behrooz

Author_Institution

Dept. of Electr. & Comput. Eng., California Univ., Santa Barbara, CA, USA

Volume

2

fYear

1999

fDate

24-27 Oct. 1999

Firstpage

1327

Abstract

Convergence methods are widely used for division, reciprocation, and square-rooting. With such methods, it is common to use an initial table lookup step for obtaining an approximate result that leads to faster convergence. In the case of division and reciprocation, the required table size has been extensively analyzed and closed form formulas are available for the table length and width, given a desired maximum error. We offer similar analyses for square-rooting, deriving necessary and sufficient conditions on the length and width of a lookup table that yields a result with a maximum error of r/sup -h/, where r is the radix, or that provides the first h digits of the square root correctly.

Keywords

approximation theory; convergence of numerical methods; digital arithmetic; error analysis; table lookup; approximate result; closed form formulas; convergence methods; division; initial table lookup; lookup table size; maximum error; necessary conditions; reciprocation; square-rooting; sufficient conditions; table length; table width; Approximation algorithms; Computer errors; Convergence; Delay; Digital arithmetic; Error analysis; Error correction; Hardware; Programmable logic arrays; Table lookup;

fLanguage

English

Publisher

ieee

Conference_Titel

Signals, Systems, and Computers, 1999. Conference Record of the Thirty-Third Asilomar Conference on

Conference_Location

Pacific Grove, CA, USA

ISSN

1058-6393

Print_ISBN

0-7803-5700-0

Type

conf

DOI

10.1109/ACSSC.1999.831922

Filename

831922