US4481600A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus for speeding up digital division in radix-2n machine
Assignee: Individual
•
Filing: 1982-03-26
•
Granted: 1984-11-06
•
Expires: 2002-03-26
Abstract
Abstract A division A/B where A and B are represented in a radix D can be accomplished by evaluating a power series. It is very important not only for the power series to converge but also to converge quickly in practical application. Thus, the convergence rate of the power series must be small in order to obtain a reasonably good approximation of the quotient by evaluating the first few terms. The acceleration method that guarantees to give a small convergence rate, 1/(2D-3 ), of the power series (see the section of the related application) was proposed with at most three successive applications of acceleration constants. This invention reduces the convergence rate, 1/(2D-3), to a smaller convergence rate, 1/(2mD-3), in the worst case where m=1,2,2 2 ,2 3 ,2 4 , . . . and the three successive applications of acceleration constants to at most the two successive applications of the constants. These two reductions promise to yield faster division in digital computer.
Inventors
- 👤 Hitohisa Asai
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 09:06
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/38; G06F7/48; G06F7/52; G06F7/535; G06F2207/00; G06F2207/535; G06F2207/5355
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
360 words
An apparatus for speeding up convergence division computation for producing a quotient by performing successive multiplication operations comprising: divisor register means for receiving and storing a divisor quantity B, dividend/quotient register means for receiving and storing A', wherein the initial A' is a dividend quantity A, pseudoradix register means for receiving and storing a predetermined pseudoradix D n , wherein D is the radix and n is an integer, first means, connected to said pseudoradix register means and said divisor register means, to compute a quantity q o =B-D n , q register means, connected to said first means, to receive and store q i , wherein i=0,1, . . . , logic means, connected to said q register means, to determine acceleration factors a i and j i , acceleration constant ma i +j i , and q r wherein m is an integer chosen from a set {1,2,2 2 2 3 , . . . , D}, and to generate control signals corresponding to each condition (1) ((D-1>a i ) or (D-1=a i and m-1>j i )), (2) (D-1=a i and m-1=j i ), and (3) (D-1<a i ), by table lookup of an ls-subdivision table using q i wherein table entries comprise interval quantities and roots of q r , second means, connected to said pseudoradix register means and said q register means, to compute D n +q i , third means, connected to said logic means, to selectively generate acceleration constant ma i +j i and modified acceleration constant (2ma i +2j i +1)/2, first multiplication means, connected to said second means and to said third means, to compute (ma i +j i )(D n +q i ) and (2ma i +2j i +1)(D n +q i )/2, fourth means, connected to said logic means and said second means, to compute (mD-1)(D n +q i ), first shift means, connected to said first multiplication means, said fourth means, and said logic means, to selectively shift (ma i +j i )(D n +q i ) and (mD-1)(D n +q i ) by m bits, fifth means, connected to said pseudoradix register means, to compute D n+1 ,
Claim 2
Independent Claim
360 words
An apparatus for speeding up convergence division computation for producing a quotient by performing successive multiplication operations comprising: divisor register means for receiving and storing a divisor quantity B, dividend/quotient register means for receiving and storing A', wherein the initial A' is a dividend quantity A, pseudoradix register means for receiving and storing a predetermined pseudoradix D n , wherein D is the radix and n is an integer, first means, connected to said pseudoradix register means and said divisor register means, to compute a quantity q o =B-D n , q register means, connected to said first means, to receive and store q i , wherein i=0,1, . . . , logic means, connected to said q register means, to determine acceleration factors a i and j i , acceleration constant ma i +j i , and q r wherein m is an integer chosen from a set {1,2,2 2 2 3 , . . . , D}, and to generate control signals corresponding to each condition (1) ((D-1>a i ) or (D-1=a i and m-1>j i )), (2) (D-1=a i and m-1=j i ), and (3) (D-1<a i ), by table lookup of an ls-subdivision table using q i wherein table entries comprise interval quantities and roots of q r , second means, connected to said pseudoradix register means and said q register means, to compute D n +q i , third means, connected to said logic means, to selectively generate acceleration constant ma i +j i and modified acceleration constant (2ma i +2j i +1)/2, first multiplication means, connected to said second means and to said third means, to compute (ma i +j i )(D n +q i ) and (2ma i +2j i +1)(D n +q i )/2, fourth means, connected to said logic means and said second means, to compute (mD-1)(D n +q i ), first shift means, connected to said first multiplication means, said fourth means, and said logic means, to selectively shift (ma i +j i )(D n +q i ) and (mD-1)(D n +q i ) by m bits, fifth means, connected to said pseudoradix register means, to compute D n+1 ,
Claim 3
Dependent Claim
204 words
sixth means to combine the outputs of the first shift means and the fifth means, seventh means, responsive to said control signals corresponding to conditions (1) ((D-1>a i ) or (D-1=a i and m-1>j i )) and (2) (D-1=a i and m-1=j i ), for passing 1 and n+1 respectively, second shift means, connected to said sixth means, sand seventh means, and said q register means, for computing q i for i>0, second multiplication means, connected to said dividend/quotient register means and said third means to selectively multiply the acceleration constant and the modified acceleration constant by the output of said dividend/quotient register means, to compute a successive A' by A'(ma i +j i ) and a successive A' by A'(2ma i +2j i +1)/2, eighth means, connected to said dividend/quotient register means and said logic means, to multiply the output of said dividend/quotient register means by (mD-1), to compute a successive A' by A'(mD-1), and third shift means, connected to said second multiplication means, said eighth means, said logic means and said dividend/quotient register means, to selectively shift the outputs of said second multiplication means and said eighth means by m bits and to feed the shifted quantity to said dividend/quotient register means.
Claim 4
Dependent Claim
204 words
sixth means to combine the outputs of the first shift means and the fifth means, seventh means, responsive to said control signals corresponding to conditions (1) ((D-1>a i ) or (D-1=a i and m-1>j i )) and (2) (D-1=a i and m-1=j i ), for passing 1 and n+1 respectively, second shift means, connected to said sixth means, sand seventh means, and said q register means, for computing q i for i>0, second multiplication means, connected to said dividend/quotient register means and said third means to selectively multiply the acceleration constant and the modified acceleration constant by the output of said dividend/quotient register means, to compute a successive A' by A'(ma i +j i ) and a successive A' by A'(2ma i +2j i +1)/2, eighth means, connected to said dividend/quotient register means and said logic means, to multiply the output of said dividend/quotient register means by (mD-1), to compute a successive A' by A'(mD-1), and third shift means, connected to said second multiplication means, said eighth means, said logic means and said dividend/quotient register means, to selectively shift the outputs of said second multiplication means and said eighth means by m bits and to feed the shifted quantity to said dividend/quotient register means.
Claim 5
Dependent Claim
136 words
The apparatus for speeding up convergence division computation set forth in claim 1 including: successive means for recursively determining q i for i>0 through activating selectively and repeatedly the following means: (1) said first means, (2) said logic means, (3) said second means, (4) said third means, (5) said first multiplication means, (6) said first shift means, (7) said fifth means, (8) said sixth means, (9) said seventh means, (10) said second shift means, and (11) said fourth means; and for recursively determining A' through activating selectively and repeatedly the following means: (1) said logic means, (2) said third means, (3) said second multiplication means, (4) said third shift means, and (5) said eighth means until said logic generates a control signal corresponding to a condition, (D-1=a i and m-1=j i ) or (D-1>a i ).
Claim 6
Dependent Claim
68 words
The apparatus for speeding up convergence division computation set forth in claim 1 wherein: said interval quantities comprise register means for storing numerical values determined by (D-1)D n , (2m(D-1)-1)D n /(2m+1), . . . ,(2m(D-a)-2j-1)D n /(2ma+2j+1), . . . , D n /(2mD-1), 0, wherein (2m(D-a)-2j-1)D n /(2ma+2j+1) represents the terms for a=1,2,3, . . . ,D-1 and j=0,1,2, . . . ,m-1 in each a.
Claim 7
Dependent Claim
50 words
The apparatus for speeding up convergence division computation set forth in claim 1 wherein: said roots or q r comprise register means for storing numerical values determined by the relationship q r =(mD-(ma+j))D n /(ma+j) for a=1,2,3, . . . ,D-1 and j=0,1,2, . . . ,m-1 in each a.
Claim 8
Dependent Claim
62 words
The apparatus for speeding up convergence division computation set forth in claim 1 wherein: said first multiplication means includes means (1) for selecting (ma i +j i )(D n +q i ) when q i is greater than q r and (2) for selecting (2ma i +2j i +1)(D n +q i )/2 when q i is less than q r .
Claim 9
Dependent Claim
54 words
The apparatus for speeding up convergence division computation set forth in claim 1 wherein: said second multiplication means includes means (1) for selecting A'(ma i +j i ) when q i is greater than q r and (2) for selecting A'(2ma i +2j i +1)/2 when q i is less than q r .
Claim 10
Dependent Claim
35 words
The apparatus for speeding up convergence division computation set forth in claim 1 wherein: said first shift means includes means for selectively shifting (2ma i +2j i +1)(D n +q i )/2 by m bits.
Claim 11
Dependent Claim
97 words
The apparatus for speeding up convergence division computation set forth in claim 1 wherein: said logic means includes (1) means for comparing q i with said interval quantities, (2) means for recursively determining said acceleration constant ma i +j i by the relationship ma.sub.i+1 +j.sub.i+1 = ((2mD+1)(2ma.sub.i +2j.sub.i -1)+1)/(4ma.sub.i +4j.sub.i) for i≧0 wherein R denotes an integer in the range R-1< R ≦R and R is a real number, and (3) means for selectively choosing a root of q r corresponding to a q i value by using a determined pairvalue (a i , j i ).
References Cited (Backward Citations)
US3234367A
Cited
US3633018A
Cited
US3736413A
Cited
US3777132A
Cited
US3828175A
Cited
US4025773A
Cited
US3917935A
Cited
US4364115A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1987-11-06 | 1988-05-07 | 1988-11-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1991-11-06 | 1992-05-07 | 1992-11-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1995-11-06 | 1996-05-07 | 1996-11-06 | $7700.00 | Window Closed / Lapsed |