近似值从双精度到单精度的转换

生成多项式极小值近似的常用方法是使用俄罗斯数学家叶夫根尼·雷梅兹 （Evgeny Remez） 于 1934 年发表的 Remez 交换算法。这是一个数值过程，通常涉及条件不佳的方程组。因此，它通常是在任意精度库的帮助下实现的。例如，在我使用的 Remez 算法的实现中，我将库配置为 1024 位精度。

对于表现相当良好的函数，Remez 算法的各种变体可以找到非常接近数学最小值多项式的近似值。正如问题中所指出的，问题在于，当将生成的多项式系数移动到有限精度浮点计算时会发生什么。人们经常发现近似值的最小值特性受损，有时甚至严重受损。有两个错误来源在起作用。首先，生成的系数不能用有限精度浮点格式准确表示。其次，多项式的计算使用有限精度运算，而不是具有无限精度的数学运算。

The first problem is the easier one to address. As one can see from some quick experiments, simply rounding the coefficients to the finite-precision format doesn't accomplish the desired near minimax result. By using a finite-precision format, we basically transform from an N-dimensional continuous space to an N-dimensional discrete lattice, and to do this properly, we need to find the closest lattice points. This is a solvable but hard problem, which is usually made easier through the use of heuristics. Relevant literature:

N. Brisebarre, J.-M. Muller, and A. Tisserand, "Computing machine-efficient polynomial approximations". ACM Transactions on Mathematical Software, Vol. 32. No. 2, June 2006, pp. 236-256. (online)

Nicolas Brisebarre and Sylvain Chevillard, "Efficient polynomial L^∞-approximations", In 18th IEEE Symposium on Computer Arithmetic, June 2007, pp. 169-176 (online)

Florent de Dinechin and Christoph Lauter, "Optimizing polynomials for floating-point implementation", ArXiv preprint 2008 (online)

The Sollya tool uses these techniques from the literature for its command. Worth checking out in addition to Maple's and Mathematica's facilities for generating minimax polynomial approximations, as it often results in superior approximations in my experience.fpminimax

The second problem, how to account for evaluation with finite-precision floating-point computation and how to adjust the coefficients of a polynomial approximation accordingly, are still subject to research. Some initial results:

Tor Myklebust, "Computing accurate Horner form approximations to special functions in finite precision arithmetic", ArXiv manuscript 2015 (online)

Denis Arzelier, Florent Bréhard, Mioara Joldes, "Exchange algorithm for evaluation and approximation error-optimized polynomials", In 26th IEEE Symposium on Computer Arithmetic, June 2019, pp. 30-37 (online)

Note that the first publication came about due to a question I asked on Stackoverflow.

For my own use I am using a heuristic search for finding approximations optimized to account for both representational error in the coefficients and evaluation error in the polynomial evaluation. it can be loosely described as a form of simulated annealing. I have also checked into the use of genetic programming, but the preliminary results did not look promising, so I stopped pursuing this approach.