Skip Menu |

This queue is for tickets about the Math-Polynomial CPAN distribution.

Report information
The Basics
Id: 46575
Status: resolved
Priority: 0/
Queue: Math-Polynomial

People
Owner: hasch-cpan [...] cozap.com
Requestors: user42 [...] zip.com.au
Cc: randomcoder1 [...] gmail.com
AdminCc:

Bug Information
Severity: Wishlist
Broken in: (no value)
Fixed in: 1.003



Subject: pretty-printing polynomials
This idea came up during discussion of a bug [rt.cpan.org #44829] and has now a ticket of its own. Kevin Ryde has asked for more options wrt stringification, in particular output formatted like perl code used in evaluating polynomials. This could go into a module Math::Polynomial::PrettyPrint or some namespace indicating that polynomial expressions are being optimized using Horner's method. This feature is purely a matter of formatting data already available through Math::Polynomial. A possible implementation has been hidden in the examples collection distributed with the module, but a more accessible application interface remains to be designed. -Martin
Subject: Re: [rt.cpan.org #46575] AutoReply: pretty-printing polynomials
Date: Wed, 03 Jun 2009 11:48:59 +1000
To: bug-Math-Polynomial [...] rt.cpan.org
From: Kevin Ryde <user42 [...] zip.com.au>
Don't forget to avoid "$str .=", since it makes stringizing an O(N^2) operation, where of course it should be linear. For me it only seems to hurt at about 100,000 coeffs, which is pretty humongous, but good algorithms well implemented has to be the aim of any library.
What kind of pretty printing did you have in mind ? First idea I can think of is LaTeX ..
On Mon Aug 17 01:45:51 2009, WSDOOKADR wrote: Show quoted text
> What kind of pretty printing did you have in mind ? > First idea I can think of is LaTeX ..
There are plenty of possibilities, all involving some kind of text processing based on information coming from a polynomial object. I think, however, that most of this processing could be done in a way that is useful for more kinds of arithmetic expressions than just polynomials. Examples: Simplifying, rounding, formatting as code for a given language (such as your typesetting system). For that reason I am inclined to drop this wishlist item from the Math::Polynomial roadmap in favor of a more general solution in a more general namespace. If you know of other modules Math::Polynomial should interface with in order to extend its formatting capabilities (or whatever), I am open for suggestions. -Martin
On Wed Aug 19 09:41:50 2009, MHASCH wrote: Show quoted text
> On Mon Aug 17 01:45:51 2009, WSDOOKADR wrote:
> > What kind of pretty printing did you have in mind ? > > First idea I can think of is LaTeX ..
> > There are plenty of possibilities, all involving > some kind of text processing based on information coming > from a polynomial object. I think, however, that most > of this processing could be done in a way that is useful > for more kinds of arithmetic expressions than just > polynomials. > > Examples: Simplifying, rounding, formatting as code for > a given language (such as your typesetting system).
Can you be more explicit about 'simplifying' and 'rounding' ? I'm not sure what you mean. Show quoted text
> > For that reason I am inclined to drop this wishlist item > from the Math::Polynomial roadmap in favor of a more > general solution in a more general namespace. > > If you know of other modules Math::Polynomial should > interface with in order to extend its formatting > capabilities (or whatever), I am open for suggestions. > > -Martin
For example a more general way of doing these things would be: First we use(or we extend so that we can use) Math::Symbolic on a polynomial to create a parse tree from it ( parse_from_string method from Math::Symbolic ). Then we use Math::Symbolic::Custom::LaTeXDumper to take that Math::Symbolic tree and use the method to_latex that LaTeXDumper provides in order to get LaTeX code ,and then we can draw images of the formula of the polynomial.
On Wed Aug 19 12:28:20 2009, WSDOOKADR wrote: Show quoted text
> On Wed Aug 19 09:41:50 2009, MHASCH wrote:
> > On Mon Aug 17 01:45:51 2009, WSDOOKADR wrote:
> > > What kind of pretty printing did you have in mind ?
> > Examples: Simplifying, rounding, formatting as code for > > a given language (such as your typesetting system).
> Can you be more explicit about 'simplifying' and 'rounding' ? > I'm not sure what you mean.
One form already mentioned was a Horner schema, which may be "simplified" by way of constant folding and redundant parentheses elimination. "Rounding" meant rounding of coefficients for terse output. None of these examples is terribly important, my point being that one should carefully consider what features to put into a specialized polynomial package and what elsewhere. Show quoted text
> > If you know of other modules Math::Polynomial should > > interface with in order to extend its formatting > > capabilities (or whatever), I am open for suggestions.
Show quoted text
> For example a more general way of doing these things would be: > First we use(or we extend so that we can use) Math::Symbolic on a > polynomial to create a parse tree from it ( parse_from_string method > from Math::Symbolic ). [...]
A symbolic calculator is definitely something useful to be compatible with. Nice suggestion. -Martin
On Thu Aug 20 19:54:44 2009, MHASCH wrote: Show quoted text
> On Wed Aug 19 12:28:20 2009, WSDOOKADR wrote:
> > On Wed Aug 19 09:41:50 2009, MHASCH wrote:
> > > On Mon Aug 17 01:45:51 2009, WSDOOKADR wrote:
> > > > What kind of pretty printing did you have in mind ?
> > > Examples: Simplifying, rounding, formatting as code for > > > a given language (such as your typesetting system).
> > Can you be more explicit about 'simplifying' and 'rounding' ? > > I'm not sure what you mean.
> > One form already mentioned was a Horner schema, which may be > "simplified" by way of constant folding and redundant parentheses > elimination.
From what I remember from school and from refreshing my memory from here If you're refering to this http://planetmath.org/encyclopedia/ HornersRule.html and here http://en.wikipedia.org/wiki/Horner_scheme I think that after applying Horner's scheme the polynomial will look like a0+x(a1+x(a2+x(...+x(a_{n-1}+x*an)...) So basically there will be lots of parenthesis. If however some of the ais happen to be 0 , then then yes we can fold some parenthesis , is that what you're reffering to ? Show quoted text
> "Rounding" meant rounding of coefficients for terse > output.
Option1 sprintf("%.3f",3.141592); Option2 Number::Format Option3 Math::Round Option4 Math::Round::Var Which would be best ? Show quoted text
> None of these examples is terribly important, my point > being that one should carefully consider what features to put > into a specialized polynomial package and what elsewhere.
So this feature should lie elsewhere ? Where ? (same namespace I presume) Show quoted text
> > > If you know of other modules Math::Polynomial should > > > interface with in order to extend its formatting > > > capabilities (or whatever), I am open for suggestions.
>
> > For example a more general way of doing these things would be: > > First we use(or we extend so that we can use) Math::Symbolic on a > > polynomial to create a parse tree from it ( parse_from_string
method Show quoted text
> > from Math::Symbolic ). [...]
> > A symbolic calculator is definitely something useful to be > compatible with. Nice suggestion. > > -Martin
With a small modification to the as_string routine of your module, I had to add a "*" to the end of line 634 in Polynomial.pm 634 $result .= $config{'convert_coeff'}->($coeff)."*"; So that the output could be parsed by Math::Symbolic 1 use Math::Polynomial; 2 use Math::Symbolic::Custom::LaTeXDumper; 3 use Math::Symbolic qw/parse_from_string/; 4 use Data::Dumper; 5 use feature 'say'; 6 $p = Math::Polynomial->new(0, -2, 3, 1); 7 8 9 my $tree = parse_from_string($p->as_string); 10 #print Dumper $tree; 11 12 say $tree->to_latex; 13 say $p; OUTPUT: x^3 + 3 x^2 + -2 x (x^3 + 3* x^2 + -2* x) P.S. : can I use html tags here ? how do I format some code ? Actually , the initial output of your code was valid LaTeX(before I modified it with the "*").
On Thu Aug 20 22:40:19 2009, WSDOOKADR wrote: Show quoted text
> With a small modification to the as_string routine of your module, > I had to add a "*" to the end of line 634 in Polynomial.pm > 634 $result .= $config{'convert_coeff'}->($coeff)."*"; > So that the output could be parsed by Math::Symbolic
Good grief, don't fiddle with internals like this (actually breaking things), just look more closely at the docs. The proper way of getting an asterisk in that place would be something like calling $p->as_string({'times' => '*'}) or setting such defaults beforehand using the string_config method. Your observation that, through an intermediate string representation, there would be no need for a dedicated interface to Math::Symbolic, is valuable advice, though. Thank you for sharing your ideas in this thread. I think I am now close to a conclusion. -Martin
Subject: Re: [rt.cpan.org #46575] pretty-printing polynomials
Date: Sat, 22 Aug 2009 10:39:10 +1000
To: bug-Math-Polynomial [...] rt.cpan.org
From: Kevin Ryde <user42 [...] zip.com.au>
"Petrea Corneliu Stefan via RT" <bug-Math-Polynomial@rt.cpan.org> writes: Show quoted text
> > a0+x(a1+x(a2+x(...+x(a_{n-1}+x*an)...)
Yes, and perhaps laid out across multiple lines for clarity if the coefficients are a bit big. A form using "+=" and "*=" into a single variable might help perl save a little copying of values, when cut and pasted into code to be run. (Even C/C++ likewise if the coeffs are not a native float/int type.) I suspect the base printing options can give TeX, probably other formats like nroff too. A canned set of options for that might be nice. But other forms like Horner with parens, or a little bit of lightweight common subexpression noticing, are rearranged a bit. Some direct ascii art would be another possibility (with even more limited use).
On Fri Aug 21 20:39:53 2009, user42@zip.com.au wrote: Show quoted text
> "Petrea Corneliu Stefan via RT" <bug-Math-Polynomial@rt.cpan.org>
writes: Show quoted text
> > > > a0+x(a1+x(a2+x(...+x(a_{n-1}+x*an)...)
> > Yes, and perhaps laid out across multiple lines for clarity if the > coefficients are a bit big. A form using "+=" and "*=" into a single > variable might help perl save a little copying of values, when cut and > pasted into code to be run. (Even C/C++ likewise if the coeffs are
not Show quoted text
> a native float/int type.)
Can you give an example here of how we'd use the *= and += ? I will attach a patch , please let me know if it's what you were thinking of. Show quoted text
> > I suspect the base printing options can give TeX, probably other
formats Show quoted text
> like nroff too. A canned set of options for that might be nice. But > other forms like Horner with parens, or a little bit of lightweight > common subexpression noticing, are rearranged a bit. Some direct
ascii Show quoted text
> art would be another possibility (with even more limited use).
So bottom line is I've used the Horner representation and written a method called pretty_print for this. As a last proposal , I think we could include mimetex along with Math::Polynomial and have it compiled so that we can generate images of the polynomials. Here is mimetex -> http://www.forkosh.com/mimetex.html I've written also a test_pol.pl that will show the output of the print method. I will also write the output here: ((((((((((((((6 * x) + 6) * x) * x) * x) + 3) * x) * x) + 1) * x) + 3) * x) + (-2)) * x) + 2 ((((((((((((((6 * x) + 6) * x) * x) * x) + 3) * x) * x) + 1) * x) + 3) * x) + (-2) ) * x) + 2 (6 x^9 + 6 x^8 + 3 x^5 + x^3 + 3 x^2 + -2 x + 2) Patches rolled in.
--- Polynomial.pm 2009-06-12 15:00:28.000000000 +0300 +++ /usr/local/share/perl/5.10.0/Math/Polynomial.pm 2009-08-22 06:29:16.000000000 +0300 @@ -589,6 +589,26 @@ return $ad->evaluate($upper) - $ad->evaluate($lower); } +sub pretty_print { + my ($this , $multiple_lines) = @_; + use Math::Symbolic; + my $x = Math::Symbolic::Variable->new('x'); + + my @ais = reverse $this->coeff; # we want them from the smallest one to the largest one + my $pretty = Math::Symbolic->parse_from_string(sprintf "%s",shift @ais); + + for my $coeff (@ais ) { + $pretty *= $x; + $pretty += $coeff if $coeff; + }; + + my $output = $pretty->to_string(); + if( defined $multiple_lines && $multiple_lines == 1 ) { + $output =~ s/\)/\)\n/g; + } + return $output ; +} + sub as_string { my ($this, $params) = @_; my %config = (
use Math::Polynomial; use Math::Symbolic::Custom::LaTeXDumper; use Math::Symbolic qw/parse_from_string/; use Data::Dumper; use feature 'say'; $p = Math::Polynomial->new(2, -2, 3, 1 , 0 , 3 , 0 , 0 , 6, 6); #my $tree = parse_from_string($p->as_string); #print Dumper $tree; say $p->pretty_print."\n"; say $p->pretty_print(1)."\n"; say $p; #print $p;
Subject: Re: [rt.cpan.org #46575] pretty-printing polynomials
Date: Sat, 29 Aug 2009 10:13:50 +1000
To: bug-Math-Polynomial [...] rt.cpan.org
From: Kevin Ryde <user42 [...] zip.com.au>
"Petrea Corneliu Stefan via RT" <bug-Math-Polynomial@rt.cpan.org> writes: Show quoted text
> > I will attach a patch , please let me know if it's what you were > thinking of.
Not really, or not with the name pretty_print. The horner form including += style is quite an ugly print actually, it'd be a slightly specialized thing, not necessarily in the main .pm file. I expect Math::Symbolic isn't needed to print it. Show quoted text
> ... * x) * x) * x)
There'd be a choice between multiple "*" multiplies and an exponential "**" there. Which one is better might depend on the coefficient type. For plain floats perhaps 3 or more would definitely be "**". Or give "**" always and let perl and/or the coeff module worry about it.
I am now thinking of a small addition to the base module that will support generating Horner schemes as well as Math::Symbolic trees via another configurable output method, named as_tree. The deal is that as_tree will deliver arithmetic atoms to callback functions which in turn can call Math::Symbolic constructors or simply add their arguments to a string. It may be feasible to refactor as_string into a wrapper for as_tree with some intelligent parameter conversion. Whether power sums or Horner-type grouping are used would be one of the configuration options. The downside is that we then give an even more low-level tool than as_string into the hands of our poor users. It will probably require tons of documentation and never be used outside the test suite. A way to avoid this might be to declare as_tree an obscure feature while providing a couple of convenience wrappers with nice defaults. This in turn can bring us back to the beginning of this thread where Kevin simply wanted to have nested parentheses in the string output. Bottom line: The API design is once again more tricky to get right than implementing the algorithms. But I like that. Thanks for bearing with me so far. -Martin
Done. On Fri Aug 28 20:14:44 2009, user42@zip.com.au wrote: Show quoted text
> "Petrea Corneliu Stefan via RT" <bug-Math-Polynomial@rt.cpan.org>
writes: Show quoted text
> > > > I will attach a patch , please let me know if it's what you were > > thinking of.
> > Not really, or not with the name pretty_print. The horner form > including += style is quite an ugly print actually, it'd be a slightly > specialized thing, not necessarily in the main .pm file. I expect > Math::Symbolic isn't needed to print it. >
> > ... * x) * x) * x)
> > There'd be a choice between multiple "*" multiplies and an exponential > "**" there. Which one is better might depend on the coefficient type. > For plain floats perhaps 3 or more would definitely be "**". Or give > "**" always and let perl and/or the coeff module worry about it.
-- Your bugs , they are afraid of me.
--- /usr/local/share/perl/5.10.0/Math/Polynomial.pm 2009-06-12 00:51:47.000000000 +0300 +++ Math/Polynomial.pm 2009-09-05 00:05:35.000000000 +0300 @@ -589,6 +589,60 @@ return $ad->evaluate($upper) - $ad->evaluate($lower); } +sub pretty_print { + + my ($this , $multiple_lines , $pack) = @_; + + my @ais = reverse $this->coeff; # we want them from the smallest one to the largest one + # by ais we mean actually a_i , the generic coefficient + + my $pretty = ''; + if( defined $pack && $pack == 1 ) { + + } else { + $pretty = '('x$this->degree(); + } + $pretty .= shift @ais; + + my $parens = 0; + my $power = 0; # actually I'm strong + + for my $coeff (@ais ) { + my $coeffstr = + $coeff > 0 + ? "+$coeff" + : $coeff; # this is to avoid cases like x + -2 or similar things + if( defined $pack && $pack == 1 ) { + if( $coeff == 0 ) { + $power++; + } else { + $parens++; + # we count how many parenthesis we closed so we know how many to open ( scratching left ear with right hand) + if( $power > 0 ) { + $pretty .= ' x**'.($power+1)." $coeffstr)"; + } else { + $pretty .= " x $coeffstr )"; + }; + $power=0; + } + } else { + $pretty .= ' x'; + $pretty .= "$coeffstr" if $coeff; + $pretty .= ')'; + }; + }; + + if( defined $pack && $pack == 1 ) { + $pretty = ( '('x$parens ) + .$pretty; # prepend the needed open parenthesis + } + + if( defined $multiple_lines && $multiple_lines == 1 ) { + $pretty =~ s/\)/\)\n/g; + } + return $pretty ; +} + sub as_string { my ($this, $params) = @_; my %config = (
Also , a script to test it with is attached. Sample output: WITHOUT Packing -> (((((((((6 x+6) x) x) x+3) x) x+1) x+3) x-2) x+2) With Packing -> ((((((6 x +6 ) x**3 +3) x**2 +1) x +3 ) x -2 ) x +2 ) As String -> (6 x^9 + 6 x^8 + 3 x^5 + x^3 + 3 x^2 + -2 x + 2) On Fri Aug 28 20:14:44 2009, user42@zip.com.au wrote: Show quoted text
> "Petrea Corneliu Stefan via RT" <bug-Math-Polynomial@rt.cpan.org>
writes: Show quoted text
> > > > I will attach a patch , please let me know if it's what you were > > thinking of.
> > Not really, or not with the name pretty_print. The horner form > including += style is quite an ugly print actually, it'd be a slightly > specialized thing, not necessarily in the main .pm file. I expect > Math::Symbolic isn't needed to print it. >
> > ... * x) * x) * x)
> > There'd be a choice between multiple "*" multiplies and an exponential > "**" there. Which one is better might depend on the coefficient type. > For plain floats perhaps 3 or more would definitely be "**". Or give > "**" always and let perl and/or the coeff module worry about it.
-- Your bugs , they are afraid of me.
use lib './'; use Math::Polynomial; use Data::Dumper; sub say { print (@_,"\n"); }; #say Dumper %INC; my @coeff_array =(2, -2, 3, 1 , 0 , 3 , 0 , 0 , 6, 6); $p = Math::Polynomial->new(@coeff_array); #my $tree = parse_from_string($p->as_string); #print Dumper $tree; say "COEFF @coeff_array"."\n"; say $p->pretty_print."\n"; #say $p->pretty_print(1)."\n"; say $p->pretty_print(0,1)."\n"; say $p; #print $p;
On Tue Sep 01 12:03:42 2009, MHASCH wrote: Show quoted text
> I am now thinking of a small addition to the base module that will > support generating Horner schemes as well as Math::Symbolic trees via > another configurable output method, named as_tree. > > The deal is that as_tree will deliver arithmetic atoms
can you please describe what you mean by "arithmetic atoms" ? Show quoted text
> to callback > functions which in turn can call Math::Symbolic constructors or simply > add their arguments to a string. It may be feasible to refactor > as_string into a wrapper for as_tree with some intelligent parameter > conversion. Whether power sums or Horner-type grouping are used would > be one of the configuration options. > > The downside is that we then give an even more low-level tool than > as_string into the hands of our poor users. It will probably require > tons of documentation and never be used outside the test suite.
If needed I can write docs. I'm not in a rush :) Show quoted text
> > A way to avoid this might be to declare as_tree an obscure feature
while Show quoted text
> providing a couple of convenience wrappers with nice defaults. > This in turn can bring us back to the beginning of this thread where > Kevin simply wanted to have nested parentheses in the string output. > > Bottom line: The API design is once again more tricky to get right
than Show quoted text
> implementing the algorithms. But I like that. Thanks for bearing
with Show quoted text
> me so far. > > -Martin
-- Your bugs , they are afraid of me.
CC: randomcoder1 [...] gmail.com
Subject: Re: [rt.cpan.org #46575] pretty-printing polynomials
Date: Mon, 07 Sep 2009 10:35:39 +1000
To: bug-Math-Polynomial [...] rt.cpan.org
From: Kevin Ryde <user42 [...] zip.com.au>
"Martin Becker via RT" <bug-Math-Polynomial@rt.cpan.org> writes: Show quoted text
> > as_tree.
Sounds both a bit too general and a bit too specific at the same time, if that's not a contradiction :). But inter-operation with Math::Symbolic sounds good. I don't know much about it, perhaps its what I should be using for the final expressions I was fiddling with, especially since I end up being in two variables. Of course for inter-operation there's always a choice which module to have the conversion, whether Math::Polynomial spits out a symbolic, or Math::Symbolic can take in a poly. If Math::Symbolic is biggish anyway you'd be tempted to put code there ...
Version 1.003 of Math::Polynomial adds two methods as_horner_tree and as_power_sum_tree to the conversions toolbox. Both can be used to generate operand trees as well as plain strings. Examples are documented. Thanks for the discussion. I consider this wishlist issue resolved. -Martin