The following algorithm creates a nested polynomial to minimize the number
of multiplications and additions in evaluating a polynomial at some given
point, x. I use it to reduce my Finite Element Method basis functions.
//Converts an *expanded* polynomial into a nested polynomial for efficient
evaluation at points
ex nested_polynomial( ex polynomial, realsymbol x ){
//result is returned to the user, highest order is the peeled off highest
order term of the polynomial
ex result=0, highest_order;
//While the polynomial is not empty continue peeling off the highest degree
while( polynomial.degree( x ) != 0 ){
//get the highest order term
highest_order = polynomial.lcoeff(x) * pow( x, polynomial.degree(x) );
//add to nest
result+= highest_order.lcoeff( x );
//remove the highest order term from the expanded polynomial
polynomial-=highest_order;
//multiply the result by the proper amount of x's
result*=pow(x, highest_order.degree(x)-
polynomial.degree(x) );
}
//correct for forgotten 0th order terms
result+=polynomial.lcoeff(x);
return result;
}
Example:
polynomial = 10*x^5 + 3*x^3 + 1;
the function would return (with polynomial and x as inputs):
1+x^3*(3+x^2*10)
which minimizes the number of multiplications and additions we need to do
in evaluation.
The first polynomial form needs 5+3=8 multiplications and 2 additions, while
the second form needs 2+3=5 multiplications and 2 additions.