Skip to content

Tutorial 1 of 5: exp(x) the quick way

Jump to bottom
Sam Hocevar edited this page Jan 2, 2023 · 4 revisions
Clone this wiki locally

This is a hands-on example of the Lol Remez toolkit.

In this section we are going to approximate the $e^{x}$ function on $[-1,1]$ using a polynomial.

Getting started

This tutorial will assume that you successfully downloaded and built LolRemez from source, and have a lolremez or lolremez.exe executable ready.

What does Remez do?

Given a function $f$ and a range $[a,b]$, the Remez algorithm looks for the polynomial $P(x)$ that minimises the following error value $E$:

$$\max_{x \in [a,b]}{\big\vert f(x) - P(x)\big\vert} = E$$

Note that $E$ is not a parameter. It is a value that the algorithm computes together with the polynomial. Though we will see ways to fine-tune the error, a general rule is: if you want a smaller error, ask for a polynomial of higher degree.

Invocation

lolremez --degree 4 --range -1:1 "exp(x)"

What does this mean?

  • exp(x) is the function we want to approximate.
  • --degree 4 asks for a 4th-degree polynomial.
  • --range -1:1 runs the solver on the $[-1,1]$ range.

After all the iterations the output should look like this:

/* Approximation of f(x) = exp(x)
 * on interval [ -1.0000000000000000000, 1.0000000000000000000 ]
 * with a polynomial of degree 4. */
float f(float x)
{
    float u = 4.4155517622880223000e-2f;
    u = u * x + 1.7734527436884122688e-1f;
    u = u * x + 4.9883511709023591553e-1f;
    u = u * x + 9.9730925167444643205e-1f;
    return u * x + 1.0000900001021276399f;
}

Additional options

Adding the --progress flag will also output the actual polynomial at each iteration of the algorithm:

   1.0000900001021276399
 + 9.9730925167444643205e-1 * x
 + 4.9883511709023591553e-1 * x**2
 + 1.7734527436884122688e-1 * x**3
 + 4.4155517622880223000e-2 * x**4

Adding the --stats flag will show timing information as well as the final maximal error:

 -:- timing for extrema: 44.765423 ms
 -:- error: 5.4666760051379794745e-4
 -:- timing for inversion: 1.138785 ms

Analysing the results

Plotting the real exponential function and our fastexp function gives the following curves:

The curves are undistinguishable. Actually they differ by no more than 5.46668e-4, which is the value the lolremez output gave.

It can be verified on the following error curve:

Conclusion

You should now be all set up for your own minimax polynomial computation!

Please report any trouble you may have had with this document to sam@hocevar.net. You may then carry on to the next section: switching to relative error.