Name:

fpminimax computes a good polynomial approximation with fixed-point or floating-point coefficients

Usage:

fpminimax(f, n, formats, range, indic1, indic2, indic3, P) : (function, integer, list, range, absolute|relative | fixed|floating | function, absolute|relative | fixed|floating | function, absolute|relative | fixed|floating | function, function) -> function fpminimax(f, monomials, formats, range, indic1, indic2, indic3, P) : (function, list, list, range, absolute|relative | fixed|floating | function, absolute|relative | fixed|floating | function, absolute|relative | fixed|floating | function, function) -> function fpminimax(f, n, formats, L, indic1, indic2, indic3, P) : (function, integer, list, list, absolute|relative | fixed|floating | function, absolute|relative | fixed|floating | function, absolute|relative | fixed|floating | function, function) -> function fpminimax(f, monomials, formats, L, indic1, indic2, indic3, P) : (function, list, list, list, absolute|relative | fixed|floating | function, absolute|relative | fixed|floating | function, absolute|relative | fixed|floating | function, function) -> function

Parameters:

• f is the function to be approximated
• n is the degree of the polynomial that must approximate f
• monomials is the list of monomials that must be used to represent the polynomial that approximates f
• formats is a list indicating the formats that the coefficients of the polynomial must have
• range is the interval where the function must be approximated
• L is a list of interpolation points used by the method
• indic1 (optional) is one of the optional indication parameters. See the detailed description below.
• indic2 (optional) is one of the optional indication parameters. See the detailed description below.
• indic3 (optional) is one of the optional indication parameters. See the detailed description below.
• P (optional) is the minimax polynomial to be considered for solving the problem.

Description:

• fpminimax uses a heuristic (but practically efficient) method to find a good polynomial approximation of a function f on an interval range. It implements the method published in the article:
Efficient polynomial L^\infty - approximations Nicolas Brisebarre and Sylvain Chevillard
Proceedings of the 18th IEEE Symposium on Computer Arithmetic (ARITH 18)
pp. 169-176
• The basic usage of this command is fpminimax(f, n, formats, range). It computes a polynomial approximation of f with degree at most n on the interval range. formats is a list of integers or format types (such as double, doubledouble, etc.). The polynomial returned by the command has its coefficients that fit the formats indications. For instance, if formats[0] is 35, the coefficient of degree 0 of the polynomial will fit a floating-point format of 35 bits. If formats[1] is D, the coefficient of degree 1 will be representable by a floating-point number with a precision of 53 bits (which is not necessarily an IEEE 754 double precision number. See the remark below), etc.
• The second argument may be either an integer or a list of integers interpreted as the list of desired monomials. For instance, the list [|0,2,4,6|] indicates that the polynomial must be even and of degree at most 6. Giving an integer n as second argument is equivalent as giving [|0,...,n|].
The list of formats is interpreted with respect to the list of monomials. For instance, if the list of monomials is [|0,2,4,6|] and the list of formats is [|161,107,53,24|], the coefficients of degree 0 is searched as a floating-point number with precision 161, the coefficient of degree 2 is searched as a number of precision 107, and so on.
• The list of formats may contain either integers or format types (double, doubledouble, tripledouble and doubleextended). The list may be too large or even infinite. Only the first indications will be considered. For instance, for a degree n polynomial, formats[n+1] and above will be discarded. This lets one use elliptical indications for the last coefficients.
• The floating-point coefficients considered by fpminimax do not have an exponent range. In particular, in the format list, double or 53 does not imply that the corresponding coefficient is an IEEE-754 double.
• By default, the list of formats is interpreted as a list of floating-point formats. This may be changed by passing fixed as an optional argument (see below). Let us take an example: fpminimax(f, 2, [107, DD, 53], [0;1]). Here the optional argument is missing (we could have set it to floating). Thus, fpminimax will search for a polynomial of degree 2 with a constant coefficient that is a 107 bits floating-point number, etc.
Currently, doubledouble is just a synonym for 107 and tripledouble a synonym for 161. This behavior may change in the future (taking into account the fact that some double-doubles are not representable with 107 bits).
Second example: fpminimax(f, 2, [25, 18, 30], [0;1], fixed). In this case, fpminimax will search for a polynomial of degree 2 with a constant coefficient of the form m/2^25 where m is an integer. In other words, it is a fixed-point number with 25 bits after the point. Note that even with argument fixed, the formats list is allowed to contain double, doubledouble or tripledouble. In this this case, it is just a synonym for 53, 107 or 161. This is deprecated and may change in the future.
• The fourth argument may be a range or a list. Lists are for advanced users that know what they are doing. The core of the method is a kind of approximated interpolation. The list given here is a list of points that must be considered for the interpolation. It must contain at least as many points as unknown coefficients. If you give a list, it is also recommended that you provide the minimax polynomial as last argument. If you give a range, the list of points will be automatically computed.
• The fifth, sixth and seventh arguments are optional. By default, fpminimax will approximate f while optimizing the relative error, and interpreting the list of formats as a list of floating-point formats.
This default behavior may be changed with these optional arguments. You may provide zero, one, two or three of the arguments in any order. This lets the user indicate only the non-default arguments.
The three possible arguments are: The constrained part lets the user assign in advance some of the coefficients. For instance, for approximating exp(x), it may be interesting to search for a polynomial p of the form p = 1 + x + x^2/2 + a3 x^3 + a4 x^4. Thus, there is a constrained part q = 1 + x + x^2/2 and the unknown polynomial should be considered in the monomial basis [|3, 4|]. Calling fpminimax with monomial basis [|3,4|] and constrained part q, will return a polynomial with the right form.
• The last argument is for advanced users. It is the minimax polynomial that approximates the function f in the monomial basis. If it is not given this polynomial will be automatically computed by fpminimax.
This minimax polynomial is used to compute the list of interpolation points required by the method. In general, you do not have to provide this argument. But if you want to obtain several polynomials of the same degree that approximate the same function on the same range, just changing the formats, you should probably consider computing only once the minimax polynomial and the list of points instead of letting fpminimax recompute them each time.
Note that in the case when a constrained part is given, the minimax polynomial must take that into account. For instance, in the previous example, the minimax would be obtained by the following command: P = remez(1-(1+x+x^2/2)/exp(x), [|3,4|], range, 1/exp(x)); Note that the constrained part is not to be added to P.
• Note that fpminimax internally computes a minimax polynomial (using the same algorithm as remez command). Thus fpminimax may encounter the same problems as remez. In particular, it may be very slow when Haar condition is not fulfilled. Another consequence is that currently fpminimax has to be run with a sufficiently high working precision.

Example 1:

> P = fpminimax(cos(x),6,[|DD, DD, D...|],[-1b-5;1b-5]);
> printexpansion(P);
(0x3ff0000000000000 + 0xbc09fda20235c100) + x * ((0x3b29ecd485d34781 + 0xb7c1cbc97120359a) + x * (0xbfdfffffffffff98 + x * (0xbbfa6e0b3183cb0d + x * (0x3fa5555555145337 + x * (0x3ca3540480618939 + x * 0xbf56c138142d8c3b)))))

Example 2:

> P = fpminimax(sin(x),6,[|32...|],[-1b-5;1b-5], fixed, absolute);
> display = powers!;
> P;
x * (1 + x^2 * (-357913941 * 2^(-31) + x^2 * (35789873 * 2^(-32))))

Example 3:

> P = fpminimax(exp(x), [|3,4|], [|D,24|], [-1/256; 1/246], 1+x+x^2/2);
> display = powers!;
> P;
1 + x * (1 + x * (1 * 2^(-1) + x * (375300225001191 * 2^(-51) + x * (5592621 * 2^(-27)))))

Example 4:

> f = cos(exp(x));
> pstar = remez(f, 5, [-1b-7;1b-7]);
> listpoints = dirtyfindzeros(f-pstar, [-1b-7; 1b-7]);
> P1 = fpminimax(f, 5, [|DD...|], listpoints, absolute, default, default, pstar);
> P2 = fpminimax(f, 5, [|D...|], listpoints, absolute, default, default, pstar);
> P3 = fpminimax(f, 5, [|D, D, D, 24...|], listpoints, absolute, default, default, pstar);
> print("Error of pstar: ", dirtyinfnorm(f-pstar, [-1b-7; 1b-7]));
Error of pstar:  7.9048441305459735102879831325718745399379329453102e-16
> print("Error of P1:    ", dirtyinfnorm(f-P1, [-1b-7; 1b-7]));
Error of P1:     7.9048441305459735159848647089192667442047469404883e-16
> print("Error of P2:    ", dirtyinfnorm(f-P2, [-1b-7; 1b-7]));
Error of P2:     8.2477144579950871061147021597406077993657714575238e-16
> print("Error of P3:    ", dirtyinfnorm(f-P3, [-1b-7; 1b-7]));
Error of P3:     1.08454277156993282593701156841863009789063333951055e-15
Go back to the list of commands