Skip to main content

Square-rich fixed point polynomial evaluation on FPGAs

Xu, Simin and Fahmy, Suhaib A. and McLoughlin, Ian V. (2014) Square-rich fixed point polynomial evaluation on FPGAs. In: Proceedings of the 2014 ACM/SIGDA international symposium on Field-programmable gate arrays. FPGD International Symposium on Field Programmable Gate Arrays . ACM, New York, USA, pp. 99-108. ISBN 978-1-4503-2671-1. (doi:10.1145/2554688.2554779) (KAR id:48925)

PDF Author's Accepted Manuscript
Language: English
Download (380kB) Preview
[thumbnail of fpga2014-xu.pdf]
This file may not be suitable for users of assistive technology.
Request an accessible format
Official URL


Polynomial evaluation is important across a wide range of application domains, so significant 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 computation. 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 efficient polynomial evaluation algorithm, which reforms the evaluation process to include an increased number of squaring steps. By using a squarer design that is more efficient 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.

Item Type: Book section
DOI/Identification number: 10.1145/2554688.2554779
Additional information: Unmapped bibliographic data: Y1 - 2014/02// [EPrints field already has value set] L1 - file:///Users/ivm/Library/Application Support/Mendeley Desktop/Downloaded/Xu, Fahmy, McLoughlin - 2014 - Square-rich fixed point polynomial evaluation on FPGAs.pdf [Field not mapped to EPrints]
Uncontrolled keywords: field programmable gate arrays, fixed point, polynomial evaluation
Subjects: T Technology
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Ian McLoughlin
Date Deposited: 25 Aug 2015 09:38 UTC
Last Modified: 16 Feb 2021 13:25 UTC
Resource URI: (The current URI for this page, for reference purposes)
McLoughlin, Ian V.:
  • Depositors only (login required):


Downloads per month over past year