2021/11/24 by Mridul Aanjaneya, Aanjaneya, Mridul, Jay P. Lim +3
Computer Science · #FOS: Computer and information sciences #Mathematical Software (cs.MS) #Numerical Methods and Algorithms #Parallel Computing and Optimization Techniques #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.2111.12852
openalex publication_date 2021/11/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper presents a novel method for generating a single polynomial\napproximation that produces correctly rounded results for all inputs of an\nelementary function for multiple representations. The generated polynomial\napproximation has the nice property that the first few lower degree terms\nproduce correctly rounded results for specific representations of smaller\nbitwidths, which we call progressive performance. To generate such progressive\npolynomial approximations, we approximate the correctly rounded result and\nformulate the computation of correctly rounded polynomial approximations as a\nlinear program similar to our prior work on the RLibm project. To enable the\nuse of resulting polynomial approximations in mainstream libraries, we want to\navoid piecewise polynomials with large lookup tables. We observe that the\nproblem of computing polynomial approximations for elementary functions is a\nlinear programming problem in low dimensions, i.e., with a small number of\nunknowns. We design a fast randomized algorithm for computing polynomial\napproximations with progressive performance. Our method produces correct and\nfast polynomials that require a small amount of storage. A few polynomial\napproximations from our prototype have already been incorporated into LLVM's\nmath library.\n