Dear all, this message is a first of a small series where we try to summarize our difficulties with GiNaC and its (lack of) documentation. As a general remark, several concepts are defined only through examples whereas formal definitions would help greatly. In this message we concentrate on one concept that is central to our application: the concept of "polynomial". Here are our sources of information: 1) The tutorial: a bunch of examples are presented that, however do not clarify the general idea. 2) The method `info(info_flags::polynomial)' should constitute, we used to believe, the very formal specification of the notion of "being a polynomial". 3) The message by Christian Bauer (March 7th, 2002, see http://www.ginac.de/lists/ginac-list/msg00232.html): "But this is the intended behavior: If e is of the form e = sum(i=n1..n2, a_i * x^i) with n1, n2 integer and expressions a_i that satisfy has(a_i, x) == false, then degree(e, x) and ldegree(e, x) are well defined and accurate. I think this should even cover cases like degree(sin(y)^3-sin(y),sin(y)) which is guaranteed to return 3." The problem is that, while 1 is inconclusive, 2 and 3 (with the correction replacing "integer" by "nonnegative integer") conflict with each other. Let us consider the expression e = sqrt(2)*x. Since, clearly, has(sqrt(2), x) == false, `e' is a polynomial for 3. But, since e.info(info_flags::polynomial) == false, `e' is not a polynomial according to 2. The point here is to decide _exactly_ for which class of expressions are the functions degree(), ldegree(), coeff(), lcoeff(), tcoeff(), expand(), collect(), quo(), rem(), prem(), gcd(), lcm(), sqrfree() and so forth guaranteed to work. All the best Roberto Bagnara Alessandro Zaccagnini Enea Zaffanella Tatiana Zolo /***************************************************************************/ #include <ginac/ginac.h> #include <iostream> using namespace GiNaC; using namespace std; int main() { symbol x("x"); ex coeff = sqrt(ex(2)); ex e = coeff*x; cout << (e.info(info_flags::polynomial) ? "true" : "false") << endl; cout << (!has(coeff, x) ? "true" : "false") << endl; return 0; } /***************************************************************************/ -- Prof. Roberto Bagnara Computer Science Group Department of Mathematics, University of Parma, Italy http://www.cs.unipr.it/~bagnara/ mailto:bagnara@cs.unipr.it
Hi! On Wed, Oct 09, 2002 at 04:50:55PM +0200, Roberto Bagnara wrote:
As a general remark, several concepts are defined only through examples whereas formal definitions would help greatly.
Agreed.
2) The method `info(info_flags::polynomial)' should constitute, we used to believe, the very formal specification of the notion of "being a polynomial".
Yes, that's what info_flags::polynomial was intended for.
3) The message by Christian Bauer (March 7th, 2002, see http://www.ginac.de/lists/ginac-list/msg00232.html): [...] degree(sin(y)^3-sin(y),sin(y)) which is guaranteed to return 3."
The problem is that, while 1 is inconclusive, 2 and 3 (with the correction replacing "integer" by "nonnegative integer") conflict with each other.
3) wasn't intended to define "polynomial". degree() works on a class of expressions that is a superset of the class of polynomials.
e = sqrt(2)*x e.info(info_flags::polynomial) == false
That's a case where the GiNaC definition of a polynomial clashes with the "intuitive" one. info() should probably return 'true' here, because sqrt(2) is clearly a number. But so is zeta(3), and I'm not sure how to handle this in a way that is general enough.
The point here is to decide _exactly_ for which class of expressions are the functions degree(), ldegree(), coeff(), lcoeff(), tcoeff(), expand(), collect(), quo(), rem(), prem(), gcd(), lcm(), sqrfree() and so forth guaranteed to work.
An exact specification of the maximal classes of expressions that these functions can operate on and the exact results they produce would require more work than I'm willing to invest (that's partly because GiNaC was designed for a bunch of physicists to "get some work done", not as a collection of rigorously defined functions). I'd be more comfortable if you could propose a set of specifications for these functions (for the cases you need), where I can say "Yes, this will work in all future versions of GiNaC", even if these are not the 'maximal' specifications. Bye, Christian -- / Coding on PowerPC and proud of it \/ http://www.uni-mainz.de/~bauec002/
Christian Bauer wrote:
The point here is to decide _exactly_ for which class of expressions are the functions degree(), ldegree(), coeff(), lcoeff(), tcoeff(), expand(), collect(), quo(), rem(), prem(), gcd(), lcm(), sqrfree() and so forth guaranteed to work.
An exact specification of the maximal classes of expressions that these functions can operate on and the exact results they produce would require more work than I'm willing to invest (that's partly because GiNaC was designed for a bunch of physicists to "get some work done", not as a collection of rigorously defined functions).
I'd be more comfortable if you could propose a set of specifications for these functions (for the cases you need), where I can say "Yes, this will work in all future versions of GiNaC", even if these are not the 'maximal' specifications.
Here is a formal definition of what is, for our application, a polynomial in `x'. The first (auxiliary) function defines scalars for `x', the other function defines the real thing. Notice that this is written referring to the layer of software we have put on top of GiNaC, but the concepts should be easily recognizable anyway. //! \brief //! Returns <CODE>true</CODE> if \p e is a scalar rapresentation for \p x; //! returns <CODE>false</CODE> otherwise. /*! This function realizes the definition of <EM>scalar representation for \f$ x \f$</EM>, where \f$ x \f$ is any symbol. This is more briefly written <EM>scalar</EM> and defined inductively as follows: - every number is a scalar; - every symbolic constant is a scalar; - every parameter different from \f$ x \f$ is a scalar; - if \f$ f \f$ is any unary function and \f$ x \f$ is a scalar representation, then \f$ f(x) \f$ is a scalar; - if \f$ a \f$ and \f$ b \f$ are scalars then \f$ a+b \f$, \f$ a*b \f$, and \f$ a^b \f$ are scalars. */ bool is_scalar_representation(const Expr& e, const Symbol& x) { if (e.is_a_number()) return true; else if (e.is_a_constant()) return true; else if (e.is_a_symbol() && !e.is_equal(x)) return true; else if (e.is_a_power()) return is_scalar_representation(e.op(0), x) && is_scalar_representation(e.op(1), x); else if (e.is_a_function()) return is_scalar_representation(e.op(0), x); else if (e.is_a_add() || e.is_a_mul()) { for (unsigned i = e.nops(); i-- > 0; ) if (!is_scalar_representation(e.op(i), x)) return false; return true; } return false; } //! \brief //! Returns <CODE>true</CODE> if \p e is a polynomial in \p x; //! returns <CODE>false</CODE> otherwise. /*! This function realizes the definition of <EM>polynomial in \f$ x \f$</EM>, where \f$ x \f$ is any symbol. This is more briefly written <EM>polynomial</EM> and defined inductively as follows: - every scalar representation for \f$ x \f$ is a polynomial; - \f$ x \f$ is a polynomial; - if \f$ a \f$ is a polynomial in \f$ x \f$ and \f$ b \f$ is a positive integer, then \f$ a^b \f$ is a polynomial; - if \f$ a \f$ and \f$ b \f$ are polynomials then \f$ a + b \f$ and \f$ a * b \f$ are polynomials. */ bool is_polynomial(const Expr& e, const Symbol& x) { if (is_scalar_representation(e, x)) return true; else if (e.is_equal(x)) return true; else if (e.is_a_power()) { if (is_polynomial(e.op(0), x)) if (e.op(1).is_a_number()) { Number exponent = e.op(1).ex_to_number(); if (exponent.is_positive_integer()) return true; } } else if (e.is_a_add() || e.is_a_mul()) { for (unsigned i = e.nops(); i-- > 0; ) if (!is_polynomial(e.op(i), x)) return false; return true; } return false; } -- Prof. Roberto Bagnara Computer Science Group Department of Mathematics, University of Parma, Italy http://www.cs.unipr.it/~bagnara/ mailto:bagnara@cs.unipr.it
On Wed, 9 Oct 2002, Christian Bauer wrote: [...]
e = sqrt(2)*x e.info(info_flags::polynomial) == false
That's a case where the GiNaC definition of a polynomial clashes with the "intuitive" one. info() should probably return 'true' here, because sqrt(2) is clearly a number. But so is zeta(3), and I'm not sure how to handle this in a way that is general enough.
I don't see a difference between sqrt(2) and zeta(3) apart from the irrelevant fact that zeta(3) is transcendental while sqrt(2) is just irrational. The point here was that Z[x,y,z,...] and Q[x,y,z,...] ought to be classified as polynomials while more general fields are something different. This is so because as soon as you start nesting roots it is not at all obvious how to obtain a canonical form -- definitely "expanding" is not enough. For more general functions (like zeta(2*n+1)) it becomes even less obvious. I'm not entirely sure but methinks a valid definition would be this one: A polynomial is an object that has a unique canonical form such that given two such objects their equality is guaranteed to be unambigously determined using `expand' on both objects. I think this is what I was having in mind when I implemented info(info_flags::polynomial) long ago. Does this make sense? Regards -richy. -- Richard B. Kreckel <Richard.Kreckel@GiNaC.DE> <http://www.ginac.de/~kreckel/>
participants (3)
-
Christian Bauer
-
Richard B. Kreckel
-
Roberto Bagnara