Reconsider `(1+x/2^k)^(2^k)` as the default lowering for `math.exp`
- Dominant language
- MLIR
- Stars
- 906
- Forks
- 171
- Avg merge
- 4d 12h
- Merged PRs (30d)
- 32
Description
Following up on #2935, closed by #3213 with the note that it was open to thoughts on
whether there should be an explicit trade-off between the two methods. I think there
should be, and I disagree with the premise the current guard encodes.
### Why CF is hard to beat here
`exp` is entire, and for analytic functions CF is not merely "near-best" in the
O(log n) Chebyshev-interpolant sense — it is indistinguishable from the true minimax
polynomial in floating point. Trefethen (*ATAP*, ch. 20) makes the point with e^x on
[-1,1] specifically: at n=2 the CF and minimax errors agree to 9 significant digits,
and "for n > 3, the CF and best polynomials are indistinguishable in floating point
arithmetic."
So on the default domain the general-purpose solver is already delivering a pretty good
polynomial of that degree for practical purposes.
### Numbers on the default domain [-1,1]
| lowering | mult depth | ct x ct mults | max abs err | max rel err | rms err |
|---|---|---|---|---|---|
| `(1+x/128)^128` (current default) | 7 | 7 | 1.05e-2 | 3.92e-3 | 2.93e-3 |
| CF degree 3 | 2 | 2 | 5.53e-3 | 1.50e-2 | 3.88e-3 |
| CF degree 5 (previous default) | 3 | 4 | 4.52e-5 | 1.23e-4 | 3.19e-5 |
Against the previous default the Taylor form loses every column at once: more depth, more
multiplications, and about two orders of magnitude more error on all three measures.
Against CF degree 3 it is closer and it does win on relative and rms error — its error is
essentially a relative one by construction, so it nearly vanishes near the origin instead
of being spread evenly — but it pays 7 levels and 7 multiplications for that, against 2
and 2. Script to regenerate the whole table straight from `heir-opt`:
https://gist.github.com/z0cal/46e5162b029b8642b96df5db3ea306d7
### Where the Taylor form does shine
It is not a bad method, and its advantage is structural. Its error is on the order of
`e^x · x²/2^(k+1)`, whose maximum over an interval never falls on the lower endpoint, so
extending the domain downwards is free. CF has no such property: the degree it needs
grows without bound as the interval widens. A crossover therefore always exists — on a
wide enough domain the Taylor form wins on depth, and on operation count well before
that. It is also non-negative and monotone by construction, which a minimax approximant is
not: equioscillation forces the error down to `-E`, so the approximant goes negative
wherever `e^x` falls below that level. On [-1,1] that stays theoretical — `min e^x` is
0.368, far above the degree-5 error, and every row above is positive — but on a domain
wide enough for `e^x` to approach `E` it is real, and it matters when the result feeds a
softmax denominator followed by an approximate reciprocal.
The method earns its place on wide domains. It is just not the right default on [-1,1].
### The guard
I think the problem is the guard. Since this touches HEIR's design, I don't think it is
my place to code the solution, but I would recommend revisiting the current pattern
priority.
Contributor guide
Research direction
Start by reading the context in #2935 and #3213, then inspect the current pattern-priority guard for math.exp. Use the linked heir-opt script to reproduce the approximation table and define the revised trade-off and default behavior before implementation.
Written by the indexing model from the issue text.
Assessment
- Domain
- compilers
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100