# RETROSPECTIVE: Table-based polynomials for fast hardware function evaluation

Florent de Dinechin

<figure><img src="image_1.png" /></figure>

## ► To cite this version:

Florent de Dinechin. RETROSPECTIVE: Table-based polynomials for fast hardware function evaluation. ASAP 2025 - 36th IEEE International Conference on Application-specific Systems, Architectures and Processors, Jul 2025, Vancouver (British Columbia), Canada. hal-05139896

HAL Id: hal-05139896

https://inria.hal.science/hal-05139896v1

Submitted on 2 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# RETROSPECTIVE:
## Table-based polynomials
### for fast hardware function evaluation

Florent de Dinechin

INSA Lyon - Inria, CITI (UR3720), 69621 Villeurbanne, France

florent.de-dinechin@insa-lyon.fr

0000-0003-4927-3301

*Abstract*—The Higher Order Table-Based Method (HOTBM) was published [1] during Jérémie Detrey's PhD. It was at the time one of the most advanced generic methods for fixed-point hardware function evaluation. This article reviews its legacy, some of the subsequent progress in this field, and the challenges that remain.

*Keywords*—Elementary function, hardware arithmetic.

## I. HARDWARE FUNCTION EVALUATION

In this paper, a fixed-point function evaluator is the hardware implementation of a mathematical function of one real variable $f(x)$. As Fig. 1 shows, it inputs a fixed-point number $X$ in some format on $w_{in}$ bits, and outputs a value $F(X)$ on $w_{out}$ bits, where the function $F$ is an approximation to $f$. Some techniques for building such components are function-specific, for instance CORDIC for trigonometric functions (many other examples can be found in dedicated textbooks [2, 3]). Here we only deal with generic techniques, i. e. techniques that work for a very large class of functions [4, part III].

<figure><img src="image_3.png" /><figcaption>Fig. 1: A fixed-point function approximator</figcaption></figure>

For instance, HOTBM was developed to address the needs of floating-point elementary functions. The standard technique here is always to reduce the floating-point function to a fixed-point one. This reduction is application-specific [2], and for exp, log, sin and cos, Jérémie eventually needed to evaluate:

$$f_{\text{exp}}(x) = e^x - x - 1 \text{ on } [0, 2^{-k}) \text{ for some } k;$$

$$f_{\text{log}}(x) = \frac{\log(x)}{x-1} \text{ on } [0.75, 1.5);$$

$$f_{\text{sin}}(x) = \frac{\pi}{4} - \frac{\sin(\frac{\pi}{4}x)}{x} \quad \text{and} \quad f_{\text{cos}}(x) = 1 - \cos(\frac{\pi}{4}x) \text{ on } [0, 1).$$

Beyond floating-point, his work on the Logarithm Number System (LNS) involved $f_{\oplus}(x) = \log_2(1 + 2^x)$ and $f_{\ominus}(x) = \log_2(1 - 2^x)$. This set of 6 functions was enough to invest in generic methods that work on any $f(x)$.

This work was partially supported by the PEPR IA HOLIGRAIL project of the Agence Nationale de la Recherche, ANR-23-PEIA-0010.

<figure><img src="image_4.png" /><figcaption>Fig. 2: A generator of function approximators</figcaption></figure>

and any input interval (Fig. 2). Another motivation for contemporary developments [5] was the need of inverse cumulative distribution functions in non-uniform random number generators.

## II. FROM AN INTERNAL TOOL TO AN OPEN ONE

We had already converged at the time to the idea that any good approximator should be accurate to its last bit. This is easy to formalize mathematically [4, chapter 3], makes for a simple rule of the game when comparing implementation, and even simplifies the interface to the tool: in Fig 2, the precision of the output format also specifies the operator accuracy.

Less clear was the specification of the input interval. For instance $f_{\text{exp}}$ and $f_{\text{log}}$ in the list above have very different intervals. Tools developed before HOTBM attempted to input the bounds of both input and output intervals, and whether these bounds were open or not. The match with fixed-point was an issue: fixed-point intervals (see Fig. 3) can be viewed either as open on the right, or closed but with a precision-dependent bound. This interface question may seem trivial, but it actually made it very difficult to compare different publications on the same function. Consider for instance a useful benchmark, the reciprocal of a floating-point mantissa: $f_{\text{recip}}(x) = \frac{1}{x}$ on $[1, 2)$. Its output domain is $(0.5, 1]$: note that it is closed in 1, and therefore is a poor match to

<figure><img src="image_5.png" /><figcaption>Fig. 3: Two 8-bit fixed-point formats: left, unsigned numbers in $[0, 1)$, actually $[0, 1 - 2^{-8}]$; right, signed numbers in $[-1, 1)$, actually $[-1, 1 - 2^{-7}]$</figcaption></figure>
a fixed-point format. Note also that the bit of weight 0.5 is constant in the output. Now if an article reports results for $f_{\text{recip}}$ with 16-bit inputs and outputs, does it count this constant bit? And the (little used) output bit of weight 1? In the input bits, does it count the constant bit of weight 1?

The proper solution to these problems [4, Ch.16] is to standardize the interface (Fig 2) on one of the canonical fixed-point intervals, $[0,1)$ or $[-1,1)$. For instance the reciprocal could become $f(x) = \frac{1}{x+1} - 0.5$ on $[0,1)$. The problem of coercing the function to a canonical interval is delegated to the outside, which is where it belongs since the choice of the best coercion is context-specific. Later, we realized that this choice not only simplifies the interface, it also clarifies the numerical implications of further interval decomposition [4, Ch.18]. HOTBM was the experiment that showed that this approach is the one that works best in practice.

More generally, HOTBM was very influential in the early design of the FloPoCo arithmetic core generator<fnref n="1" /> (in some other cases, as a demonstration of how things should not be done).

### III. PROGRESS BEYOND HOTBM

Due to lack of space, we will not try to describe the HOTBM method in details. Here is a summary whose purpose is only to use keywords relevant in the sequel:

HOTBM is a piecewise polynomial approximation technique with uniform segmentation of the input interval. The hardware evaluates a polynomial in developed form (i.e. as a sum of monomials). Monomials are evaluated by ad-hoc units inputting ad-hoc subsets of the bits of X, with tabulation replacing computations whenever possible. The exploration of the parameter space is heuristic.

Here are a few notable improvements to the highlighted terms since then.

Non-uniform segmentation proved useful for some functions [5]. This work also studied arbitrary compositions of segmentation techniques, and concluded that two layers are enough in practice.

Better methods for approximating a function by a polynomial with low-precision coefficients were designed and implemented in the open-source Sollya tool [6]. They were applied to approximators which scale to 64 bits and more [7] using Horner form evaluation.

HOTBM is one among many operators involving a sum of many fixed-point terms. This motivated a framework for application-specific compressor trees [8], which in turn triggered more research on the construction of optimal compression trees [9].

For low precisions (below 24 bits), the optimal values of the architectural parameters of a piecewise polynomial evaluator can be determined by mathematical programming (Integer Linear Programming or SAT) [10]. For

low precisions, this approach enables correctly rounded architectures, one bit more accurate than HOTBM and its predecessors and successors [7].

Finally, all these methods involve tables, and table compression is still an active research subject [11, 12]. Interestingly, all the generic methods could actually be considered as compression techniques, applied to a table of values of $f(X)$.

### IV. WHERE SHOULD WE GO FROM HERE

The ultimate generator of application-specific function approximators, combining all the advances listed above, remains to be written. Is it possible to define the architecture optimization as a mathematical programming problem which

* considers uniform and non-uniform segmentation;

* determines the polynomial coefficient values;

* considers various polynomial evaluation schemes (developed form, Horner, and in between);

* uses HOTBM-like decompositions of the bits of X;

* integrates the latest table compression techniques;

* integrates compression tree generation;

* and takes into account the target technology?

This is an interesting project for the coming years.

### REFERENCES

[1] J. Detrey and F. de Dinechin. "Table-based polynomials for fast hardware function evaluation". In: *International Conference on Application-Specific Systems, Architectures and Processors (ASAP)*. IEEE, 2005, pp. 328-333.

[2] J.-M. Muller. *Elementary Functions, Algorithms and Implementation*. 3rd ed. Birkhäuser Boston, 2016.

[3] A. Omondi. *Computer-Hardware Evaluation of Mathematical Functions*. Imperial College Press, 2016.

[4] F. de Dinechin and M. Kumm. *Application-Specific Arithmetic*. Springer, 2024.

[5] D.-U. Lee, P. Cheung, W. Luk, and J. Villasenor. "Hierarchical Segmentation Schemes for Function Evaluation". In: *IEEE Transactions on VLSI Systems* 17.1 (2009).

[6] S. Chevillard, M. Joldeş, and C. Lauter. "Sollya: An Environment for the Development of Numerical Codes". In: *Mathematical Software - ICMS 2010*. Vol. 6327. LNCS. Springer, 2010, pp. 28-31.

[7] F. de Dinechin, M. Joldeş, and B. Pasca. "Automatic generation of polynomial-based hardware architectures for function evaluation". In: *Application-specific Systems, Architectures and Processors*. IEEE, 2010.

[8] N. Brunie et al. "Arithmetic Core Generation Using Bit Heaps". In: *Field Programmable Logic and Application (FPL)*. IEEE, 2013, pp. 1-8.

[9] M. Kumm and J. Kappauf. "Advanced Compressor Tree Synthesis for FPGAs". In: *IEEE Transactions on Computers* 67.8 (2018), pp. 1078-1091.

[10] D. De Caro et al. "Minimizing Coefficients Wordlength for Piecewise-Polynomial Hardware Function Evaluation With Exact or Faithful Rounding". In: *IEEE Transactions on Circuits and Systems I: Regular Papers* 64.5 (2017), pp. 1187-1200.

[11] S.-F. Hsiao, P.-H. Wu, C.-S. Wen, and P. K. Meher. "Table Size Reduction Methods for Faithfully Rounded Lookup-Table-Based Multiplierless Function Evaluation". In: *Transactions on Circuits and Systems II* 62.5 (2015), pp. 466-470.

[12] A. Khataei and K. Bazargan. "CompressedLUT: An Open Source Tool for Lossless Compression of Lookup Tables for Function Evaluation and Beyond". In: *International Symposium on Field Programmable Gate Arrays (FPGA)*. ACM, 2024.

<footnote n="1">¹The HOTBM code is still available from www.flopoco.org.</footnote>