[GiNaC-devel] Nested Polynomial Algorithm

[Frank Greenhalgh]

 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.cebix.net/pipermail/ginac-devel/attachments/20110310/8d05c372/attachment.html>