Title :
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
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;
Conference_Titel :
Signals, Systems, and Computers, 1999. Conference Record of the Thirty-Third Asilomar Conference on
Conference_Location :
Pacific Grove, CA, USA
Print_ISBN :
0-7803-5700-0
DOI :
10.1109/ACSSC.1999.831922
