Browse Prior Art Database

High-Speed Decimal Division

IP.com Disclosure Number: IPCOM000049468D
Original Publication Date: 1982-Jun-01
Included in the Prior Art Database: 2005-Feb-09
Document File: 4 page(s) / 72K

Publishing Venue

IBM

Related People

Tan, KG: AUTHOR

Abstract

The division method set forth is derived from the principles of high-radix division. However, the quotient decoder is extremely complicated in high-radix division schemes. This invention utilizes only a portion of the P-D plot such that the quotient is generated iteratively and hence the quotient decoder is greatly simplified and easy to design.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 47% of the total text.

Page 1 of 4

High-Speed Decimal Division

The division method set forth is derived from the principles of high-radix division. However, the quotient decoder is extremely complicated in high-radix division schemes. This invention utilizes only a portion of the P-D plot such that the quotient is generated iteratively and hence the quotient decoder is greatly simplified and easy to design.

The theories and implementations of high-radix division have been well explored for binary arithmetic (1,2,3,4) and have been implemented in a number of computers, such as Illiac 4. However, high-radix division methods have not been applied to decimal operations. The following examines the implementation schemes of high-radix division in decimal operations. High-Radix Division Fundamentals

The basic division iteration is described by the following equation:

P(i+l) = rp(i) - q(i+l) . d where p(i) equals the partial remainder of the ith iteration, p(o) equals the dividend,

d equals the division,

r equals the radix,

q(i+l) equals the quotient generated for (i+l) iteration.

The quotient q(i) is allowed to take a range of integer values (-n, ..., -1, 0, 1, ..., n). It has been shown in (1,4) that 1/2 (r - 1) less than n less than r - 1 defines the redundancy constant k=n divided by R- 1 Then, 1/2 less than k less than 1

The choice of k is an important design parameter which has major impact on actual implementation.

Rewrite (1) as rp(i)=p(i+l) + q(i+l) . d (2)

It is also required that (see original).

For a given q(i+l), (rp(i)) max and (rp(i)) min are determined as (rp(i)) max=(k + q)i+l)) . d

(rp(i)) min=(- k + q(i+l)) . d

Equation (2) can be plotted as a function of d, with q(i+l) taking on values from -n to n in increments of one. This graphical representation of division iteration is referred to as the P-D plot. The P-D plot of decimal arithmetic (r=10) for n 6, K=2/3 is shown in Fig. 1.

In this figure, q(i) denotes the region of (rp, d) for which the quotient of value
(i) can be selected. The overlapped areas between successive q(i) regions provide a degree of freedom in selecting the quotient. Each overlapped area must be partitioned into a subarea with quotient (i) and a subarea with quotient (i- 1), as indicated by the dotted lines in Fig. 2. The area of (fp,d) pairs which select quotient (i) is called Q(i)' P-D Plot Implementation for Decimal Division

1

Page 2 of 4

As can be seen from Fig. 2, the quotient decode consists of the implementations of a pair of staircase lines bounded for each Q(i). Because of the high number of steps in each staircase line, implementation of all Q(i) is very complicated. Fig. 2 also demonstrates the fact that the implementations of the P- D plot for decimal operations (where (1/10 less than d less than 1) are much more difficult than the implementations of the P-D plot for normalized binary operations (1/2 less than d less than 1). P-D Plot Implementation

The standard high-radix decimal division method required the direct full i...