Evaluating Monotonic Functions using Binary Search
Open Access
- 19 August 2026
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Reconfigurable Technology and Systems
Abstract
This work addresses the accurate (correctly rounded) evaluation of arbitrary functions. The simplest solution is to use a Look-Up Table (LUT), with a storage requirement (hence area) that grows linearly with the output word size, but exponentially with the input word size. This limits its applicability to small input word sizes. For monotonic functions, a binary search in the output domain enables implementations whose area scales linearly with the input word size and exponentially with the output word size. This article introduces several novel architectures exploiting this idea, investigates their efficient mapping to FPGA micro-architecture using features such as \(k\) -input LUT and fast carry logic, compares them to the LUT approach in area and delay, and demonstrates an application to a Gaussian pseudo-random number generator.
Keywords
This publication has 18 references indexed in Scilit:
- Hierarchical Multipartite Function EvaluationIEEE Transactions on Computers, 2016
- A dynamic non-uniform segmentation method for first-order polynomial function evaluationMicroprocessors and Microsystems, 2012
- Floating-point exponential functions for DSP-enabled FPGAs2010
- Elementary Functions Hardware Implementation Using Constrained Piecewise-Polynomial ApproximationsIEEE Transactions on Computers, 2010
- Multipartite table methodsIEEE Transactions on Computers, 2005
- A Few Results on Table-Based MethodsReliable Computing, 1999
- The Symmetric Table Addition Method for Accurate Function ApproximationJournal of Signal Processing Systems, 1999
- Evaluating elementary functions in a numerical coprocessor based on rational approximationsIEEE Transactions on Computers, 1990
- CMOS/SOS frequency synthesizer LSI circuit for spread spectrum communicationsIEEE Journal of Solid-State Circuits, 1984
- A General Hardware-Oriented Method for Evaluation of Functions and Computations in a Digital ComputerIEEE Transactions on Computers, 1977