Novel polynomial approximation methods for generating correctly rounded elementary functions
Description
TitleNovel polynomial approximation methods for generating correctly rounded elementary functions
Date Created2021
Other Date2021-10 (degree)
Extent1 online resource (xvii, 225 pages) : illustrations
DescriptionAll endeavors in science use math libraries to approximate elementary functions (e.g., ln(x) or e^x). Unfortunately, mainstream math libraries for floating point (FP) representations do not produce correctly rounded results for all inputs. In addition, given the importance of FP performance in numerous domains, several new variants of FP and its alternatives have been proposed (e.g., bfloat16, tensorfloat32, posits). These representations do not have correctly rounded math libraries. This dissertation proposes the RLibm approach, a collection of novel techniques for generating polynomial approximations that produce correctly rounded results of an elementary function f(x).
Existing approaches use polynomial approximations that approximate the real value of f(x). The minimax approach generates polynomials that minimize the maximum approximation error compared to the real value of f(x) across all inputs. However, minimax polynomials produce wrong results due to approximation errors and rounding errors in the implementation. In contrast, the RLibm approach makes a case for generating polynomials that approximate the correctly rounded result of f(x) (i.e., the exact value of f(x) computed in reals and rounded to the target representations). This approach provides more freedom in generating efficient polynomials that produce correctly rounded results for all inputs.
Additionally, this dissertation makes the following contributions. First, we show that the problem of generating polynomials that produce correctly rounded results can be structured as a linear programming problem. Second, the RLibm approach accounts for numerical errors that occur from range reduction by automatically adjusting the amount of freedom available to generate polynomials. The generated polynomial with RLibm produces the correctly rounded results for all inputs. Third, we propose a set of techniques to develop correctly rounded elementary functions for 32-bit types. Specifically, we generate efficient piecewise polynomials using counterexample guided polynomial generation and bit-pattern based domain splitting. Finally, we extend the RLibm approach to generate a single polynomial approximation that produces the correctly rounded results for multiple rounding modes and multiple precision configurations. To generate correctly rounded elementary functions for n-bit type, our key idea is to generate a polynomial approximation for a (n+2)-bit representation using the round-to-odd mode. We provide formal proof that the resulting polynomial will produce the correctly rounded results for all standard rounding modes and for multiple representations with k bits where k <= n.
Using the RLibm approach, we have developed several implementations of elementary functions for various representations and rounding modes. These elementary functions produce the correctly rounded results for all inputs in the target representations. Additionally, the functions are faster than mainstream math libraries which have been optimized for decades. Our RLibm-All prototype, a collection of elementary functions that produce the correctly rounded results for multiple floating point representations with all standard rounding modes, has 1.1x, 1.3x, and 1.9x speedup over glibc, Intel, and CR-LIBM math libraries, respectively. Our prototypes also provide the first correctly rounded elementary functions for 32-bit posit.
NotePh.D.
NoteIncludes bibliographical references
Genretheses
LanguageEnglish
CollectionSchool of Graduate Studies Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.
Statistical Profile