New Svoboda-Tung division

Luis A. Montalvo, Keshab K Parhi, Alain Guyot

Research output: Contribution to journalArticle

4 Citations (Scopus)

Abstract

This paper presents a general theory for developing new Svoboda-Tung (or simply NST) division algorithms not suffering the drawbacks of the "classical" Svoboda-Tung (or simply ST) method. NST avoids the drawbacks of ST by proper receding of the two most significant digits of the residual before selecting the most significant digit of this receded residual as the quotient-digit. NST relies on the divisor being in the range [1, 1 + •), where • is a positive fraction depending upon: 1) the radix, 2) the signed-digit set used to represent the residual, and 3) the receding conditions of the two most significant digits of the residual. If the operands belong to the IEEE-Std range [1, 2), they have to be conveniently prescaled. In that case, NST produces the correct quotient but the final residual is scaled by the same factor as the operands, therefore, NST is not useful in applications where the unsealed residual is necessary. An analysis of NST shows that previously published algorithms can be derived from the general theory proposed in this paper. Moreover, NST reveals a spectrum of new possibilities for the design of alternative division units. For a given radix-b, the number of different algorithms of this kind is b 2 /4.

Original language English (US) 1014-1020 7 IEEE Transactions on Computers 47 9 https://doi.org/10.1109/12.713319 Published - Dec 1 1998

Division
Digit
Quotient
Signed
Divisor
Range of data
Unit
Necessary
Alternatives

Keywords

• Computer arithmetic
• Digit-recurrence division
• Operand prescaling
• Redundant number system
• Svoboda-Tung method

Cite this

New Svoboda-Tung division. / Montalvo, Luis A.; Parhi, Keshab K; Guyot, Alain.

In: IEEE Transactions on Computers, Vol. 47, No. 9, 01.12.1998, p. 1014-1020.

Research output: Contribution to journalArticle

Montalvo, LA, Parhi, KK & Guyot, A 1998, 'New Svoboda-Tung division', IEEE Transactions on Computers, vol. 47, no. 9, pp. 1014-1020. https://doi.org/10.1109/12.713319
Montalvo, Luis A. ; Parhi, Keshab K ; Guyot, Alain. / New Svoboda-Tung division. In: IEEE Transactions on Computers. 1998 ; Vol. 47, No. 9. pp. 1014-1020.
@article{894aff290c684c90998ca5971f749a19,
title = "New Svoboda-Tung division",
abstract = "This paper presents a general theory for developing new Svoboda-Tung (or simply NST) division algorithms not suffering the drawbacks of the {"}classical{"} Svoboda-Tung (or simply ST) method. NST avoids the drawbacks of ST by proper receding of the two most significant digits of the residual before selecting the most significant digit of this receded residual as the quotient-digit. NST relies on the divisor being in the range [1, 1 + •), where • is a positive fraction depending upon: 1) the radix, 2) the signed-digit set used to represent the residual, and 3) the receding conditions of the two most significant digits of the residual. If the operands belong to the IEEE-Std range [1, 2), they have to be conveniently prescaled. In that case, NST produces the correct quotient but the final residual is scaled by the same factor as the operands, therefore, NST is not useful in applications where the unsealed residual is necessary. An analysis of NST shows that previously published algorithms can be derived from the general theory proposed in this paper. Moreover, NST reveals a spectrum of new possibilities for the design of alternative division units. For a given radix-b, the number of different algorithms of this kind is b 2 /4.",
keywords = "Computer arithmetic, Digit-recurrence division, Operand prescaling, Redundant number system, Svoboda-Tung method",
author = "Montalvo, {Luis A.} and Parhi, {Keshab K} and Alain Guyot",
year = "1998",
month = "12",
day = "1",
doi = "10.1109/12.713319",
language = "English (US)",
volume = "47",
pages = "1014--1020",
journal = "IEEE Transactions on Computers",
issn = "0018-9340",
publisher = "IEEE Computer Society",
number = "9",

}

TY - JOUR

T1 - New Svoboda-Tung division

AU - Montalvo, Luis A.

AU - Parhi, Keshab K

AU - Guyot, Alain

PY - 1998/12/1

Y1 - 1998/12/1

N2 - This paper presents a general theory for developing new Svoboda-Tung (or simply NST) division algorithms not suffering the drawbacks of the "classical" Svoboda-Tung (or simply ST) method. NST avoids the drawbacks of ST by proper receding of the two most significant digits of the residual before selecting the most significant digit of this receded residual as the quotient-digit. NST relies on the divisor being in the range [1, 1 + •), where • is a positive fraction depending upon: 1) the radix, 2) the signed-digit set used to represent the residual, and 3) the receding conditions of the two most significant digits of the residual. If the operands belong to the IEEE-Std range [1, 2), they have to be conveniently prescaled. In that case, NST produces the correct quotient but the final residual is scaled by the same factor as the operands, therefore, NST is not useful in applications where the unsealed residual is necessary. An analysis of NST shows that previously published algorithms can be derived from the general theory proposed in this paper. Moreover, NST reveals a spectrum of new possibilities for the design of alternative division units. For a given radix-b, the number of different algorithms of this kind is b 2 /4.

AB - This paper presents a general theory for developing new Svoboda-Tung (or simply NST) division algorithms not suffering the drawbacks of the "classical" Svoboda-Tung (or simply ST) method. NST avoids the drawbacks of ST by proper receding of the two most significant digits of the residual before selecting the most significant digit of this receded residual as the quotient-digit. NST relies on the divisor being in the range [1, 1 + •), where • is a positive fraction depending upon: 1) the radix, 2) the signed-digit set used to represent the residual, and 3) the receding conditions of the two most significant digits of the residual. If the operands belong to the IEEE-Std range [1, 2), they have to be conveniently prescaled. In that case, NST produces the correct quotient but the final residual is scaled by the same factor as the operands, therefore, NST is not useful in applications where the unsealed residual is necessary. An analysis of NST shows that previously published algorithms can be derived from the general theory proposed in this paper. Moreover, NST reveals a spectrum of new possibilities for the design of alternative division units. For a given radix-b, the number of different algorithms of this kind is b 2 /4.

KW - Computer arithmetic

KW - Digit-recurrence division

KW - Operand prescaling

KW - Redundant number system

KW - Svoboda-Tung method

UR - http://www.scopus.com/inward/record.url?scp=0001673788&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0001673788&partnerID=8YFLogxK

U2 - 10.1109/12.713319

DO - 10.1109/12.713319

M3 - Article

VL - 47

SP - 1014

EP - 1020

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

SN - 0018-9340

IS - 9

ER -