Method and apparatus for division employing table-lookup and functional iteration

Claim 2

A data processing system storing a dividend N and a divisor D which are operated upon to form a quotient Q, where Q includes n quotient bytes Q(0), Q(1),..., Q(i), Q(i+1),..., Q(n-1), said system comprising, a first unit for concurrently adding and multiplying operands, a second unit for adding, for one''s complementing and for two''s complementing operands, a shifter unit for shifting operands, a plurality of registers for storing operands, including said dividend N and said divisor D, control means for controlling the processing of operands, a table-lookup unit for storing a plurality of first approximate reciprocal divisors; means, responsive to said control means for gating high-order bits of said divisor D from said registers to said table-lookup unit to gate a corresponding one, (Dt) 1, of said first approximate reciprocal divisors into said registers; means, responsive to said control means, for gating the approximate recIprocal divisor (Dt) 1 and the divisor D from said registers to said first unit to form the product D(Dt) 1 which equals (1-(dt)) where (dt) is an initial multiplier, means, responsive to said control means, connecting said first unit to said registers for storing (1-(dt)) in said registers; means, responsive to said control means, for gating (1-(dt)) from said registers to said second unit for two''s complementing (1-(dt)) to form (1+(dt)), means, responsive to said control means, connecting said second unit to said registers for storing (1+(dt)) in said registers; means, responsive to said control means, for gating (1+(dt)) and the approximate reciprocal divisor (Dt) 1 from said registers to said first unit to form the product (1+(dt))(Dt) 1 which equals a second approximate reciprocal divisor (Dp)116 1; means, responsive to said control means, connecting said first unit to said registers for storing (Dp) 1 in said registers.

Claim 3

The apparatus of claim 1 including, means, responsive to said control means, for gating the approximate reciprocal divisor (Dp) 1 and the divisor D from said registers to said first unit to form the product D(Dp) 1 which equals (1-(dp)) where (dp) is an iterative multiplier; means, responsive to said control means, connecting said first unit to said registers for storing (1-(dp)) in said registers, means, responsive to said control means, for gating (1-(dp)) from said registers to said second unit to form the one''s complement of (1-(dp)) equal to the iterative multiplier (dp); and means, responsive to said control means, connecting said second unit to said registers for storing the iterative multiplier (dp) in said registers.

Claim 4

The system of claim 2 in which No is a given dividend stored in said registers and Do is a given divisor stored in said registers, said system including, means, responsive to said control means, connecting said registers to said shifting unit for binary normalizing said divisor Do by shifting y bits to truncate all high-order 0''s thereby forming said divisor D, means, responsive to said control means, connecting said shifter unit to said registers for storing said divisor D in said registers, means, responsive, to said control means, for gating said dividend No to said shifter unit for shifting the dividend No y bits thereby forming said dividend N, means, responsive to said control means, connecting said shifter unit to said registers for storing said dividend N in said registers.

Claim 5

The apparatus of claim 2 including, means, responsive to said control means, for gating (Dp) 1 and N to said first unit for multiplying (Dp) 1 by N to form Q(0), r(0), where r(0) is the 0th truncated remainder of the truncated remainders r(i), means, responsive to said control means, connecting said first unit to said registers for storing Q(0), r(0) in said registers, means, responsive to said control means, for gating (dp), Q(0) and r(0) to said first unit for multiplying (dp) by Q(0) and adding the product to r(0) to form the term Q(1), r(1) where r(1) is the 1st truncated remainder of the truncated remainders r(i), means, responsive to said control means, connecting said first unit to Said register means for storing Q(1), r(1) in said registers, means, responsive to said control means, for iteratively gating (dp), Q(i), and r(i) from said registers to said first unit for iteratively multiplying (dp) by Q(i) and adding the product to r(i) to form Q(i+1), r(i+1) for all values of i from 1 to (n-1), means, responsive to said control means, connecting to said first unit to said registers for iteratively storing Q(i+1), r(i+1) in said registers for all values of i from 1 to (n-1).

Claim 6

A data processing system storing a dividend N and a divisor D which are operated upon to form a quotient Q where Q includes n non-overlapping quotient bytes Q(0), Q(1),...,Q(i), Q(i+1), ...,Q(n-1), where each byte includes x binary bits, said system comprising, a first unit for concurrently adding and multiplying operands, a second unit for adding, for one''s complementing and for two''s complementing operands, a shifter unit for shifting operands, a plurality of registers for storing operands, including said dividend N and said divisor D, control means for controlling the processing of operands, a table-lookup unit for storing a plurality of first approximate reciprocal divisors of the form (Dt) 1 where (Dt) does not differ from D by more than 2 (x/2), means, responsive to said control means, for gating high-order bits of said divisor D from said registers to address said table-lookup unit to access a corresponding one, (Dt)c 1, of said first approxiamte reciprocal divisors, means, responsive to said control means, connecting said table-lookup unit to said registers for storing said reciprocal divisor (Dt)c 1 in said registers, means, responsive to said control means, for gating said reciprocal divisor (Dt)c 1 and the divisor D from said registers to said first unit to form the product D(Dt) 1 which equals (1-(dt)) where (dt) is an initial multiplier, means, responsive to said control means, connecting said first unit to said registers for storing (1-(dt)) in said registers; means, responsive to said control means, for gating (1-(dt)) from said registers to said second unit for two''s complementing (1-(dt)) to form (1+(dt)), means, responsive to said control means, connecting said second unit to said registers for storing (1+(dt)) in said registers; means, responsive to said control means, for gating (1+(dt)) and the approximate reciprocal divisor (Dt) 1 from said registers to said first unit to form the product (1+ (dt)) (Dt) 1 which equals a second approximate reciprocal divisor (Dp) 1 where (Dp) does not differ from D by more than 2 x, means, responsive to said control means, connecting said first unit to said registers for storing (Dp) 1 in said registers.

Claim 7

A data processing system storing a dividend N and a divisor D which are operated upon to form a quotient Q where Q includes n non-overlapping quotient bytes Q(0), Q(1),...,Q(i), Q(i+1), ...,Q(n-1), where each byte includes x binary bits, said system comprising, a first unit for concurrently adding and multiplying operands, a second unit for adding, for one''s complementing and for two''s complementing operands, a shifter unit for shifting operands, a plurality of registers for storing operands, including said dividend N and said divisor D, control means for controlling the processing of operands, a table-lookup unit for storing a plurality of first approximate reciprocal divisors of the form (Dt) 1 where (Dt) does not differ from D by more than 2 (x/2), means, responsive to said control means, for gating high-order bits of said divisor D from said registers to address said table-lookup unit to access a corresponding one, (Dt)c 1, of said first approxiamte reciprocal divisors, means, responsive to said control means, connecting said table-lookup unit to said registers for storing said reciprocal divisor (Dt)c 1 in said registers, means, responsive to said control means, for gating said reciprocal divisor (Dt)c 1 and the divisor D from said registers to said first unit to form the product D(Dt) 1 which equals (1-(dt)) where (dt) is an initial multiplier, means, responsive to said control means, connecting said first unit to said registers for storing (1-(dt)) in said registers; means, responsive to said control means, for gating (1-(dt)) from said registers to said second unit for two''s complementing (1-(dt)) to form (1+(dt)), means, responsive to said control means, connecting said second unit to said registers for storing (1+(dt)) in said registers; means, responsive to said control means, for gating (1+(dt)) and the approximate reciprocal divisor (Dt) 1 from said registers to said first unit to form the product (1+ (dt)) (Dt) 1 which equals a second approximate reciprocal divisor (Dp) 1 where (Dp) does not differ from D by more than 2 x, means, responsive to said control means, connecting said first unit to said registers for storing (Dp) 1 in said registers.

Claim 10

The method of claim 6 including the steps, gating (Dp) 1 and D to said first unit, multiplying (Dp) 1 and D in said first unit to form (1-(dp)), storing (1-(dp)) in said register means, gating (1-(dp)) from said registers to said second unit, one''s complementing (1-(dp)) in said first unit to form (dp) where (dp) is an iterative multiplier, storing (dp) in said registers, gating (Dp) 1 and N to said first unit, multiplying (Dp) 1 and N in said first unit to form Q(0), r(0) where r(0) is a 0th truncated remainder of the truncated remainder r(i), storing Q(0), r(0) in said registers, gating Q(0), (dp), and r(0) to said first unit, multiplying Q(0) and (dp) and adding r(0) to the product in said first unit to form Q(1), r(1), storing Q(1), r(1) in said registers, iteratively gating (dp), Q(i), and r(i ) from said registers to said first unit for all values of i from 1 to (n-1), iteratively multiplying (dp) by Q(i) in said first unit to form the product (dp)Q(i) and adding said product (dp)Q(i) to r(i) in said first unit to form Q(i+1), r(i+1) for all values of i from 1 to (n-1), iteratively storing Q(i+1), r(i+1) in said registers for all values of i from 1 to (n-1).