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.
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