I have a dream of "safe" numerical programming, where any time you do| pavpanchekha.com
One thing Herbie does is simplify stuff, and one that I am personally interested in is simplifying trigonometric expressions. For example, did you know that sin(x) / (1 + cos(x)) and (1 - sin(x)) / cos(x) are the same? Or that both are equal to tan(x / 2)? But how can we do this automatically? Before I move on, a thank you to ChatGPT, mostly o3 and 4.1, for generative discussions. The Weirstrass Substitution One key to any discussion of trigonometric stuff is the Weirstrass substitution.1 [1 ...| Pavel Panchekha’s Blog
I have recently become a big fan of the condition number formalism for floating-point error; it is a simple mental model that explains a lot about floating point. In this blog post I want to use that mental model to investigate "operator fusion": basically, why library functions like log1p, cospi, or hypot improve error.1 [1 Actually, one of the big effects of hypot is to avoid overflow, which condition numbers don't address, so, uhh, it's only part of the story.] The condition number formali...| Pavel Panchekha’s Blog
Alright, I'm back at it: comparing Herbie against LLMs to see who is best at numerical rewriting. If you're new here, Herbie is a research compiler I've been working on for about a decade that helps compile mathematical expressions to fast and accurate floating-point code. More recently, I've been comparing new OpenAI models against Herbie to see who is the top numerical analyst. So far, Herbie's been winning all of the match-ups… but with O3-mini's release can the LLMs finally dethrone the...| Pavel Panchekha’s Blog
This proposal suggests a radically different way Herbie could work, making use of high-quality oracle-free methods of evaluating error. This new method would make Herbie simpler, faster, and possibly better, while (I hope) maintaining all the things we currently like about Herbie. This new Herbie would use egg/egglog much more heavily than today, and the greedy improvement loop would be gone. Background Herbie currently works by: Take a starting expression or expressions Grow an egraph contai...| Pavel Panchekha’s Blog
First, users should be able to specify a platform and have Herbie load and run using that platform. The platform should affect:| pavpanchekha.com
This post is the third in a series of me trying to work out batches, a new data structure I am testing for Herbie and more generally for programming with recursive data structures. In my first post I laid out a type theory for batches, and in my second post I discussed how we can check that programs that use batches are safe. But I'm still after a "holy grail": how to making programming with batches "normal". Specifically, most programming with batches involves lots of indices, which need to ...| Pavel Panchekha’s Blog
A year and a half ago, I wrote a blog post comparing Herbie to the first ChatGPT (which we now call, I think, GPT 3.5). I chose 11 floating-point repair benchmarks, and fed all of them to Herbie and ChatGPT. Herbie is a tool my students and I develop to do exactly this work, and I wanted to know if AI tools had obsoleted it. The conclusion was that Herbie was still much better, winning 6/11 and tying two others. Moreover, the cases where Herbie lost ChatGPT's response was usually not actually...| Pavel Panchekha’s Blog
Doing normal programming with batches has a common pattern. For| pavpanchekha.com
In research it's common to compare your solution to some simple approach as a baseline, to prove that whatever complex algorithm you've developed is actually worth using. Sometimes, coming up with this baseline is hard. But now we have ChatGPT, so let's plug a hole in my 2015 research paper on floating-point error improvement by comparing my tool, Herbie, with ChatGPT. Methodology I've chosen a representative sample of 12 benchmarks from the Herbie benchmark suite. Iv'e biased it a bit toward...| Pavel Panchekha’s Blog
Last week I had a fun experience using Herbie to actually improve the numerical accuracy of real code. Discovering a Rust problem It all started when Finn (an undergraduate from UW) submitted a PR to FPBench to compile FPBench benchmarks to Rust. Besides being great work and a valuable contribution, he also pointed out that our test framework was failing on his FPBench to Rust compiler "due to precision issues with Rust's implementation" of the asinh and acosh functions. This intrigued me, be...| Pavel Panchekha’s Blog
Earlier today, I merged one of the biggest improvements to Herbie ever. Let me take a moment to celebrate. Why cost-accuracy trade-offs? About a year ago, the Herbie team, lead by Brett and Oliver, published Combining Precision Tuning and Rewriting at ARITH'21. While ostensibly that paper was about incorporating precision tuning into Herbie, in reality it was about slightly more than that—it was about teaching Herbie about program cost, and having Herbie find not just the single most accura...| Pavel Panchekha’s Blog
I've been tackling a lot of old issues in Herbie this summer, and in the process I found out that Herbie's pruning algorithm is incredibly slow. This is the story of how I sped it up, demonstrating both some good optimization tricks and also some nice tooling that we've built in Herbie. The Backstory Pruning is an essential part of Herbie. At a high level, Herbie has three phases: first, it samples a bunch of points it can use to evaluate how accurate a program is; then, it generates a bunch ...| Pavel Panchekha’s Blog
As part of Ian and my work on synthesizing math libraries, I've been thinking about synthesizing range reductions. I think we've found a beautiful and efficient way to do this tricky bit of synthesis using e-graphs. This idea is also related to recent Herbie work on detecting symmetric expressions. What is range reduction The core of modern library function implementation is the Remez algorithm, which approximates a function f over an interval [a, b] with polynomials.1 [1 When certain conditi...| Pavel Panchekha’s Blog
As maintainer of Racket's math library, I sometimes put my numerical methods knowledge to a practical test. For example, a few days ago, I took a look at Racket's quadratic-solutions function, which returns the roots of a quadratic formula. Humorously, I've used the quadratic formula as an example in dozens of talks and in the Herbie paper. Yet it was more complex than I expected! The quadratic formula The quadratic formula returns all roots \(x\) of the equation \(a x^2 + b x + c = 0\). You ...| Pavel Panchekha’s Blog
For NSV 2020, Zach and I were invited to give a keynote talk about numerica accuracy, and we set out to write down some lessons learned from our five years of work on Herbie. One theme of our talk, Toward Numerical Assistants, was on user trust: how we can help users trust Herbie. A recent interaction on the Herbie mailing list underscored this issue. The Problem About a month ago, Steve Hoelzer wrote in with a fun Herbie bug. You can see the bug for yourself, but in short Herbie is proposing...| Pavel Panchekha’s Blog
FPTaylor is a big advance in sound floating-point error estimation;1 [1 Alexey Solovyev, the primary author of FPTaylor, notes that the inspiration for FPTaylor came from earlier projects like Rosa and Daisy, and the Taylor series technique itself goes back further.] but it is little-known even in the field. I've been working with error Taylor series recently and think they're the bees knees, so I want them to be more broadly understood. Error at a point Suppose you have a floating-point expr...| Pavel Panchekha’s Blog
Implementing a mathematical function like sin or exp is tricky! Yet if you want to trade off accuracy and input range, for speed or vectorization, you'll need to do that, and likely once for each architecture you need an implementation for. In the process, you'll need to decide on range reduction strategies, working precisions, polynomial orders, and function-specific tricks. So my student Ian Briggs and I are working to make it easier. I don't want to get deep into the weeds here, so I'm jus...| Pavel Panchekha’s Blog
As I work on Herbie, my numerical analysis assistant, I'm always thinking about how I could teach it classic numerical analysis tricks. Recently, my student Oliver Flatt and I have been thinking about tricks for symmetric expressions. Symmetry for Accuracy Consider the following computation, which is important in statistics: \[ \log(e^a + e^b) \] The numerical analysis wisdom is that this expression is best evaluated via the expression max(a, b) + log1p(exp(min(a, b) - max(a, b))) There's a l...| Pavel Panchekha’s Blog
Over the last semester of 2019, Oliver Flatt rewrote Herbie's simplifier—its most important and most expensive component—to use Max Willsey's Egg library. There were quite some difficulties involved, but this change speeds up Herbie by 2.8× and opens up opportunities for further improvements in the future. E-graphs Herbie's simplification component takes an algebraic expression and simplifies it. The main intended benefit is to remove algebraic cancellations, which would otherwise introd...| Pavel Panchekha’s Blog
As part of my usual quality assurance routine, I did a crawl through the latest Herbie reports, looking for timeouts, long runtimes, and sampling errors. In summary, Herbie is now really fast! I found only a few benchmarks that run for more than 20s, with even quite large benchmarks running fast. What makes Herbie slow? Taking a look at a few timelines, it seems like Herbie now spends most of its time, especially for the slower benchmarks, in series expansion and pruning. That said, it seems ...| Pavel Panchekha’s Blog
One of the most rewarding non-research tasks I've done in grad school is to maintain Herbie, a tool for automatically improving the accuracy of floating-point programs. I published Herbie at PLDI’15, which means that Herbie was largely done (as a research project) in 2014. But in the five years since, Herbie has had several major changes that have significantly improved it. Making Herbie more maintainable Since I maintain Herbie in my free time (I have other research projects), making Herbi...| Pavel Panchekha’s Blog
I had a blast attending RacketCon 2018. Besides some great talks (check out Nadeem Abdul Hamid's talk on Sinbad), I also learned about a lot of neat stuff going on in the Racket world (for example, I discovered both the macro and feature profilers). One particularly enjoyable bit was attempting to port a part of Herbie to Typed Racket, under Sam Tobin-Hochstadt's supervision. Typed Racket is Racket plus sound gradual typing. This means that all functions get types, and those types are checked...| Pavel Panchekha’s Blog
I recently had an interesting conversation with Xin Yi, of NUDT, about accurately evaluating the polynomial \(P(x) = 5x^2 - 3\) near its root \(x = \sqrt{3/5}\). He wanted to know: what's the most accurate way to evaluate this polynomial, and why doesn't Herbie find it? Error in evaluating polynomials Evaluating a polynomial P(x) at one of its roots is bound to be inaccurate. If you pick a floating point input x, think of it as representing a range (x-ε, x+ε). and very close to a zero, P(x-...| Pavel Panchekha’s Blog
A conversation with Jeffrey Sarnoff on the Herbie mailing list raised a very interesting small example of how floating-point error can occur. This example is extreme, but I thought it would be interesting to work through. The program is this: sqrt(x^2). Non-compositional error Run it through Herbie and Herbie will tell you that this expression is fairly inaccurate: approximately 29.1 bits of error, with the problems occurring for very large and very small inputs.1 [1 Herbie suggests the more ...| Pavel Panchekha’s Blog
Some of my friends at the University of Washington have been working with computational geometry and running into quite a few headaches because of floating-point error. Of course, they were expecting my work on Herbie to have taught me how to help, so I've been fielding a few floating-point questions. When they got desperate enough to start using MPFR and talking about computable reals, I had an idea. My friends are working on a programming language for describing shapes in two and three dime...| Pavel Panchekha’s Blog
Cassius, my tool for formal reasoning about web page layout, can be used in a lot of ways. You can use it to lay out web pages, much like a browser; you can use it to find bugs like overlapping text; you can use it to debug web pages; or you can use it to synthesize CSS files from examples. For each of these uses, Cassius provides a convenient command-line tool. Since most of these tools use the same back-end, these command-line tools share many options and flags. The old way: multiple files ...| Pavel Panchekha’s Blog
Over winter break, I decided to dig into my notes and try to sketch out the history of the Herbie project. Besides a fun exploration of our git history, I was hoping to crystallize some of the lessons I learned from the project. Besides being my first successful research project in general, I think Herbie taught me a few particular lessons: Tackle ambitious problems I don't work well alone Good benchmarks guide research Generating reports from search processes is great for debugging You never...| Pavel Panchekha’s Blog