Fast computation of products by dyadic fractions with sign-symmetric rounding errors
AssigneeQUALCOMM Incorporated
InventorYuriy Reznik
Life of this patent
Estimating the term…
Abstract
A product of an integer value and an irrational value may be determined by a sign-symmetric algorithm. A process may determine possible algorithms that minimize metrics such as mean asymmetry, mean error, variance of error, and magnitude of error. Given an integer variable x and rational dyadic constants that approximate the irrational fraction, a series of intermediate values may be produced that are sign-symmetric. The intermediate values may include a sequence of addition, subtraction and right shift operations the when summed together approximate the product of the integer and irrational value. Other operations, such as additions or subtractions of 0s or shifts by 0 bits may be removed.
Claims17
A method of determining an algorithm for calculating two or more products of an integer value x and approximations of two or more irrational values using a processor, the method comprising:
- receiving, by the processor, the integer value x;
- determining, by the processor, a set of dyadic fractions a1/2b . . . am/2b approximating the two or more irrational values;
- determining, by the processor, a sequence of intermediate values w1 . . . wt to calculate the two or more products by:
- setting w1 equal to the integer value x;
- and
- determining w2 . . . wt in accordance with (a) at least one of w1 . . . wt−1, and (b) one of a plus operation, a minus operation, and a right-shift operation;
- determining, by the processor, indices l1 . . . lm ≦t of intermediate values among the sequence of intermediate values w1 . . . wt that correspond to the two or more products, such that:
- wl1≈x*a1/2b . . . wlm≈x*am/2b;
- and
- determining, by the processor, the algorithm by determining the sequence of intermediate values w1 . . . wt and determining the indices l1 . . . lm ≦t of the intermediate values among the sequence of intermediate values w1 . . . wt to minimize an error metric.
A non-transitory computer-readable storage medium comprising executable instructions to perform a method of determining an algorithm for calculating two or more products of an integer value x and approximations of two or more irrational values using a processor, comprising instructions for:
- receiving the integer value x;
- determining a set of dyadic fractions a1/2b . . . am/2b approximating the two or more irrational values;
- determining a sequence of intermediate values w1 . . . wt to calculate the two or more products by:
- setting w1 equal to the integer value x;
- and
- determining w2 . . . wt in accordance with (a) one of w1 . . . wt−1, and (b) one of a plus operation, a minus operation, and a right-shift operation;
- determining indices l1 . . . lm≦t of intermediate values among the sequence of intermediate values w1 . . . wt that correspond to the two or more products, such that:
- wl1≈x*a1/2b . . . wlm26 x*am/2b;
- and
- determining the algorithm by determining the sequence of intermediate values w1 . . . wt and determining the indices l1 . . . lm ≦t of the intermediate values among the sequence of intermediate values w1 . . . wt to minimize an error metric.
An apparatus for determining an algorithm for calculating two or more products of an integer value x and approximations of two or more irrational values, comprising:
- means for receiving the integer value x;
- means for determining a set of dyadic fractions a1/2b . . . am/2b approximating the two or more irrational values;
- means for determining a sequence of intermediate values w1 . . . wt to calculate the two or more products by:
- setting w1 equal to the integer value x;
- and
- determining w2 . . . wt in accordance with (a) one of w1 . . . wt−1, and (b) one of a plus operation, a minus operation, and a right-shift operation;
- means for determining indices l1 . . . lm≦t of intermediate values among the sequence of intermediate values w1 . . . wt that correspond to the two or more products, such that:
- wl1≈x*a1/2b . . . wlm≈x*am/2b;
- and
- means for determining the algorithm by determining the sequence of intermediate values w1 . . . wt and determining the indices l1 . . . lm≦t of the intermediate values among the sequence of intermediate values w1 . . . wt to minimize an error metric.
A method of determining an algorithm for calculating two or more products of an integer value x and approximations of two or more irrational values using a processor, the method comprising:
- receiving, by the processor, the integer value x;
- determining, by the processor, a set of dyadic fractions a1/2b . . . am/2b approximating the two or more irrational values;
- determining, by the processor, a sequence of intermediate values w1 . . . wt to calculate the two or more products;
- determining, by the processor, indices l1 . . . lm≦t of intermediate values among the sequence of intermediate values w1 . . . wt that correspond to the two or more products, such that:
- wl1≈x*a1/2b . . . wlmx*am/2b;
- and
- determining, by the processor, the algorithm by determining the sequence of intermediate values w1 . . . wt and determining the indices l1 . . . lm≦t of the intermediate values among the sequence of intermediate values w1 . . . wt;
- setting, by the processor, w1 equal to the integer value x;
- and
- determining, by the processor, w2 . . . wt in accordance with one of w1 . . . wt−1 and one of a plus operation, a minus operation, and a right-shift operation;
- and
- wherein determining, by the processor, the algorithm by determining the sequence of intermediate values w1 . . . wt and determining the indices l1 . . . lm≦t of the intermediate values among the sequence of intermediate values w1 . . . wt comprises:
- determining, by the processor, the intermediate values among the sequence of intermediate values w1 . . . wt in accordance with one or more of a mean asymmetry metric, a mean error metric, a variance of error metric, and a magnitude of error metric.
Dependencies are inferred from the claim text.