Nested Polynomial Algorithm
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.
participants (1)
-
Frank Greenhalgh