[[TOC]]
= Remez exchange toolbox =
'''TL;DR:''' this toolbox helps find CPU-friendly approximations to complicated and/or slow functions.
The Remez exchange algorithm is a fast method for approximating functions in a Chebyshev space. More precisely, the Lol Engine provides its own implementation of the Remez exchange algorithm to find '''polynomial approximations to real functions'''. Such polynomials are also known as '''minimax polynomials'''.
== Overview ==
Remez helps speed up code such as the following:
{{{
#!cpp
double y = sin(x);
}}}
The following graph shows approximations of ''sin(x)'' over [-π, π] using three different polynomials:
* the Taylor series to the 5th order: ''x-x³/3!+x⁵/5! ''
* the Taylor series to the 7th order: ''x-x³/3!+x⁵/5!-x⁷/7! ''
* a minimax polynomial to the 5th order found using LolRemez: ''x-0.1587164x³+0.00585375x⁵''
The graph only shows [0, π] but [-π, 0] is similar:
[[Image(taylor-vs-remez.png, nolink)]]
It is obvious that the polynomial found using the Remez method is closer to the sine curve than the Taylor series of the same order, and still better than the Taylor series of the next order. If you want to approximate a function over an interval, Remez is always better. If you want to convince people that it is, please refer them to [blog:2011/12/21/better-function-approximations this blog article].
In many situations the above code can therefore be replaced with:
{{{
#!cpp
double y = x - x * x * x * (0.1587164 + x * x * 0.00585375);
}}}
On most systems this will be up to 20 times faster than the original `sin` call. The tradeoff is lost precision, but Remez allows to tune that, too.
== Prerequisites ==
In order to use LolRemez, you need:
* basic knowledge of C++ (include headers, write functions, compile programs)
* decent knowledge of [http://en.wikipedia.org/wiki/Algebra algebra] (mainly [http://en.wikipedia.org/wiki/Polynomial polynomials]) and [http://en.wikipedia.org/wiki/Mathematical_analysis analysis] (if you don’t understand how a function behaves, you should not try to approximate it)
Essentially, if you don’t understand the maths in the tutorial, there is a problem either with the tutorial, or with your math skills.
Before you start reading the tutorial, I suggest you have a quick look at the Lol Engine [wiki:doc/lol/math/real.h real numbers] documentation.
== Tutorial ==
There are five main sections in the tutorial:
* 1/5: [wiki:doc/maths/remez/tutorial-exponential exp(x) the quick way]
* 2/5: [wiki:doc/maths/remez/tutorial-relative-error switching to relative error]
* 3/5: [wiki:doc/maths/remez/tutorial-changing-variables changing variables for simpler polynomials]
* 4/5: [wiki:doc/maths/remez/tutorial-fixing-parameters fixing lower-order parameters]
* 5/5: [wiki:doc/maths/remez/tutorial-additional-tips additional tips]