concave.h File Reference

Definition of a concave function computed from the coefficients of some polynomial. More...

Go to the source code of this file.

Data Structures
struct	concave_struct
	Description of a concave function computed from the coefficients of some polynomial. More...

Macros
#define	BITS_GUARD   6
	The extra bits that are needed as explained in [1].

Typedefs
typedef concave_struct *	concave
	Convenience pointer to concave_struct.

Functions
concave	conc_new (list l, prec_t prec)
	Computes the concave cover of the graph of a list l sorted in decreasing order. More...
bool	conc_free (concave f)
	Frees all the memory used by the concave map f, assuming the struct has been allocated with malloc(), for example with conc_new(). More...
bool	conc_range (concave f, real_t la)
	Computes the range of indexes in f->allPow to use for evaluating the original polynomial at z with la=log_2|z|. More...
bool	conc_range_der (concave f, real_t la)
	Computes the range of indexes in f->allPow to use for evaluating the derivative of the original polynomial at z with la=log_2|z|. More...

Detailed Description

Definition of a concave function computed from the coefficients of some polynomial.

Admissible powers are for any of the original polynomial P or its derivative P'.

Definition in file concave.h.

Function Documentation

conc_free()

bool conc_free

(

concave

f

)

Frees all the memory used by the concave map f, assuming the struct has been allocated with malloc(), for example with conc_new().

Parameters

f

the map

Returns

true if successfull, false otherwise.

conc_new()

concave conc_new	(	list	l,
		prec_t	prec
	)

Computes the concave cover of the graph of a list l sorted in decreasing order.

Note

Retains the list of non-zero coefficients in all.

Parameters

l	the sorted list
prec	the precision that will be used to evaluate the polynomial

Returns

the concave function above the graph of l, NULL if some error occurred.

conc_range()

bool conc_range	(	concave	f,
		real_t	la
	)

Computes the range of indexes in f->allPow to use for evaluating the original polynomial at z with la=log_2|z|.

Stores the result in the f->start and respectively f->end.

Note

f->start>=f->end, otherwise the value of the polynomial is 0.

Parameters

f	the map
la	the slope, or log_2|z|

Returns

true if successfull, false otherwise.

conc_range_der()

bool conc_range_der	(	concave	f,
		real_t	la
	)

Computes the range of indexes in f->allPow to use for evaluating the derivative of the original polynomial at z with la=log_2|z|.

Stores the result in the f->start and respectively f->end.

Note

f->start>=f->end, otherwise the value of the derivative is 0.

Parameters

f	the map
la	the slope, or log_2|z|

Returns

true if successfull, false otherwise.