Progressive Polynomial Approximations for Fast Correctly Rounded Math Libraries
summary
Paper presents a Clarkson‑inspired, fast randomized LP solver that samples and reweights constraints to solve low‑dimensional linear programs with billions of inequalities, proves expected O(k log n) iterations when full rank, and generates progressive polynomials that share lower‑order terms so 10–16–32‑bit formats evaluate cheaper. Implementation produces a libm prototype that is correctly rounded for 10–32 bit formats and all rounding modes, is adopted into LLVM for five functions, shows 49–123% speedups and up to 150× memory reduction on some functions.
AI-written summary · about
chapters (13)
- 0:00Start
- 0:23Why should we care about Math libraries?
- 0:40The RLIBM Project
- 2:49What Is This Paper About
- 5:19What is a Correctly Rounded Result?
- 8:16Progressive Polynomials for Efficiency
- 9:06Randomized LP Solver (inspired by [Clarkson '95])
- 10:37Technical Details of the Randomized Algorithm
- 10:57Prototypes And Experimental Evaluation
- 11:31RLIBM-PROG Functions are Correctly Rounded
- 12:18RLIBM-PROG Functions are More Efficient
- 13:48Transition to Practice
- 14:03Conclusion
related talks
26mGenerating Correctly Rounded Math Libraries for New Floating Point Variants
22mOne Polynomial Approximation to Produce Correctly Rounded Results of an Elementa
22mCorrectly Rounded Math Libraries without Worrying about the Application’s Rounding Mode
58mFrom Formal Verification to Correctly Rounded Math Libraries
58mPortable floating-point calculations
14mFPL: Fast Presburger Arithmetic through Transprecision
14mFast and Efficient Bit-Level Precision Tuning
14mFast Linear Programming through Transprecision Computing on Small and Sparse Data