4 ms·

And, should have used Chebyshev polynomials. Or if you look at libc, you'll find coefficients for a hand picked optimized polynomial that minimizes error evenly

And, should have used Chebyshev polynomials. Or if you look at libc, you'll find coefficients for a hand picked optimized polynomial that minimizes error evenly across the floating point domain. Actually minimizing error in the floating point domain is a really cool subject. Intuitively, you want the most accuracy when you're close to zero and the mantissa is 10e-37. When you're in the region with mantissa 1, +- 10e-10 means a lot less. One "trick" is to approximate a different polynomial, and then multiply by x, since x itself is naturally distributed across the floating point domain. E.g, instead of approximating sin(x), approximate sin(x)/x distributing the error evenly between +-pi/4. Then multiply by x to get sin(x). For cos, cos(x) gets small and difficult at +-pi/2. If you look at libc, you'll find lots of if statements that apply different hacks to preserve accuracy depending on how close to zero the result is.

okaleniuk 6y ago
Good point. I think, that if you're aiming for the speed, Chebyshev polynomials may even be excessive. It's unlikely that a high order polynomial will beat the hardware implementation. And for tiny polynomials it's best to spend the sparse grid values for the special points. E. g., you can get your approximation both smooth and continuous by adding the target derivatives in +-PI/2 into the Vandermonde matrix. The overall error may become higher with the same polynomial order but the approximation will be smooth.
- 0xfaded 6y ago
  Generally you sum the coefficients from the polynomials to get a single set of coefficients. They are usually very close to the Taylor approximation.
  - okaleniuk 6y ago
    Yes, indeed. What I mean is, with Chebyshov polynomials, you will avoid Runge effect but it's not an issue for a small order polynomial. And to win against the hardware implementation, you have to keep your polynomial small. I measured this for a contemporary Intel processor some maybe ten years ago and found out that 6th degree (actually, its 3 for x^2 since you can throw away all the even coefficients) makes sense performance-wise, yes the error is greater but that's the point of the trade-off. But even 8 or 10 is already doubtful. Of course, there are architectures other than Intel and it might make sense to use higher order polynomials for better accuracy there.
azhenley 6y ago
A few people on Reddit mentioned Chebyshev polynomials too so I think I need to try it out. Helpful tips about distributing the error too. Thanks!
ChrisLomont 6y ago
>And, should have used Chebyshev polynomials If I remember correctly, Pade approximants would be more accurate with less work. Instead of using a polynomial, you use the ratio of two polynomials. They generally work better than Chebyshev since they're a larger class of approximants.
- Someone 6y ago
  Padé approximants (https://en.m.wikipedia.org/wiki/Padé_approximant https://en.m.wikipedia.org/wiki/Padé_approximant) can be better, but “larger class” isn’t a good criterion. The ratio of two polynomials of identical complexity will have twice the number of degrees of freedom as each of its polynomials, and will typically take twice as long to compute (and that’s ignoring the division, which is relatively expensive). So, instead of dividing two polynomials of degree n, you could compute one of degree 2n.
  - ChrisLomont 6y ago
    >The ratio of two polynomials of identical complexity will have twice the number of degrees of freedom as each of its polynomials I wrote with "Pade approximants would be more accurate with less work." for a reason. If they have identical complexity they cannot have twice the degrees of freedom. You're confusing ideas here. First, there are a lot of ways to evaluate Pade than a naive compute two polynomials and then divide them. There's quite a large literature on evaluation methods, just as there are for polynomails (and the naive polynomial evaluation method is generally terrible - at least consider Horner's method). Second, the Chebyshev poly of deg d can simply be the Pade poly P(n) / 1 with P(n) of degree d. Thus Checbyshev is a special case of Pade at the same cost. Thus it's a smaller class, in the pure mathematical sense that one space of functions is a strict subset of the other. So if you want to check all approximations of fixed computational complexity, vary the top and bottom degrees appropriately to check a strictly larger space of approximants for fixed computational cost. You'll usually find that Pade, for the same computational cost, makes a better approximant. It's simply richer. What's more, once you have computed the various powers of x, you can reuse them (unless you're using Horner's method or similar, which is generally better). If you're really looking for minmal cost computation, there is another entire literature on decomposition of functions to minimal operations, and finding the optimal one is NP-complete (but completely doable for these low order approximations). Knuth TAOCP has an intro to the lit under (if I recall) "addition chains" for evaluating polynomials. There is parallel theory for Pade. Thus Pade is a strictly better method. It completely encompasses Chebyshev, and since I've used it a lot, I have found it always better, for the same computational work. It simply let's you optimize over a larger class of approximants.

okaleniuk 6y ago

Good point. I think, that if you're aiming for the speed, Chebyshev polynomials may even be excessive. It's unlikely that a high order polynomial will beat the hardware implementation. And for tiny polynomials it's best to spend the sparse grid values for the special points. E. g., you can get your approximation both smooth and continuous by adding the target derivatives in +-PI/2 into the Vandermonde matrix. The overall error may become higher with the same polynomial order but the approximation will be smooth.

0xfaded 6y ago
Generally you sum the coefficients from the polynomials to get a single set of coefficients. They are usually very close to the Taylor approximation.
- okaleniuk 6y ago
  Yes, indeed. What I mean is, with Chebyshov polynomials, you will avoid Runge effect but it's not an issue for a small order polynomial. And to win against the hardware implementation, you have to keep your polynomial small. I measured this for a contemporary Intel processor some maybe ten years ago and found out that 6th degree (actually, its 3 for x^2 since you can throw away all the even coefficients) makes sense performance-wise, yes the error is greater but that's the point of the trade-off. But even 8 or 10 is already doubtful. Of course, there are architectures other than Intel and it might make sense to use higher order polynomials for better accuracy there.

azhenley 6y ago

A few people on Reddit mentioned Chebyshev polynomials too so I think I need to try it out. Helpful tips about distributing the error too. Thanks!

ChrisLomont 6y ago

>And, should have used Chebyshev polynomials If I remember correctly, Pade approximants would be more accurate with less work. Instead of using a polynomial, you use the ratio of two polynomials. They generally work better than Chebyshev since they're a larger class of approximants.

Someone 6y ago
Padé approximants (https://en.m.wikipedia.org/wiki/Padé_approximant https://en.m.wikipedia.org/wiki/Padé_approximant) can be better, but “larger class” isn’t a good criterion. The ratio of two polynomials of identical complexity will have twice the number of degrees of freedom as each of its polynomials, and will typically take twice as long to compute (and that’s ignoring the division, which is relatively expensive). So, instead of dividing two polynomials of degree n, you could compute one of degree 2n.
- ChrisLomont 6y ago
  >The ratio of two polynomials of identical complexity will have twice the number of degrees of freedom as each of its polynomials I wrote with "Pade approximants would be more accurate with less work." for a reason. If they have identical complexity they cannot have twice the degrees of freedom. You're confusing ideas here. First, there are a lot of ways to evaluate Pade than a naive compute two polynomials and then divide them. There's quite a large literature on evaluation methods, just as there are for polynomails (and the naive polynomial evaluation method is generally terrible - at least consider Horner's method). Second, the Chebyshev poly of deg d can simply be the Pade poly P(n) / 1 with P(n) of degree d. Thus Checbyshev is a special case of Pade at the same cost. Thus it's a smaller class, in the pure mathematical sense that one space of functions is a strict subset of the other. So if you want to check all approximations of fixed computational complexity, vary the top and bottom degrees appropriately to check a strictly larger space of approximants for fixed computational cost. You'll usually find that Pade, for the same computational cost, makes a better approximant. It's simply richer. What's more, once you have computed the various powers of x, you can reuse them (unless you're using Horner's method or similar, which is generally better). If you're really looking for minmal cost computation, there is another entire literature on decomposition of functions to minimal operations, and finding the optimal one is NP-complete (but completely doable for these low order approximations). Knuth TAOCP has an intro to the lit under (if I recall) "addition chains" for evaluating polynomials. There is parallel theory for Pade. Thus Pade is a strictly better method. It completely encompasses Chebyshev, and since I've used it a lot, I have found it always better, for the same computational work. It simply let's you optimize over a larger class of approximants.