https://doi.org/10.1145/3734692

A Lookup Table (LUT) is a computationally inexpensive piecewise function used to approximate computationally expensive mathematical functions. Evaluating a LUT can be as quick as using Horner’s method to evaluate a polynomial after looking up its coefficients. A common choice of LUT is a piecewise constant or piecewise linear function; however, high-degree interpolating polynomials can also be valuable.
Here, we describe the functionality of FunC 2.0, a C++ library designed to streamline the process of building, comparing, and implementing univariate LUTs in practical applications. In particular, FunC 2.0 can build relatively small LUTs satisfying user-provided absolute and relative tolerances for error. Furthermore, FunC 2.0 can build nonuniform LUTs, it provides utilities to quickly determine reasonable LUT bounds and tolerances for error, and it provides a way to quickly profile a set of LUTs. We demonstrate FunC’s utility in application by reducing the total runtime of a simulation performed by the Canadian Hydrological Model (CHM). This simulation modeled the snow mass distribution across Western Canada over 1 month. Now, the CHM can evaluate the mathematical function of interest about 28 times faster, allowing the necessary algorithm to finish two times faster, and the overall simulation is about 9% faster.

https://doi.org/10.1145/3734692