Remez tutorial 2/5: switching to relative error

In the previous section, we saw that RemezSolver looked for a polynomial P(x) and the smallest error value E such that:

Where f(x) = exp(x).

A look at the error graph indicates that the error values in -1 and 1 are the same but the relative error values are not: it is about 0.15% for -1 whereas it is about 0.02% for 1.

Representing the relative error mathematically

We actually want a polynomial P(x) and the smallest error value E such that:

Where f(x) = exp(x), just like before, and g(x) = exp(x).

Fortunately RemezSolver is able to find such a polynomial, too.

Source code

#include "lol/math/real.h"
#include "lol/math/remez.h"

using lol::real;
using lol::RemezSolver;

real f(real const &x) { return exp(x); }
real g(real const &x) { return exp(x); }

int main(int argc, char **argv)
{
    RemezSolver<4, real> solver;
    solver.Run(-1, 1, f, g, 30);
    return 0;
}

See the subtle change? solver.Run is passed an additional argument, g, called the weight function.

Compilation and execution

Build and run the above code:

make
./remez

After all the iterations the output should be as follows:

Final error: 5.013601837829611832543456624618162324553e-4
Polynomial estimate:
x**0*9.996300117834416472580281524513498806018e-1
+x**1*9.979375106869197460757909002367767916720e-1
+x**2*5.028987713562873328002723059456010884108e-1
+x**3*1.764900437662188117750392851519785741686e-1
+x**4*3.996265258908758676733711372875779522269e-2

We can therefore write the corresponding C++ function:

double fastexp2(double x)
{
    const double a0 = 9.996300117834416472580281524513498806018e-1;
    const double a1 = 9.979375106869197460757909002367767916720e-1;
    const double a2 = 5.028987713562873328002723059456010884108e-1;
    const double a3 = 1.764900437662188117750392851519785741686e-1;
    const double a4 = 3.996265258908758676733711372875779522269e-2;

    return a0 + x * (a1 + x * (a2 + x * (a3 + x * a4)));
}

Analysing the results

Again, the polynomial and the original function are undistinguishable:

However, the error curve now looks like this:

We accomplished our goal: the smaller the value of f(x), the smaller the error.

Conclusion

You should now be able to weigh your error function to control the final error curve of the minimax polynomial!

Please report any trouble you may have had with this document to ​sam@hocevar.net. You may then carry on to the next section: fixing parameters in the minimax polynomial.