Fast integer division
AssigneeImagination Technologies Limited
InventorLeonard Rarick
Life of this patent
Estimating the term…
Abstract
Embodiments disclosed pertain to apparatuses, systems, and methods for fast integer division. Disclosed embodiments pertain to an integer divide circuit to divide a dividend by a divisor and produce multiple quotient bits per iteration. In some embodiments, the fast integer divider may include a partial remainder register initialized with the dividend. Further, the fast integer divider circuit may include a plurality of adders, where each adder subtracts a multiple of the divisor from the current value in the partial remainder register. A logic block coupled to each of the adders, determines multiple quotient bits at each iteration based on the subtraction results.
Claims20
An integer divide circuit to divide a dividend by a divisor (D) and produce m quotient bits per iteration, where m≧2, the circuit comprising:
- a partial remainder register, initialized with the dividend, to hold a current partial remainder (R);
- a plurality (2m−1) of adders coupled to the partial remainder register, each adder i to output a corresponding subtraction result R−i*D, where 1≦i≦2m−1;
- and
- a logic block coupled to the plurality of adders, wherein, the logic block determines m quotient bits based, at least in part, on the 2m−1 subtraction results.
A processor comprising an integer divide unit to produce m quotient bits per iteration, where m≧2, and wherein the integer divide unit further comprises:
- a partial remainder register, initialized with a dividend, to hold a current partial remainder (R);
- a plurality (2m−1) of adders coupled to the partial remainder register, each adder i to output a corresponding subtraction result R−i*D, where D is the divisor and 1≦i≦2m−1;
- and
- a logic block coupled to the plurality of adders, wherein, the logic block is configured to determine m quotient bits based, at least in part, on the 2m−1 subtraction results.
A non-transitory computer-readable medium comprising executable instructions to describe an integer divide circuit to divide a dividend by a divisor (D) and produce m quotient bits per iteration, where m≧2, the integer divide circuit comprising:
- a partial remainder register, initialized with the dividend, to hold a current partial remainder (R);
- a plurality (2m−1) of adders coupled to the partial remainder register, each adder i to output a corresponding subtraction result R−i*D, where 1≦i≦2m−1;
- and
- a logic block coupled to the plurality of adders, wherein, the logic block is configured to determine m quotient bits based, at least in part, on the 2m−1 subtraction results.
Dependencies are inferred from the claim text.