Hacker News Reader

Comment by stephencanon | Hacker News Reader

It’s worth noting that for fixed-precision math libraries, we usually want the best approximation in the (possibly weighted) L-inf sense, which doesn’t generally have a closed-form solution, so we use iterative methods to generate approximations instead.

View on HN

Seems also worth noting that although the usual algorithm for finding the minimax polynomial is the very old Remez algorithm, I'm playing with a minimax finder that relies on what I think is a novel algorithm. My algorithm seems better than Remez, and certainly beats it (as in, finds the solution when Remez can not) in many cases, even though I don't have an analysis of the algorithm.

The main idea is to use linear programming with some chosen points from the interval to look for the polynomial that approximates the chosen function over that interval. Unlike Remez, this enables control over which individual points from the interval are chosen as representatives, which enables avoiding ill-behaved points. An example of where this leads to improvements over Remez is when optimizing relative error: Remez would trip over zeros of the function, because they cause singularities in the relative error, however my algorithm works (by avoiding ill-behaved points) as long as the discontinuities are removable.

My algorithm is also a lot more flexible than Remez', for example it allows optimizing over multiple intervals instead of a single one.

The Git repo of the (still in-progress) project is here: https://gitlab.com/nsajko/FindMinimaxPolynomial.jl

The Julia package is already registered (installable from the official Julia registry): https://juliahub.com/ui/Packages/FindMinimaxPolynomial/kNIo8...

This is really cool and I think it might be a re-discovery of https://dl.acm.org/doi/abs/10.1145/3434310.

Yeah, some ideas are the same. Some notes:

1. Their LP constraint matrix is just a Vandermonde matrix according to the linked paper, while my code formulates the LP problem in a smarter way that should make the job much easier for the LP solver. I guess this improvement would be easy to adopt on their end.

2. The linked paper focuses on tiny types like BFloat16, but they mention scalability with large data types as a future goal. My focus was on larger types like IEEE-754 binary64 (double in C) from the start.

3. They account for range reduction and output compensation! This seems really nice, I hope that whatever they did can be applied to my approach to improve it.

I’d like to add to this that iterative solutions are wonderful, and often better than closed-form solutions in a lot of ways. Of course you know that already :-)

What's a good textbook intro to these methods?

I wrote this intro for a friend and since then more people have found it useful:

https://xn--2-umb.com/22/approximation

If you want a proper textbook, I recommend L.N. Trefethen (2019). “Approximation Theory and Approximation Practice.” Which is available online here:

https://epubs.siam.org/doi/book/10.1137/1.9781611975949

That's a really nice overview of Remez, thanks for sharing!

I think this is the first time I've seen a punycode URL in the wild. I love it!

Reply on news.ycombinator.com