Progressive polynomial approximations for fast correctly rounded math libraries
Progressive polynomial approximations for fast correctly rounded math libraries
复制标题
快速正确舍入数学库的渐进多项式近似
DOI：
10.1145/3519939.3523447
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Nagarakatte, Santosh
中科院分区：
文献类型：
--
作者：
Aanjaneya, Mridul;Lim, Jay P.;Nagarakatte, Santosh
本文提出了一种新的方法来产生一个单一的多项式近似，该近似对一个初等函数的多个表示的所有输入产生正确的四舍五入结果。生成的多项式近似值有一个很好的特性，即对于较小的位宽的特定表示，前几个较低次项产生正确的舍入结果，我们称之为渐进性能。为了生成这种渐进的多项式近似，我们近似正确舍入的结果，并将正确舍入的多项式近似的计算表述为类似于我们之前在RLIBM项目上的工作的线性程序。为了在主流库中使用得到的多项式近似，我们希望避免使用大型查找表的分段多项式。我们观察到初等函数的多项式逼近计算问题是一个低维的线性规划问题，即具有少量的未知数。我们设计了一种快速的随机算法来计算多项式近似，并具有递进性能。我们的方法产生正确和快速的多项式，需要少量的存储空间。我们的原型中的一些多项式近似已经被合并到LLVM的数学库中。
This paper presents a novel method for generating a single polynomial approximation that produces correctly rounded results for all inputs of an elementary function for multiple representations. The generated polynomial approximation has the nice property that the first few lower degree terms produce correctly rounded results for specific representations of smaller bitwidths, which we call progressive performance. To generate such progressive polynomial approximations, we approximate the correctly rounded result and formulate the computation of correctly rounded polynomial approximations as a linear program similar to our prior work on the RLIBM project. To enable the use of resulting polynomial approximations in mainstream libraries, we want to avoid piecewise polynomials with large lookup tables. We observe that the problem of computing polynomial approximations for elementary functions is a linear programming problem in low dimensions, i.e., with a small number of unknowns. We design a fast randomized algorithm for computing polynomial approximations with progressive performance. Our method produces correct and fast polynomials that require a small amount of storage. A few polynomial approximations from our prototype have already been incorporated into LLVM’s math library.