From 5a8b8e3c4d882249db35b679ce3144a59a7012e8 Mon Sep 17 00:00:00 2001 From: Chris Dams Date: Tue, 14 Feb 2006 19:40:06 +0000 Subject: [PATCH] Fixed problems on 64-bit machines and introduced has_options::algebraic. --- check/exam_misc.cpp | 32 ++++++++++++++++---- configure.ac | 8 +++-- doc/tutorial/ginac.texi | 66 ++++++++++------------------------------- ginac/basic.cpp | 6 ++-- ginac/basic.h | 2 +- ginac/constant.cpp | 2 +- ginac/ex.h | 6 ++-- ginac/expairseq.cpp | 2 +- ginac/flags.h | 8 +++++ ginac/idx.cpp | 2 +- ginac/mul.cpp | 16 ++++++++++ ginac/mul.h | 1 + ginac/numeric.cpp | 2 +- ginac/numeric.h | 2 +- ginac/power.cpp | 24 +++++++++++++++ ginac/power.h | 1 + ginac/relational.cpp | 2 +- ginac/structure.h | 2 +- ginac/symbol.cpp | 2 +- ginac/utils.h | 12 +++++++- ginac/wildcard.cpp | 2 +- 21 files changed, 125 insertions(+), 75 deletions(-) diff --git a/check/exam_misc.cpp b/check/exam_misc.cpp index 12500524..55462c84 100644 --- a/check/exam_misc.cpp +++ b/check/exam_misc.cpp @@ -249,18 +249,40 @@ static unsigned exam_subs_algebraic() unsigned result = 0; symbol x("x"), y("y"); - ex e = ex(x*x*x*y*y).subs(x*y==2, subs_options::subs_algebraic); + ex e = ex(x*x*x*y*y).subs(x*y==2, subs_options::algebraic); if (e != 4*x) { - clog << "(x^3*y^2).subs(x*y==2,subs_options::subs_algebraic) erroneously returned " << e << endl; + clog << "(x^3*y^2).subs(x*y==2,subs_options::algebraic) erroneously returned " << e << endl; ++result; } - e = ex(x*x*x*x*x).subs(x*x==y, subs_options::subs_algebraic); + e = ex(x*x*x*x*x).subs(x*x==y, subs_options::algebraic); if (e != y*y*x) { - clog << "x^5.subs(x^2==y,subs_options::subs_algebraic) erroneously returned " << e << endl; + clog << "x^5.subs(x^2==y,subs_options::algebraic) erroneously returned " << e << endl; ++result; } - + + e=x*x*y; + if (!e.has(x*y, has_options::algebraic)) + { clog << "(x^2*y).has(x*y, has_options::algebraic) erroneously returned false." << endl; + ++result; + } + + if (e.has(x*y*y, has_options::algebraic)) + { clog << "(x^2*y).has(x*y*y, has_options::algebraic) erroneously returned true." << endl; + ++result; + } + + e=x*x*x*y; + if (!e.has(x*x, has_options::algebraic)) + { clog << "(x^3*y).has(x*x, has_options::algebraic) erroneously returned false." << endl; + ++result; + } + + if (e.has(y*y, has_options::algebraic)) + { clog << "(x^3*y).has(y*y, has_options::algebraic) erroneously returned true." << endl; + ++result; + } + return result; } diff --git a/configure.ac b/configure.ac index 47dcfdde..c9960d7c 100644 --- a/configure.ac +++ b/configure.ac @@ -73,9 +73,11 @@ AC_PROG_YACC dnl Check for data types which are needed by the hash function dnl (golden_ratio_hash). -AC_CHECK_SIZEOF(long, 4) -AC_CHECK_SIZEOF(long long, 8) -AC_CHECK_SIZEOF(long double, 12) +AC_CHECK_SIZEOF(int) +AC_CHECK_SIZEOF(long) +AC_CHECK_SIZEOF(long long) +AC_CHECK_SIZEOF(long double) +AC_CHECK_SIZEOF(void *) dnl Switch to C++ language mode for the following libraries and headers. AC_LANG([C++]) diff --git a/doc/tutorial/ginac.texi b/doc/tutorial/ginac.texi index 92fb7d14..ad48666c 100644 --- a/doc/tutorial/ginac.texi +++ b/doc/tutorial/ginac.texi @@ -4592,56 +4592,22 @@ The last example would be written in C++ in this way: @} @end example -@subsection Algebraic substitutions -Supplying the @code{subs_options::algebraic} option to @code{subs()} -enables smarter, algebraic substitutions in products and powers. If you want -to substitute some factors of a product, you only need to list these factors -in your pattern. Furthermore, if an (integer) power of some expression occurs -in your pattern and in the expression that you want the substitution to occur -in, it can be substituted as many times as possible, without getting negative -powers. - -An example clarifies it all (hopefully): - -@example -cout << (a*a*a*a+b*b*b*b+pow(x+y,4)).subs(wild()*wild()==pow(wild(),3), - subs_options::algebraic) << endl; -// --> (y+x)^6+b^6+a^6 - -cout << ((a+b+c)*(a+b+c)).subs(a+b==x,subs_options::algebraic) << endl; -// --> (c+b+a)^2 -// Powers and products are smart, but addition is just the same. - -cout << ((a+b+c)*(a+b+c)).subs(a+b+wild()==x+wild(), subs_options::algebraic) - << endl; -// --> (x+c)^2 -// As I said: addition is just the same. - -cout << (pow(a,5)*pow(b,7)+2*b).subs(b*b*a==x,subs_options::algebraic) << endl; -// --> x^3*b*a^2+2*b - -cout << (pow(a,-5)*pow(b,-7)+2*b).subs(1/(b*b*a)==x,subs_options::algebraic) - << endl; -// --> 2*b+x^3*b^(-1)*a^(-2) - -cout << (4*x*x*x-2*x*x+5*x-1).subs(x==a,subs_options::algebraic) << endl; -// --> -1-2*a^2+4*a^3+5*a - -cout << (4*x*x*x-2*x*x+5*x-1).subs(pow(x,wild())==pow(a,wild()), - subs_options::algebraic) << endl; -// --> -1+5*x+4*x^3-2*x^2 -// You should not really need this kind of patterns very often now. -// But perhaps this it's-not-a-bug-it's-a-feature (c/sh)ould still change. - -cout << ex(sin(1+sin(x))).subs(sin(wild())==cos(wild()), - subs_options::algebraic) << endl; -// --> cos(1+cos(x)) - -cout << expand((a*sin(x+y)*sin(x+y)+a*cos(x+y)*cos(x+y)+b) - .subs((pow(cos(wild()),2)==1-pow(sin(wild()),2)), - subs_options::algebraic)) << endl; -// --> b+a -@end example +@subsection The option algebraic +Both @code{has()} and @code{subs()} take an optional argument to pass them +extra options. This section describes what happens if you give the former +the option @code{has_options::algebraic} or the latter +@code{subs:options::algebraic}. In that case the matching condition for +powers and multiplications is changed in such a way that they become +more intuitive. Intuition says that @code{x*y} is a part of @code{x*y*z}. +If you use these options you will find that +@code{(x*y*z).has(x*y, has_options::algebraic)} indeed returns true. +Besides matching some of the factors of a product also powers match as +often as is possible without getting negative exponents. For example +@code{(x^5*y^2*z).subs(x^2*y^2==c, subs_options::algebraic)} will return +@code{x*c^2*z}. This also works with negative powers: +@code{(x^(-3)*y^(-2)*z).subs(1/(x*y)==c, subs_options::algebraic)} will +return @code{x^(-1)*c^2*z}. Note that this only works for multiplications +and not for locating @code{x+y} within @code{x+y+z}. @node Applying a Function on Subexpressions, Visitors and Tree Traversal, Pattern Matching and Advanced Substitutions, Methods and Functions diff --git a/ginac/basic.cpp b/ginac/basic.cpp index b4e38614..38219dcd 100644 --- a/ginac/basic.cpp +++ b/ginac/basic.cpp @@ -286,13 +286,13 @@ ex & basic::operator[](size_t i) * the pattern itself or one of the children 'has' it. As a consequence * (according to the definition of children) given e=x+y+z, e.has(x) is true * but e.has(x+y) is false. */ -bool basic::has(const ex & pattern) const +bool basic::has(const ex & pattern, unsigned options) const { lst repl_lst; if (match(pattern, repl_lst)) return true; for (size_t i=0; iop(i).gethash(); diff --git a/ginac/basic.h b/ginac/basic.h index b2dc0ade..9b226c37 100644 --- a/ginac/basic.h +++ b/ginac/basic.h @@ -160,7 +160,7 @@ public: virtual ex & operator[](size_t i); // pattern matching - virtual bool has(const ex & other) const; + virtual bool has(const ex & other, unsigned options = 0) const; virtual bool match(const ex & pattern, lst & repl_lst) const; protected: virtual bool match_same_type(const basic & other) const; diff --git a/ginac/constant.cpp b/ginac/constant.cpp index 35f5ea02..86fb55b7 100644 --- a/ginac/constant.cpp +++ b/ginac/constant.cpp @@ -177,7 +177,7 @@ bool constant::is_equal_same_type(const basic & other) const unsigned constant::calchash() const { - hashvalue = golden_ratio_hash((unsigned)tinfo() ^ serial); + hashvalue = golden_ratio_hash((p_int)tinfo() ^ serial); setflag(status_flags::hash_calculated); diff --git a/ginac/ex.h b/ginac/ex.h index 82ac4ab5..a2cc34eb 100644 --- a/ginac/ex.h +++ b/ginac/ex.h @@ -138,7 +138,7 @@ public: ex conjugate() const { return bp->conjugate(); } // pattern matching - bool has(const ex & pattern) const { return bp->has(pattern); } + bool has(const ex & pattern, unsigned options = 0) const { return bp->has(pattern, options); } bool find(const ex & pattern, lst & found) const; bool match(const ex & pattern) const; bool match(const ex & pattern, lst & repl_lst) const { return bp->match(pattern, repl_lst); } @@ -684,8 +684,8 @@ inline ex expand(const ex & thisex, unsigned options = 0) inline ex conjugate(const ex & thisex) { return thisex.conjugate(); } -inline bool has(const ex & thisex, const ex & pattern) -{ return thisex.has(pattern); } +inline bool has(const ex & thisex, const ex & pattern, unsigned options = 0) +{ return thisex.has(pattern, options); } inline bool find(const ex & thisex, const ex & pattern, lst & found) { return thisex.find(pattern, found); } diff --git a/ginac/expairseq.cpp b/ginac/expairseq.cpp index bd1604e1..458b440d 100644 --- a/ginac/expairseq.cpp +++ b/ginac/expairseq.cpp @@ -571,7 +571,7 @@ unsigned expairseq::return_type() const unsigned expairseq::calchash() const { - unsigned v = golden_ratio_hash((unsigned)this->tinfo()); + unsigned v = golden_ratio_hash((p_int)this->tinfo()); epvector::const_iterator i = seq.begin(); const epvector::const_iterator end = seq.end(); while (i != end) { diff --git a/ginac/flags.h b/ginac/flags.h index 7c51b75d..8c4bdfb2 100644 --- a/ginac/flags.h +++ b/ginac/flags.h @@ -34,6 +34,14 @@ public: }; }; +/** Flags to control the behavior of has(). */ +class has_options { +public: + enum { + algebraic = 0x0001, ///< enable algebraic matching + }; +}; + /** Flags to control the behavior of subs(). */ class subs_options { public: diff --git a/ginac/idx.cpp b/ginac/idx.cpp index 9211294b..e531f0f3 100644 --- a/ginac/idx.cpp +++ b/ginac/idx.cpp @@ -338,7 +338,7 @@ unsigned idx::calchash() const // hash keys. That is, the hash values must not depend on the index // dimensions or other attributes (variance etc.). // The compare_same_type() methods will take care of the rest. - unsigned v = golden_ratio_hash((unsigned)tinfo()); + unsigned v = golden_ratio_hash((p_int)tinfo()); v = rotate_left(v); v ^= value.gethash(); diff --git a/ginac/mul.cpp b/ginac/mul.cpp index 96294789..3385bcae 100644 --- a/ginac/mul.cpp +++ b/ginac/mul.cpp @@ -597,6 +597,22 @@ bool algebraic_match_mul_with_mul(const mul &e, const ex &pat, lst &repls, return false; } +bool mul::has(const ex & pattern, unsigned options) const +{ + if(!(options&has_options::algebraic)) + return basic::has(pattern,options); + if(is_a(pattern)) { + lst repls; + int nummatches = std::numeric_limits::max(); + std::vector subsed(seq.size(), false); + std::vector matched(seq.size(), false); + if(algebraic_match_mul_with_mul(*this, pattern, repls, 0, nummatches, + subsed, matched)) + return true; + } + return basic::has(pattern, options); +} + ex mul::algebraic_subs_mul(const exmap & m, unsigned options) const { std::vector subsed(seq.size(), false); diff --git a/ginac/mul.h b/ginac/mul.h index afb9abc8..e9b14058 100644 --- a/ginac/mul.h +++ b/ginac/mul.h @@ -52,6 +52,7 @@ public: int degree(const ex & s) const; int ldegree(const ex & s) const; ex coeff(const ex & s, int n = 1) const; + bool has(const ex & other, unsigned options = 0) const; ex eval(int level=0) const; ex evalf(int level=0) const; ex evalm() const; diff --git a/ginac/numeric.cpp b/ginac/numeric.cpp index 9687f23e..df525d60 100644 --- a/ginac/numeric.cpp +++ b/ginac/numeric.cpp @@ -624,7 +624,7 @@ ex numeric::coeff(const ex & s, int n) const * results: (2+I).has(-2) -> true. But this is consistent, since we also * would like to have (-2+I).has(2) -> true and we want to think about the * sign as a multiplicative factor. */ -bool numeric::has(const ex &other) const +bool numeric::has(const ex &other, unsigned options) const { if (!is_exactly_a(other)) return false; diff --git a/ginac/numeric.h b/ginac/numeric.h index e6596bdf..0456b81d 100644 --- a/ginac/numeric.h +++ b/ginac/numeric.h @@ -108,7 +108,7 @@ public: int degree(const ex & s) const; int ldegree(const ex & s) const; ex coeff(const ex & s, int n = 1) const; - bool has(const ex &other) const; + bool has(const ex &other, unsigned options = 0) const; ex eval(int level = 0) const; ex evalf(int level = 0) const; ex subs(const exmap & m, unsigned options = 0) const { return subs_one_level(m, options); } // overwrites basic::subs() for performance reasons diff --git a/ginac/power.cpp b/ginac/power.cpp index 60d138bd..69e3dd7f 100644 --- a/ginac/power.cpp +++ b/ginac/power.cpp @@ -541,6 +541,30 @@ ex power::evalm() const return (new power(ebasis, eexponent))->setflag(status_flags::dynallocated); } +bool power::has(const ex & other, unsigned options) const +{ + if (!(options & has_options::algebraic)) + return basic::has(other, options); + if (!is_a(other)) + return basic::has(other, options); + if (!exponent.info(info_flags::integer) + || !other.op(1).info(info_flags::integer)) + return basic::has(other, options); + if (exponent.info(info_flags::posint) + && other.op(1).info(info_flags::posint) + && ex_to(exponent).to_int() + > ex_to(other.op(1)).to_int() + && basis.match(other.op(0))) + return true; + if (exponent.info(info_flags::negint) + && other.op(1).info(info_flags::negint) + && ex_to(exponent).to_int() + < ex_to(other.op(1)).to_int() + && basis.match(other.op(0))) + return true; + return basic::has(other, options); +} + // from mul.cpp extern bool tryfactsubs(const ex &, const ex &, int &, lst &); diff --git a/ginac/power.h b/ginac/power.h index 0fe37d4c..13230e9c 100644 --- a/ginac/power.h +++ b/ginac/power.h @@ -62,6 +62,7 @@ public: ex evalm() const; ex series(const relational & s, int order, unsigned options = 0) const; ex subs(const exmap & m, unsigned options = 0) const; + bool has(const ex & other, unsigned options = 0) const; ex normal(exmap & repl, exmap & rev_lookup, int level = 0) const; ex to_rational(exmap & repl) const; ex to_polynomial(exmap & repl) const; diff --git a/ginac/relational.cpp b/ginac/relational.cpp index 63dd2459..0f94f8cf 100644 --- a/ginac/relational.cpp +++ b/ginac/relational.cpp @@ -258,7 +258,7 @@ const basic* relational::return_type_tinfo() const unsigned relational::calchash() const { - unsigned v = golden_ratio_hash((unsigned)tinfo()); + unsigned v = golden_ratio_hash((p_int)tinfo()); unsigned lhash = lh.gethash(); unsigned rhash = rh.gethash(); diff --git a/ginac/structure.h b/ginac/structure.h index 1ed46cb8..33d8ee4c 100644 --- a/ginac/structure.h +++ b/ginac/structure.h @@ -155,7 +155,7 @@ public: ex & operator[](size_t i) { return inherited::operator[](i); } // pattern matching - bool has(const ex & other) const { return inherited::has(other); } + bool has(const ex & other, unsigned options = 0) const { return inherited::has(other, options); } bool match(const ex & pattern, lst & repl_lst) const { return inherited::match(pattern, repl_lst); } protected: bool match_same_type(const basic & other) const { return true; } diff --git a/ginac/symbol.cpp b/ginac/symbol.cpp index 6c0c6960..2d680c43 100644 --- a/ginac/symbol.cpp +++ b/ginac/symbol.cpp @@ -257,7 +257,7 @@ bool symbol::is_equal_same_type(const basic & other) const unsigned symbol::calchash() const { - hashvalue = golden_ratio_hash((unsigned)tinfo() ^ serial); + hashvalue = golden_ratio_hash((p_int)tinfo() ^ serial); setflag(status_flags::hash_calculated); return hashvalue; } diff --git a/ginac/utils.h b/ginac/utils.h index 6a8739cf..e93f9b50 100644 --- a/ginac/utils.h +++ b/ginac/utils.h @@ -64,8 +64,18 @@ inline unsigned rotate_left(unsigned n) return (n & 0x80000000U) ? (n << 1 | 0x00000001U) : (n << 1); } +#if SIZEOF_VOID_P == SIZEOF_INT +typedef unsigned int p_int; +#elif SIZEOF_VOID_P == SIZEOF_LONG +typedef unsigned long p_int; +#elif SIZEOF_VOID_P == SIZEOF_LONG_LONG +typedef unsigned long long p_int; +#else +typedef unsigned long p_int; +#endif + /** Truncated multiplication with golden ratio, for computing hash values. */ -inline unsigned golden_ratio_hash(unsigned n) +inline unsigned golden_ratio_hash(p_int n) { // This function works much better when fast arithmetic with at // least 64 significant bits is available. diff --git a/ginac/wildcard.cpp b/ginac/wildcard.cpp index 84a67317..62a4eb50 100644 --- a/ginac/wildcard.cpp +++ b/ginac/wildcard.cpp @@ -106,7 +106,7 @@ unsigned wildcard::calchash() const // this is where the schoolbook method // (golden_ratio_hash(tinfo()) ^ label) // is not good enough yet... - hashvalue = golden_ratio_hash(golden_ratio_hash((unsigned)tinfo()) ^ label); + hashvalue = golden_ratio_hash(golden_ratio_hash((p_int)tinfo()) ^ label); setflag(status_flags::hash_calculated); return hashvalue; } -- 2.45.0