A fast segmentation algorithm for piecewise polynomial numeric function generators

摘要

We give an efficient algorithm for partitioning the domain of a numeric function f into segments. The function f is realized as a polynomial in each segment, and a lookup table stores the coefficients of the polynomial. Such an algorithm is an essential part of the design of lookup table methods Ercepovac et al. (2000) [5], Lee et al. (2003) [7], Nagayama et al. (2007) [12], Paul et al. (2007) [6] and Sasao et al. (2004) [8] for realizing numeric functions, such as sin(πx), ln(x), and −ln(x). Our algorithm requires many fewer steps than a previous algorithm given in Frenzen et al. (2010) [10] and makes tractable the design of numeric function generators based on table lookup for high-accuracy applications. We show that an estimate of segment width based on local derivatives greatly reduces the search needed to determine the exact segment width. We apply the new algorithm to a suite of 15 numeric functions and show that the estimates are sufficiently accurate to produce a minimum or near-minimum number of computational steps.