Browse Prior Art Database

Hardware Divide Implementation

IP.com Disclosure Number: IPCOM000104198D
Original Publication Date: 1993-Mar-01
Included in the Prior Art Database: 2005-Mar-18
Document File: 2 page(s) / 44K

Publishing Venue

IBM

Related People

Garcia, LC: AUTHOR [+2]

Abstract

Basic Algorithm- Let A,B and Q be the dividend, divisor and Quotient respectively. The quotient Q of A/B can be expressed as follows:

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Hardware Divide Implementation

      Basic Algorithm- Let A,B and Q be the dividend, divisor and
Quotient respectively.  The quotient Q of A/B can be expressed as
follows:

Q  =  A/B               (1)

The Remainder R(i) and Quotient digit Q(i) can be found iteratively
as:
q(i)  = R(i-1)/B        (2)

      R(i)  = R(i-1) - q(i)xB         (3)

Where:  q(i) is the ith digit of quotient Q and,

R(i) is the ith remainder of the ith quotient digit

If a constant K is chosen as an appropriate reciprocal of B, then (2)
and (3) can be rewritten as:
q(i)  = R(i-1)*K               (4)

R(i)  = R(i-1) - R(i-1)*K*B = R(i-1)* (1-KB)    (5)

The following table shows several iterations of q and R determined
from (4) and (5).
i    q(i)                R(i)
___  ________________    _________________

1  q1 = R0*K            R1 = R0*(1-KB) = A(1-KB)
2  q2 = R1*K            R2 = R1*(1-KB) = A(1-KB)**2
3  q3 = R2*K            R3 = R2*(1-KB) = A(1-KB)**3
4  q4 = R3*K            R4 = R3*(1-KB) = A(1-KB)**4
5  q5 = R4*K            R5 = R4*(1-KB) = A(1-KB)**5
i  q(i) = R(i-1)*K      R(i) = R(i-1)*(1-KB) = A(1-KB)**i

Substituting R(i-1) terms into q(i) and SUMMING of q(i) terms yields
the final quotient Q as:

Q = (A+R1+R2+R3+R4+R5+...R(i-1)) K          (6)

Q = (A+A(1-KB)**1 + A(1-KB)**2 + ...  +A(1-KB)**i-1)K   (7)
Where:  R0 = A

Equation (7) shows Q can be found by summations of a sufficient
number of remainders and a final multiplication by K.  Implementation
requires ONE accumulator to sum A + R1 + R2 + R3 + ---- +R(i-1) and
ONE multiplier to form A(1-KB)**n terms and for the final SUM times
K.  The accumulate function is built into the multiplier in the
proposed implementation.  For 56 bit Q precision a starting table of
11 bits and i=6 iterations are required.  Successi...