loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Higher Radix Square Rooting
October 1990 (vol. 39 no. 10)
pp. 1220-1231
ASCII Text
x 
 
L. Ciminiera, P. Montuschi, "Higher Radix Square Rooting," IEEE Transactions on Computers, vol. 39, no. 10, pp. 1220-1231, October, 1990.
 
 
BibTex
x
 
@article{ 10.1109/12.59853,
author = {L. Ciminiera and P. Montuschi},
title = {Higher Radix Square Rooting},
journal ={IEEE Transactions on Computers},
volume = {39},
number = {10},
issn = {0018-9340},
year = {1990},
pages = {1220-1231},
doi = {http://doi.ieeecomputersociety.org/10.1109/12.59853},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - JOUR
JO - IEEE Transactions on Computers
TI - Higher Radix Square Rooting
IS - 10
SN - 0018-9340
SP1220
EP1231
EPD - 1220-1231
A1 - L. Ciminiera,
A1 - P. Montuschi,
PY - 1990
KW - nonrestoring square root algorithms; bounds; constraints; feasible algorithms; radix; digit set; representation; radicand bits; starting value; partial remainder bits; digit selection; radix 4; carry-save; digital arithmetic; number theory.
VL - 39
JA - IEEE Transactions on Computers
ER -
 

A general discussion on nonrestoring square root algorithms is presented, showing bounds and constraints delimiting the space of feasible algorithms, for all the choices of radix, digit set and representation of the partial remainder. Two classes of algorithms are then derived from the general discussion, and it is shown how it is possible to determine two parameters with a relevant impact on the implementation: the number of radicand bits to be inspected in order to obtain a starting value, and the number of partial remainder bits to be examined for digit selection. The algorithms for the specific case of radix 4 digit set (-2, -1, 0, +1, +2), and partial remainder represented in carry-save form are derived in order to show that the algorithms introduced can lead to better results than those obtained with algorithms previously presented.

[1] M. Andrews, "Mathematical microprocessor software: A√x comparison,"IEEE Micro, vol. 2, pp. 63-75, May 1982.[2] D. E. Atkins, "Higher-radix division using estimates of the divisor and partial remainders,"IEEE Trans. Comput., vol. C-17, pp. 925-934, Oct. 1968.[3] L. B. Bushard, "A minimum table size result for higher radix nonrestoring division,"IEEE Trans. Comput., vol. C-32, pp. 521-526, June 1983.[4] M. D. Ercegovac, "An on-line square rooting algorithm," inProc. 4th IEEE Symp. Comput. Arithmetic, Santa Monica, CA, Oct. 1978, pp. 183-189.[5] M. D. Ercegovac and T. Lang, "On-line computation of rotation factors," inProc. 8th IEEE Symp. Comput. Arithmetic, Como, Italy, May 1987, pp. 196-203.[6] M. D. Ercegovac and T. Lang, "On-the-fly conversion of redundant into conventional representations,"IEEE Trans. Comput., vol. C-36, no. 7, pp. 895-897, July 1987.[7] M. D. Ercegovac and T. Lang, "Radix-4 square root without initial PLA," inProc. 9th IEEE Symp. Comput. Arithmetic, Santa Monica, CA, Sept. 1989, pp. 162-168.[8] J. Fandrianto, "Algorithm for high speed shared radix 4 division and radix 4 square-root," inProc. 8th IEEE Symp. Comput. Arithmetic, Como, Italy, May 1987, pp. 73-79.[9] "IEEE Standard for Binary Floating-Point Arithmetic" IEEE Standard 754, 1985 IEEE Computer Society.[10] S. Majerski, "Square-rooting algorithms for high-speed digital circuits,"IEEE Trans. Comput., vol. C-34, pp. 724-733, Aug. 1985.[11] G. Metze, "Minimal square rooting,"IEEE Trans. Electron. Comput., vol. EC-14, pp. 181-185, Apr. 1965.[12] V. G. Oklobdzija and M. D. Ercegovac, "An on-line square root algorithm,"IEEE Trans. Comput., vol. C-31, pp. 70-75, Jan. 1982.[13] H. Peng, "Algorithms for extracting square roots and cube roots," inProc. 5th IEEE Symp. Comput. Arithmetic, Ann Arbor, MI, May 1981, pp. 121-126.[14] C. V. Ramamoorthy, J. R. Goodman, and K. H. Kim, "Some properties of iterative square-rooting methods using high-speed multiplication,"IEEE Trans. Comput., vol. C-21, pp. 837-847, Aug. 1972.[15] J. E. Robertson, "A new class of digital division methods,"IRE Trans. Electron. Comput., vol. EC-7, pp. 218-222, Sept. 1958.[16] K. G. Tan, "The theory and implementation of high-radix division," inProc. 4th IEEE Symp. Comput. Arithmetic, Santa Monica, CA, Oct. 1978, pp. 183-189.[17] K. S. Trivedi and M. D. Ercegovac, "On-line algorithms for division and multiplication,"IEEE Trans. Comput., vol. C-26, pp. 681-687, July 1977.[18] K. S. Trivedi and J. G. Rusnak, "Higher radix on-line division," inProc. 4th IEEE Symp. Comput. Arithmetic, Santa Monica, CA, Oct. 1978, pp. 183-189.[19] J. H. P. Zurawski and J. B. Gosling, "Design of high-speed digital divide units,"IEEE Trans. Comput., vol. C-30, pp. 691-699, Sept. 1981.[20] J. H. Zurawski and J. B. Gosling, "Design of a high-speed square root multiply and divide unit,"IEEE Trans. Comput., vol. C-36, pp. 13-23, Jan. 1987.

Index Terms:
nonrestoring square root algorithms; bounds; constraints; feasible algorithms; radix; digit set; representation; radicand bits; starting value; partial remainder bits; digit selection; radix 4; carry-save; digital arithmetic; number theory.
Citation:
L. Ciminiera, P. Montuschi, "Higher Radix Square Rooting," IEEE Transactions on Computers, vol. 39, no. 10, pp. 1220-1231, Oct. 1990, doi:10.1109/12.59853
Usage of this product signifies your acceptance of the Terms of Use.