6 ms·

The Taylor expansion locally fits a polynom based on the n first derivatives. If you want to find the "best" nth-degree polynom to approximate the sine function

• stephencanon 3y ago
  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.
  • bigdict 3y ago
    What's a good textbook intro to these methods?
    • remcob 3y ago
      I wrote this intro for a friend and since then more people have found it useful: https://2π.com/22/approximation 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 https://epubs.siam.org/doi/book/10.1137/1.9781611975949
      • stephencanon 3y ago
        That's a really nice overview of Remez, thanks for sharing!
      • munificent 3y ago
        I think this is the first time I've seen a punycode URL in the wild. I love it!
  • nsajko 3y ago
    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 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/ https://juliahub.com/ui/Packages/FindMinimaxPolynomial/kNIo8...
    • adgjlsfhk1 3y ago
      This is really cool and I think it might be a re-discovery of https://dl.acm.org/doi/abs/10.1145/3434310 https://dl.acm.org/doi/abs/10.1145/3434310.
      • nsajko 3y ago
        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.
  • klodolph 3y ago
    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 :-)