Fixed problems on 64-bit machines and introduced has_options::algebraic.
authorChris Dams <Chris.Dams@mi.infn.it>
Tue, 14 Feb 2006 19:40:06 +0000 (19:40 +0000)
committerChris Dams <Chris.Dams@mi.infn.it>
Tue, 14 Feb 2006 19:40:06 +0000 (19:40 +0000)
21 files changed:
check/exam_misc.cpp
configure.ac
doc/tutorial/ginac.texi
ginac/basic.cpp
ginac/basic.h
ginac/constant.cpp
ginac/ex.h
ginac/expairseq.cpp
ginac/flags.h
ginac/idx.cpp
ginac/mul.cpp
ginac/mul.h
ginac/numeric.cpp
ginac/numeric.h
ginac/power.cpp
ginac/power.h
ginac/relational.cpp
ginac/structure.h
ginac/symbol.cpp
ginac/utils.h
ginac/wildcard.cpp

index 1250052..55462c8 100644 (file)
@@ -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;
 }
 
index 47dcfdd..c9960d7 100644 (file)
@@ -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++])
index 92fb7d1..ad48666 100644 (file)
@@ -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
index b4e3861..38219dc 100644 (file)
@@ -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; i<nops(); i++)
-               if (op(i).has(pattern))
+               if (op(i).has(pattern, options))
                        return true;
        
        return false;
@@ -788,7 +788,7 @@ const basic* basic::return_type_tinfo() const
  *  would all end up with the same hashvalue. */
 unsigned basic::calchash() const
 {
-       unsigned v = golden_ratio_hash((unsigned)tinfo());
+       unsigned v = golden_ratio_hash((p_int)tinfo());
        for (size_t i=0; i<nops(); i++) {
                v = rotate_left(v);
                v ^= this->op(i).gethash();
index b2dc0ad..9b226c3 100644 (file)
@@ -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;
index 35f5ea0..86fb55b 100644 (file)
@@ -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);
 
index 82ac4ab..a2cc34e 100644 (file)
@@ -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); }
index bd1604e..458b440 100644 (file)
@@ -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) {
index 7c51b75..8c4bdfb 100644 (file)
@@ -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:
index 9211294..e531f0f 100644 (file)
@@ -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();
 
index 9629478..3385bca 100644 (file)
@@ -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<mul>(pattern)) {
+               lst repls;
+               int nummatches = std::numeric_limits<int>::max();
+               std::vector<bool> subsed(seq.size(), false);
+               std::vector<bool> 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<bool> subsed(seq.size(), false);
index afb9abc..e9b1405 100644 (file)
@@ -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;
index 9687f23..df525d6 100644 (file)
@@ -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<numeric>(other))
                return false;
index e6596bd..0456b81 100644 (file)
@@ -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
index 60d138b..69e3dd7 100644 (file)
@@ -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<power>(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<numeric>(exponent).to_int()
+                                       > ex_to<numeric>(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<numeric>(exponent).to_int()
+                                       < ex_to<numeric>(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 &);
 
index 0fe37d4..13230e9 100644 (file)
@@ -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;
index 63dd245..0f94f8c 100644 (file)
@@ -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();
 
index 1ed46cb..33d8ee4 100644 (file)
@@ -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; }
index 6c0c696..2d680c4 100644 (file)
@@ -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;
 }
index 6a8739c..e93f9b5 100644 (file)
@@ -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.
index 84a6731..62a4eb5 100644 (file)
@@ -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;
 }