Dismiss
The Prior Art Database and Publishing service will be updated on Sunday, February 25th, from 1-3pm ET. You may experience brief service interruptions during that time.
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

IBM

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.

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...