Finding the "truncated" polynomial that is closest to a function

Nicolas Brisebarre, Jean-Michel MullerarXiv 2003 · arXiv

Abstract

In computer arithmetic, implementing mathematical functions requires approximating them with polynomials whose coefficients are restricted to finite-precision formats. Standard methods like the Remez algorithm produce ideal real-valued coefficients, but simply rounding these to the nearest representable values often results in suboptimal performance. This paper introduces a rigorous method to identify the absolute best "truncated" polynomial by treating the search as a geometric problem of finding integer points within a multi-dimensional polytope.

Introduction

When implementing mathematical functions such as $\cos(x)$, $\sin(x)$, or $e^x$ in hardware or software, developers typically rely on polynomial approximations. The goal is to minimize the approximation error over a target interval. The gold standard for this task is the minimax approximation, which minimizes the maximum absolute error. Traditionally, the Remez algorithm is used to find these "perfect" coefficients.

However, a significant gap exists between theory and implementation. The Remez algorithm generates coefficients with infinite precision. In practice, these must be "truncated" to fit into specific bit-widths, such as IEEE-754 floating-point formats or custom fixed-point hardware. The common heuristic of rounding the ideal coefficients to the nearest representable values frequently misses the true optimal polynomial within the restricted coefficient space.

Problem Statement

The core challenge addressed in this research is finding the "best truncated approximation." Given a function $f$ and an interval $[a, b]$, we seek a polynomial $p(x) = \sum a_i x^i$ where each $a_i$ is a representable number (e.g., a multiple of $2^{-k_i}$), such that the maximum error $\|f - p\|_\infty$ is minimized. Because the space of representable coefficients is discrete, this is a combinatorial optimization problem rather than a continuous one.

Methodology

The authors propose a general method that combines classical approximation theory with modern polyhedral geometry.

1. Chebyshev Foundations

The method leverages the properties of Chebyshev polynomials. These polynomials are renowned in approximation theory for having the "smallest norm" (minimum maximum oscillation) on a given interval. They serve as the basis for understanding how error is distributed across the approximation range.

Figure 1: A Chebyshev polynomial exhibiting the equioscillation property, which is central to minimax approximation theory.

2. Coefficient Bounding and Polytope Formulation

A key contribution of the paper is the establishment of rigorous upper and lower bounds for each coefficient of the desired polynomial. By defining these bounds, the search space is constrained to a polytope—a high-dimensional convex shape defined by linear inequalities. The problem then becomes finding the "best" integer points (representing scaled coefficients) within this polytope.

3. Refinement and Scanning

To make the search computationally feasible, the authors employ several optimization techniques:

  • Simplex Refinement: The initial search space is narrowed using the Simplex method and additional constraints derived from the function's values at specific points.
  • Polyhedral Scanning: Specialized libraries, such as Polylib and CLooG, are used to efficiently iterate through the integer points within the defined polytope.
  • Exhaustive Search: Once the candidate pool is sufficiently pruned, an exhaustive search identifies the polynomial with the absolute minimum error.

Results and Discussion

The effectiveness of the method was demonstrated through evaluations on standard elementary functions.

Accuracy Gains in Hardware

In a test case involving a degree-3 polynomial approximation for the cosine function on the interval $[0, \pi/4]$, the proposed method identified a polynomial significantly more accurate than the one produced by simple rounding. The result was a gain of approximately 1.5 bits of accuracy. In the context of precision-sensitive hardware design, a 1.5-bit improvement is a substantial leap that can reduce overall system error or allow for smaller hardware footprints.

Computational Efficiency

For the exponential function on a small interval, the initial search space contained over 18 million potential polynomials. By applying the polytope refinement techniques, the authors pruned this set down to just 76,032 candidates. While the current implementation in Maple took approximately 15 hours to complete the search, the authors note that a C-based implementation using the same polyhedral libraries would be significantly faster, potentially reducing the time to minutes.

Conclusion

This paper demonstrates that rounding is often a "trap" in numerical implementation. By directly searching the space of representable coefficients using geometric methods, it is possible to find approximations that are demonstrably superior to those derived from rounded minimax polynomials. This approach allows for non-uniform truncation—where different coefficients have different precisions—providing hardware and software designers with a powerful tool for optimizing mathematical libraries. Future work involves integrating these algorithms into automated toolchains for compiler and hardware generation.

Summary updated

Abstract

When implementing regular enough functions (e.g., elementary or special functions) on a computing system, we frequently use polynomial approximations. In most cases, the polynomial that best approximates (for a given distance and in a given interval) a function has coefficients that are not exactly representable with a finite number of bits. And yet, the polynomial approximations that are actually implemented do have coefficients that are represented with a finite - and sometimes small - number of bits: this is due to the finiteness of the floating-point representations (for software implementations), and to the need to have small, hence fast and/or inexpensive, multipliers (for hardware implementations). We then have to consider polynomial approximations for which the degree-$i$ coefficient has at most $m_i$ fractional bits (in other words, it is a rational number with denominator $2^{m_i}$). We provide a general method for finding the best polynomial approximation under this constraint. Then, we suggest refinements than can be used to accelerate our method.
BibTeX
@misc{brisebarre2003finding,
  author = {Nicolas Brisebarre and Jean-Michel Muller},
  title = {{Finding the "truncated" polynomial that is closest to a function}},
  year = {2003},
  eprint = {cs/0307009},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/cs/0307009},
}
Figure