Apparatus and method for calculation of divisions and square roots
AssigneeSamsung Electronics Co., Ltd.
InventorDong-Gyu Lee
Life of this patent
Estimating the term…
Abstract
Non-restoring radix-2 division and square rooting procedures are provided. The proposed procedures utilize a quotient/root digit set {−1, 0, +1} and a quotient/root prediction table (QRT/RPT). The i'th quotient/root digit is determined with reference to a partial remainder from (i−2)'th iterative operation and by the quotient/root prediction table. The present procedures generate the (i−1)'th correction term, which is to be applied in calculating the i'th partial remainder, simultaneously with the (i−2)'th correction term, and need not to perform an iterative operation to obtain the i'th partial remainder.
Claims10
An apparatus generating a quotient by dividing a dividend with a divisor, the apparatus comprising:
- a first correction term generator for creating a first correction term;
- a second correction term generator for creating a second correction term;
- a first subtractor for deducting the first correction term from a left-shifted value of an (i−2)'th partial remainder;
- a second subtractor for deducting the second correction term from the left-shifted value of the (i−2)'th partial remainder;
- a carry propagation detector for determining whether there is a borrow while calculating an (i−1)'th partial remainder;
- quotient digit prediction means for predicting an i'th quotient digit in response to an (i−1)'th quotient digit, the (i−2)'th partial remainder, and an output of the carry propagation detector;
- and
- selection means for selecting an alternative one of outputs of the first and second subtractors as an i'th partial remainder in response to the i'th quotient digit.
An apparatus generating a quotient (q) by dividing a dividend (x) with a divisor (d), the apparatus comprising:
- an iterative division circuit for operating a partial remainder involved in x(i)=4x(i−2)−(2q−(i−1)+q−i)*d, where x(i) is an i'th partial remainder, x(i−2) is an (i−2)'th partial remainder, q−(i−1) is an (i−1)'th quotient digit, x(0)=x, and q−i∈ {−1, 0, +1};
- a quotient digit selector for selecting the (i−1)'th quotient digit from the (i−2)'th partial remainder;
- a carry propagation detector for checking a presence of a borrow while calculating an (i−1)'th partial remainder;
- and
- a quotient digit prediction block for predicting an i'th quotient digit in response to the (i−1)'th quotient digit, the (i−2)'th partial remainder, and an output of the carry propagation detector.
A method of providing a quotient (q) by dividing a dividend (x) with a divisor (d), using an iterative operation for a partial remainder represented by x(i)=4x(i−2)−(2q−(i−1)+q−i)*d, where x(i) is an i'th partial remainder, x(i−2) is an (i−2)'th partial remainder, q−(i−1) is an (i−1)'th quotient digit, x(0)=x, and q−i∈ {−1, 0, +1}, the method comprising the steps of;
- using a quotient digit selecting circuit for selecting the (i−1)'th quotient digit q−(i−1) from the (i−2)'th partial remainder x(i−2);
- using a carry propagation detecting circuit for detecting a presence of a borrow while calculating an (i−1)'th partial remainder;
- using a quotient digit predicting circuit for predicting an i'th quotient digit with reference to the (i−1)'th quotient digit, the (i−2)'th partial remainder, and the a presence of the borrow, without calculating the (i−1)'th partial remainder, and calculating the i'th partial remainder by means of the i'th quotient digit;
- and
- repeating the former steps to calculate the quotient (q).
Dependencies are inferred from the claim text.