Browse Prior Art Database

Transformed High Radix Division for High Performance Computers

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

Publishing Venue

IBM

Related People

Tan, KG: AUTHOR

Abstract

This article describes the theoretical foundations from which very large radix divisions become practical (generate 4, 6, 8, and more bits of quotient per iteration). The quotient decoder for this method is so simple that only the most significant fraction bit needs to be examined. This fact also greatly simplifies the quotient decoder and hence allows very fast division iterations.

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 40% of the total text.

Page 1 of 4

Transformed High Radix Division for High Performance Computers

This article describes the theoretical foundations from which very large radix divisions become practical (generate 4, 6, 8, and more bits of quotient per iteration). The quotient decoder for this method is so simple that only the most significant fraction bit needs to be examined. This fact also greatly simplifies the quotient decoder and hence allows very fast division iterations.

In high performance computers, where fast computation speed is emphasized, substantial amounts of hardware are provided for high speed multiplication. A new division algorithm, called transformed high-radix (TR) division, is described. This new algorithm will utilize the high speed multiplication hardware to achieve high speed division. The TR division is based on high-radix division methods, whose theories and implementations have been well documented in the literature (1,2,3,4). The quotients generated are completely compatible with conventional division methods.

High-Radix Division Fundamentals: The basic division iteration is described by the following equation: p(i+1) = rp(i) - q(i+1) . d where P(i) = the partial remainder of the ith iteration. p(o) = the dividend.

d = the division.

r = the radix.

q(i+1)= 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 divided by 2 (r-1) greater than or equal to n greater than or equal to r-1 defines the redundancy constant k=n divided by (r-1) then 1 divided by 2 greater than or equal to k greater than or equal to 1 Rewrite (1) as rp(i) = p(i+1) + q(i+1) . d
It also required that Absolute p(i)

Absolute less than k . d For a given q(i+1), (rp(i)) max and (rp(i)) min are determined as (rp(i)) max = (k + q(u+1)) . d (rp(i)) max = ( - k + q(i1)) . d

Equation (2) can be plotted as a function of d, with q(i+1) 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 for r = 4 and r = 8 is shown in Figs. 1A and 1B, respectively.

The P-D plot will completely specify the division iteration steps. A given divisor d and the shifted partial remainder rp(i) will specify a point in a q(j) area. The value j will be the value of the new quotient digit q(i+1). In this representation, the redundancy is indicated by the overlapping regions Q(j) between adjacent q(j) and q(j-1) areas, in which either q(i+1) = j or q(i+1) = j-1 can be the correct choice for the quotient (j range is from I to n).

1

Page 2 of 4

Some General Properties of the Overlapping Regions. The overlapping regions Q(j) play an important part in the quotient selection procedures. Some of their general properties are derived in this section. See Fig. 2. 1. The area of each overlapped region Q(j) is developed as (See Original)

Equation (5) states that all areas of Q(j) are identical and that thei...