Automatically improving accuracy for floating point expressions
- 3 June 2015
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 50 (6), 1-11
- https://doi.org/10.1145/2813885.2737959
Abstract
Scientific and engineering applications depend on floating point arithmetic to approximate real arithmetic. This approximation introduces rounding error, which can accumulate to produce unacceptable results. While the numerical methods literature provides techniques to mitigate rounding error, applying these techniques requires manually rearranging expressions and understanding the finer details of floating point arithmetic. We introduce Herbie, a tool which automatically discovers the rewrites experts perform to improve accuracy. Herbie's heuristic search estimates and localizes rounding error using sampled points (rather than static error analysis), applies a database of rules to generate improvements, takes series expansions, and combines improvements for different input regions. We evaluated Herbie on examples from a classic numerical methods textbook, and found that Herbie was able to improve accuracy on each example, some by up to 60 bits, while imposing a median performance overhead of 40%. Colleagues in machine learning have used Herbie to significantly improve the results of a clustering algorithm, and a mathematical library has accepted two patches generated using Herbie.Keywords
Funding Information
- National Science Foundation (DGE-1256082)
This publication has 18 references indexed in Scilit:
- Practically Accurate Floating-Point MathComputing in Science & Engineering, 2014
- Wave Equation Numerical Resolution: A Comprehensive Mechanized Proof of a C ProgramJournal of Automated Reasoning, 2012
- A dynamic program analysis to find floating-point accuracy problemsPublished by Association for Computing Machinery (ACM) ,2012
- Certification of bounds on expressions involving rounded operatorsACM Transactions on Mathematical Software, 2010
- The pitfalls of verifying floating-point computationsACM Transactions on Programming Languages and Systems, 2008
- MPFRACM Transactions on Mathematical Software, 2007
- Replication with Attention to Numerical AccuracyPolitical Analysis, 2003
- The Numerical Reliability of Econometric SoftwareJournal of Economic Literature, 1999
- What every computer scientist should know about floating-point arithmeticACM Computing Surveys, 1991
- A Greedy Heuristic for the Set-Covering ProblemMathematics of Operations Research, 1979