Square-rich fixed point polynomial evaluation on FPGAs

Simin Xu, Suhaib A. Fahmy, Ian V. McLoughlin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations


Polynomial evaluation is important across a wide range of application domains, so signicant work has been done on accelerating its computation. The conventional algorithm, referred to as Horner's rule, involves the least number of steps but can lead to increased latency due to serial com-putation. Parallel evaluation algorithms such as Estrin's method have shorter latency than Horner's rule, but achieve this at the expense of large hardware overhead. This paper presents an effcient polynomial evaluation algorithm, which reforms the evaluation process to include an increased num-ber of squaring steps. By using a squarer design that is more effcient than general multiplication, this can result in polynomial evaluation with a 57.9% latency reduction over Horner's rule and 14.6% over Estrin's method, while consuming less area than Horner's rule, when implemented on a Xilinx Virtex 6 FPGA. When applied in fixed point function evaluation, where precision requirements limit the rounding of operands, it still achieves a 52.4% performance gain compared to Horner's rule with only a 4% area overhead in evaluating 5th degree polynomials.
Original languageEnglish (US)
Title of host publicationACM/SIGDA International Symposium on Field Programmable Gate Arrays - FPGA
PublisherAssociation for Computing Machinery
Number of pages10
ISBN (Print)9781450326711
StatePublished - Jan 1 2014
Externally publishedYes


Dive into the research topics of 'Square-rich fixed point polynomial evaluation on FPGAs'. Together they form a unique fingerprint.

Cite this