Efficient hardware divide operation
US7599982B1 · kind B1 · utility
Assignee
Inventor
Key dates
| Filing date | Sep 8, 2005 |
| Grant date | Oct 6, 2009 |
| Priority date | — |
| Expiry date | Nov 1, 2027 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F2207/5356
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
One embodiment of the present invention provides a system that uses the Newton-Raphson technique to perform a division operation. During operation, the system receives a numerator a and a denominator b. The system then divides a by b by first using the Newton-Raphson technique to calculate 1/b, and then multiplying 1/b by a to produce the result a/b. While using Newton-Raphson technique to find 1/b, the system first obtains an initial estimate x0 for 1/b and then iteratively solves the equation xi+1=xi(2−bxi). Each iteration involves: (1) using a multiplier circuit to multiply b by xi to compute bxi; (2) performing a bit-wise complement operation on bxi to compute 2−bxi, whereby an additional pass through an adder circuit or a multiply/add circuit is not required to perform the subtraction operation. (3) The system then uses the multiplier circuit to multiply xi by 2−bxi to compute xi(2−bxi).
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.