Math::Polynomial::Horner -- stringize Math::Polynomial in Horner form
use Math::Polynomial; my $poly = Math::Polynomial->new(7,8,0,9,4,5); use Math::Polynomial::Horner; print Math::Polynomial::Horner::as_string($poly, {times=>'*'}); # ((((5*x + 4)*x + 9)*x^2 + 8)*x + 7)
This is a few lines of code to format Math::Polynomial
objects as strings in Horner form. It uses parentheses to group terms for multiplications by x rather than powering.
Horner form is quite good for computer evaluation. If you adjust times
, power
etc in the string config then it can be pasted into a program.
For Perl the default "descending" comes out better than ascending because Perl evaluates left to right so the descending does each coefficient addition successively, whereas ascending pushes all the coefficients on the stack before working down through them.
An obvious optimization for evaluation is to watch for middle powers like x^2 in the synopsis above which arise from runs of zero coefficients, and hold them in temporary variables if needed more than once. Something like that might be possible in the future for a program code form.
More sophisticated optimizations can be had from power trees or partly or completely factorizing the polynomial to find repeated roots. Some of that may be a bit difficult, and for that matter Math::Symbolic
might be a better way to keep track of transformations applied.
$string = Math::Polynomial::Horner::as_string ($poly)
$string = Math::Polynomial::Horner::as_string ($poly, $sconfig)
Return $poly
as a string in Horner form.
Optional $config
is a hashref of stringize parameters the same as $poly->as_string
takes, plus extra fields described below.
In addition to the basic string configurations of Math::Polynomial
the following are recognised.
left_paren
, string, default "("right_paren
, string, default ")"Internal parentheses to use. prefix
and suffix
are used at the very start and end of the string so if you change left_paren
and right_paren
then you will probably change prefix
and suffix
too, perhaps to empty strings if you don't want an outermost set of parens.
$str = Math::Polynomial::Horner::as_string ($poly, { left_paren => '[', right_paren => ']', prefix => '', suffix => '' });
There's a couple of secret experimental options in the code too. power_by_times_upto
prefers multiplications over powering when there's zero coefficients to be skipped. fold_sign_swap_end
extends fold_sign
to swap the order of the high term and following factor to turn for instance (-3*x + 1) into (1 - 3*x). It can save a negation if the high coefficient is -1 and the next is positive. And for_perl
gives Perl code power
operator and turns on fold_sign
. Not sure yet if these are a good idea. The Perl style might not suit if using values or coefficients which are not plain numbers but instead an object, matrix, whatever.
http://user42.tuxfamily.org/math-polynomial-horner/index.html
Math-Polynomial-Horner is Copyright 2010, 2011 Kevin Ryde
Math-Polynomial-Horner is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.
Math-Polynomial-Horner is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with Math-Polynomial-Horner. If not, see <http://www.gnu.org/licenses/>.