High-speed evaluation of polynomials
Assignee3Com Corporation
InventorsPhilip A. DesJardins, Ravi G. Mantri
Life of this patent
Estimating the term…
Abstract
A method and device for evaluating polynomial equations with a logic computer. To evaluate the polynomial equation more efficiently using a computer with latent memory accesses, the polynomial is split into a plurality of sub-polynomials. The sub-polynomials can be simultaneously evaluated using Horner's rule. The results of the sub-polynomial evaluations are summed to obtain the evaluation of the polynomial equation. A device and method are described.
Claims22
A device for evaluating a polynomial equation comprising:
- a splitter for splitting the polynomial into a plurality of sub-polynomial equations;
- a plurality of accumulators for evaluating the sub-polynomial equations of the polynomial equation;
- a plurality of adders in communication with the corresponding plurality of accumulators, wherein the adders add to the sub-polynomial equations in the plurality of accumulators;
- a plurality of multipliers in communication with the corresponding plurality of accumulators and the corresponding plurality of adders;
- control logic to control the adders and multipliers to carry out Horner's rule on the sub-polynomials;
- a plurality of final multipliers in communication with the corresponding plurality of accumulators for multiplying accumulator values;
- and
- a summer in communication with the plurality of final multipliers for summing final multiplier values to yield a result of the polynomial evaluation.
A computer readable medium having stored therein instructions for causing a processing unit to execute a method of evaluating a polynomial equation comprising the steps of:
- splitting a polynomial equation into a plurality of sub-polynomial equations;
- evaluating the sub-polynomial equations by accessing the multiplication table stored in memory, wherein a number of the plurality of sub-polynomial equations are evaluated simultaneously;
- and
- summing the results of the step of evaluating sub-polynomials to obtain the evaluation of the polynomial.
A computer-readable medium having stored therein instructions for causing a processing unit to execute a method of evaluating a polynomial equation comprising the steps of:
- storing coefficients of the polynomial into memory locations;
- separating the coefficients into a plurality of sub-polynomials;
- evaluating the plurality of sub-polynomials using a multiplication lookup table stored in memory;
- and
- summing the result of the sub-polynomials evaluation to obtain the result of the polynomial evaluation.
A device for evaluating a polynomial equation comprising:
- a splitter for splitting a polynomial equation into a plurality of sub-polynomial equations;
- a multiplier for simultaneously evaluating the sub-polynomial equations;
- and
- a summer for summing the evaluation results of the sub-polynomial equations to obtain the evaluation of the polynomial.
Dependencies are inferred from the claim text.