Fast evaluation of many polynomials with small coefficients on the same point
US8903083B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Aug 9, 2011 |
| Grant date | Dec 2, 2014 |
| Priority date | — |
| Expiry date | Aug 19, 2031 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY04S40/20
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
In one exemplary embodiment of the invention, a method for evaluating at point r one or more polynomials p1(x), . . . , pl(x) of maximum degree up to n−1, where the polynomial pi(x) has a degree of ti−1, the method including: partitioning each polynomial pi(x) into a bottom half pibot(x) with bottom terms of lowest si coefficients and a top half pitop(x) with top terms of remaining ti−si coefficients; recursively partitioning the bottom half pibot(x) and the top half pitop(x) of each polynomial pi(x) obtaining further terms having a lower degree than previous terms, performed until at least one condition is met yielding a plurality of partitioned terms; evaluating the bottom half pibot(x) and the top half pitop(x) at the point r for each polynomial pi(x) by evaluating the partitioned terms at the point r and iteratively combining the evaluated partitioned terms; and evaluating each polynomial pi(x) at the point r by setting pi(r)=rspitop(r)+pibot(r).
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.