X-Git-Url: https://www.ginac.de/ginac.git//ginac.git?p=ginac.git;a=blobdiff_plain;f=ginac%2Fmul.cpp;h=2c8456510a44d35201f5659dec50f27f32206e02;hp=bf5e70dff0d77d4bc5687907cae8974ddee24d87;hb=5ef801553eb39aed7bd2df9dd1aff9d752c3ea9d;hpb=6b3768e8c544739ae53321539cb4d1e3112ded1b diff --git a/ginac/mul.cpp b/ginac/mul.cpp index bf5e70df..2c845651 100644 --- a/ginac/mul.cpp +++ b/ginac/mul.cpp @@ -2,55 +2,49 @@ * * Implementation of GiNaC's products of expressions. */ +/* + * GiNaC Copyright (C) 1999-2003 Johannes Gutenberg University Mainz, Germany + * + * This program 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 2 of the License, or + * (at your option) any later version. + * + * This program 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 this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include #include #include +#include -#include "ginac.h" +#include "mul.h" +#include "add.h" +#include "power.h" +#include "operators.h" +#include "matrix.h" +#include "lst.h" +#include "archive.h" +#include "utils.h" + +namespace GiNaC { + +GINAC_IMPLEMENT_REGISTERED_CLASS(mul, expairseq) ////////// -// default constructor, destructor, copy constructor assignment operator and helpers +// default constructor ////////// -// public - mul::mul() { - debugmsg("mul default constructor",LOGLEVEL_CONSTRUCT); - tinfo_key = TINFO_MUL; -} - -mul::~mul() -{ - debugmsg("mul destructor",LOGLEVEL_DESTRUCT); - destroy(0); -} - -mul::mul(mul const & other) -{ - debugmsg("mul copy constructor",LOGLEVEL_CONSTRUCT); - copy(other); -} - -mul const & mul::operator=(mul const & other) -{ - debugmsg("mul operator=",LOGLEVEL_ASSIGNMENT); - if (this != &other) { - destroy(1); - copy(other); - } - return *this; -} - -// protected - -void mul::copy(mul const & other) -{ - expairseq::copy(other); -} - -void mul::destroy(bool call_parent) -{ - if (call_parent) expairseq::destroy(call_parent); + tinfo_key = TINFO_mul; } ////////// @@ -59,877 +53,883 @@ void mul::destroy(bool call_parent) // public -mul::mul(ex const & lh, ex const & rh) +mul::mul(const ex & lh, const ex & rh) { - debugmsg("mul constructor from ex,ex",LOGLEVEL_CONSTRUCT); - tinfo_key = TINFO_MUL; - overall_coeff=exONE(); - construct_from_2_ex(lh,rh); - ASSERT(is_canonical()); + tinfo_key = TINFO_mul; + overall_coeff = _ex1; + construct_from_2_ex(lh,rh); + GINAC_ASSERT(is_canonical()); } -mul::mul(exvector const & v) +mul::mul(const exvector & v) { - debugmsg("mul constructor from exvector",LOGLEVEL_CONSTRUCT); - tinfo_key = TINFO_MUL; - overall_coeff=exONE(); - construct_from_exvector(v); - ASSERT(is_canonical()); + tinfo_key = TINFO_mul; + overall_coeff = _ex1; + construct_from_exvector(v); + GINAC_ASSERT(is_canonical()); } -/* -mul::mul(epvector const & v, bool do_not_canonicalize) +mul::mul(const epvector & v) { - debugmsg("mul constructor from epvector,bool",LOGLEVEL_CONSTRUCT); - tinfo_key = TINFO_MUL; - if (do_not_canonicalize) { - seq=v; -#ifdef EXPAIRSEQ_USE_HASHTAB - combine_same_terms(); // to build hashtab -#endif // def EXPAIRSEQ_USE_HASHTAB - } else { - construct_from_epvector(v); - } - ASSERT(is_canonical()); + tinfo_key = TINFO_mul; + overall_coeff = _ex1; + construct_from_epvector(v); + GINAC_ASSERT(is_canonical()); } -*/ -mul::mul(epvector const & v) +mul::mul(const epvector & v, const ex & oc) { - debugmsg("mul constructor from epvector",LOGLEVEL_CONSTRUCT); - tinfo_key = TINFO_MUL; - overall_coeff=exONE(); - construct_from_epvector(v); - ASSERT(is_canonical()); + tinfo_key = TINFO_mul; + overall_coeff = oc; + construct_from_epvector(v); + GINAC_ASSERT(is_canonical()); } -mul::mul(epvector const & v, ex const & oc) +mul::mul(epvector * vp, const ex & oc) { - debugmsg("mul constructor from epvector,ex",LOGLEVEL_CONSTRUCT); - tinfo_key = TINFO_MUL; - overall_coeff=oc; - construct_from_epvector(v); - ASSERT(is_canonical()); + tinfo_key = TINFO_mul; + GINAC_ASSERT(vp!=0); + overall_coeff = oc; + construct_from_epvector(*vp); + delete vp; + GINAC_ASSERT(is_canonical()); } -mul::mul(epvector * vp, ex const & oc) +mul::mul(const ex & lh, const ex & mh, const ex & rh) { - debugmsg("mul constructor from epvector *,ex",LOGLEVEL_CONSTRUCT); - tinfo_key = TINFO_MUL; - ASSERT(vp!=0); - overall_coeff=oc; - construct_from_epvector(*vp); - delete vp; - ASSERT(is_canonical()); + tinfo_key = TINFO_mul; + exvector factors; + factors.reserve(3); + factors.push_back(lh); + factors.push_back(mh); + factors.push_back(rh); + overall_coeff = _ex1; + construct_from_exvector(factors); + GINAC_ASSERT(is_canonical()); } -mul::mul(ex const & lh, ex const & mh, ex const & rh) -{ - debugmsg("mul constructor from ex,ex,ex",LOGLEVEL_CONSTRUCT); - tinfo_key = TINFO_MUL; - exvector factors; - factors.reserve(3); - factors.push_back(lh); - factors.push_back(mh); - factors.push_back(rh); - overall_coeff=exONE(); - construct_from_exvector(factors); - ASSERT(is_canonical()); -} +////////// +// archiving +////////// + +DEFAULT_ARCHIVING(mul) ////////// -// functions overriding virtual functions from bases classes +// functions overriding virtual functions from base classes ////////// // public - -basic * mul::duplicate() const -{ - debugmsg("mul duplicate",LOGLEVEL_ASSIGNMENT); - return new mul(*this); +void mul::print(const print_context & c, unsigned level) const +{ + if (is_a(c)) { + + inherited::print(c, level); + + } else if (is_a(c)) { + + if (precedence() <= level) + c.s << "("; + + if (!overall_coeff.is_equal(_ex1)) { + overall_coeff.print(c, precedence()); + c.s << "*"; + } + + // Print arguments, separated by "*" or "/" + epvector::const_iterator it = seq.begin(), itend = seq.end(); + while (it != itend) { + + // If the first argument is a negative integer power, it gets printed as "1.0/" + bool needclosingparenthesis = false; + if (it == seq.begin() && it->coeff.info(info_flags::negint)) { + if (is_a(c)) { + c.s << "recip("; + needclosingparenthesis = true; + } else + c.s << "1.0/"; + } + + // If the exponent is 1 or -1, it is left out + if (it->coeff.is_equal(_ex1) || it->coeff.is_equal(_ex_1)) + it->rest.print(c, precedence()); + else if (it->coeff.info(info_flags::negint)) + // Outer parens around ex needed for broken GCC parser: + (ex(power(it->rest, -ex_to(it->coeff)))).print(c, level); + else + // Outer parens around ex needed for broken GCC parser: + (ex(power(it->rest, ex_to(it->coeff)))).print(c, level); + + if (needclosingparenthesis) + c.s << ")"; + + // Separator is "/" for negative integer powers, "*" otherwise + ++it; + if (it != itend) { + if (it->coeff.info(info_flags::negint)) + c.s << "/"; + else + c.s << "*"; + } + } + + if (precedence() <= level) + c.s << ")"; + + } else if (is_a(c)) { + c.s << class_name() << '('; + op(0).print(c); + for (size_t i=1; i(c)) + c.s << "{("; + else + c.s << "("; + } + + // First print the overall numeric coefficient + const numeric &coeff = ex_to(overall_coeff); + if (coeff.csgn() == -1) + c.s << '-'; + if (!coeff.is_equal(_num1) && + !coeff.is_equal(_num_1)) { + if (coeff.is_rational()) { + if (coeff.is_negative()) + (-coeff).print(c); + else + coeff.print(c); + } else { + if (coeff.csgn() == -1) + (-coeff).print(c, precedence()); + else + coeff.print(c, precedence()); + } + if (is_a(c)) + c.s << ' '; + else + c.s << '*'; + } + + // Then proceed with the remaining factors + epvector::const_iterator it = seq.begin(), itend = seq.end(); + if (is_a(c)) { + + // Separate factors into those with negative numeric exponent + // and all others + exvector neg_powers, others; + while (it != itend) { + GINAC_ASSERT(is_exactly_a(it->coeff)); + if (ex_to(it->coeff).is_negative()) + neg_powers.push_back(recombine_pair_to_ex(expair(it->rest, -(it->coeff)))); + else + others.push_back(recombine_pair_to_ex(*it)); + ++it; + } + + if (!neg_powers.empty()) { + + // Factors with negative exponent are printed as a fraction + c.s << "\\frac{"; + mul(others).eval().print(c); + c.s << "}{"; + mul(neg_powers).eval().print(c); + c.s << "}"; + + } else { + + // All other factors are printed in the ordinary way + exvector::const_iterator vit = others.begin(), vitend = others.end(); + while (vit != vitend) { + c.s << ' '; + vit->print(c, precedence()); + ++vit; + } + } + + } else { + + bool first = true; + while (it != itend) { + if (!first) + c.s << '*'; + else + first = false; + recombine_pair_to_ex(*it).print(c, precedence()); + ++it; + } + } + + if (precedence() <= level) { + if (is_a(c)) + c.s << ")}"; + else + c.s << ")"; + } + } } bool mul::info(unsigned inf) const { - // TODO: optimize - if (inf==info_flags::polynomial || inf==info_flags::integer_polynomial || inf==info_flags::rational_polynomial || inf==info_flags::rational_function) { - for (epvector::const_iterator it=seq.begin(); it!=seq.end(); ++it) { - if (!(recombine_pair_to_ex(*it).info(inf))) - return false; - } - return true; - } else { - return expairseq::info(inf); - } -} - -typedef vector intvector; - -int mul::degree(symbol const & s) const -{ - int deg_sum=0; - for (epvector::const_iterator cit=seq.begin(); cit!=seq.end(); ++cit) { - deg_sum+=(*cit).rest.degree(s) * ex_to_numeric((*cit).coeff).to_int(); - } - return deg_sum; -} - -int mul::ldegree(symbol const & s) const -{ - int deg_sum=0; - for (epvector::const_iterator cit=seq.begin(); cit!=seq.end(); ++cit) { - deg_sum+=(*cit).rest.ldegree(s) * ex_to_numeric((*cit).coeff).to_int(); - } - return deg_sum; -} - -ex mul::coeff(symbol const & s, int const n) const -{ - exvector coeffseq; - coeffseq.reserve(seq.size()+1); - - if (n==0) { - // product of individual coeffs - // if a non-zero power of s is found, the resulting product will be 0 - epvector::const_iterator it=seq.begin(); - while (it!=seq.end()) { - coeffseq.push_back(recombine_pair_to_ex(*it).coeff(s,n)); - ++it; - } - coeffseq.push_back(overall_coeff); - return (new mul(coeffseq))->setflag(status_flags::dynallocated); - } - - epvector::const_iterator it=seq.begin(); - bool coeff_found=0; - while (it!=seq.end()) { - ex t=recombine_pair_to_ex(*it); - ex c=t.coeff(s,n); - if (!c.is_zero()) { - coeffseq.push_back(c); - coeff_found=1; - } else { - coeffseq.push_back(t); - } - ++it; - } - if (coeff_found) { - coeffseq.push_back(overall_coeff); - return (new mul(coeffseq))->setflag(status_flags::dynallocated); - } - - return exZERO(); -} - -/* -ex mul::eval(int level) const -{ - // simplifications: *(...,x,(c1,1),(c2,1)) -> *(...,x,(c1*c2,1)) (c1, c2 numeric(), move pairs to end first) - // *(...,x,1) -> *(...,x) - // *(...,x,0) -> 0 - // *(+(x,y,...),(c,1)) -> *(+(*(x,c),*(y,c),...)) (c numeric()) - // *(x) -> x - // *() -> 1 - - debugmsg("mul eval",LOGLEVEL_MEMBER_FUNCTION); - - if ((level==1)&&(flags & status_flags::evaluated)) { -#ifdef DOASSERT - for (epvector::const_iterator cit=seq.begin(); cit!=seq.end(); ++cit) { - ASSERT((!is_ex_exactly_of_type((*cit).rest,mul))|| - (!(ex_to_numeric((*cit).coeff).is_integer()))); - } - - // test if all numerics were moved to the end and - // all numerics with coeff 1 to the very end - if (seq.size()!=0) { - epvector::const_iterator cit=seq.end(); - bool all_coeff_1=true; - bool all_numeric=true; - do { - cit--; - if (is_ex_exactly_of_type((*cit).rest,numeric)) { - ASSERT(all_numeric); - if ((*cit).coeff.is_equal(exONE())) { - ASSERT(all_coeff_1); - } else { - all_coeff_1=false; - } - } else { - all_numeric=false; - } - } while (cit!=seq.begin()); - } -#endif // def DOASSERT - return *this; - } - - epvector newseq; - epvector::iterator it1,it2; - bool seq_copied=false; - - epvector * evaled_seqp=evalchildren(level); - if (evaled_seqp!=0) { - // do more evaluation later - return (new mul(evaled_seqp))->setflag(status_flags::dynallocated); - } - - // combine pairs with coeff 1 (all numerics should be at end, assert below) - if (seq.size()>1) { - // count number of pairs with coeff 1 - unsigned num_coeff_1=0; - bool still_numeric=true; - epvector::const_iterator cit=seq.end(); - unsigned first_pos; - unsigned second_pos; - do { - cit--; - if (is_ex_exactly_of_type((*cit).rest,numeric)) { - if ((*cit).coeff.is_equal(exONE())) { - num_coeff_1++; - } - } else { - still_numeric=false; - } - } while ((cit!=seq.begin())&&still_numeric); - if (num_coeff_1>1) { - newseq=seq; - - } - - -#ifdef DOASSERT - for (epvector::const_iterator cit=seq.begin(); cit!=seq.end(); ++cit) { - ASSERT((!is_ex_exactly_of_type((*cit).rest,mul))|| - (!(ex_to_numeric((*cit).coeff).is_integer()))); - } - - // test if all numerics were moved to the end and - // all numerics with coeff 1 to the very end - if (seq.size()!=0) { - epvector::const_iterator cit=seq.end(); - bool all_coeff_1=true; - bool all_numeric=true; - do { - cit--; - if (is_ex_exactly_of_type((*cit).rest,numeric)) { - ASSERT(all_numeric); - if ((*cit).coeff.is_equal(exONE())) { - ASSERT(all_coeff_1); - } else { - all_coeff_1=false; - } - } else { - all_numeric=false; - } - } while (cit!=seq.begin()); - } -#endif // def DOASSERT - - if (flags & status_flags::evaluated) { - return *this; - } - - expair const & last_expair=*(seq.end()-1); - expair const & next_to_last_expair=*(seq.end()-2); - int seq_size = seq.size(); - - // *(...,x,(c1,1),(c2,1)) -> *(...,x,(c1*c2,1)) (c1, c2 numeric()) - if ((!seq_copied) && (seq_size>=2) && - is_ex_exactly_of_type(last_expair.rest,numeric) && - ex_to_numeric(last_expair.coeff).is_equal(numONE()) && - is_ex_exactly_of_type(next_to_last_expair.rest,numeric) && - ex_to_numeric(next_to_last_expair.coeff).is_equal(numONE()) ) { - newseq=seq; - seq_copied=true; - it2=newseq.end()-1; - it1=it2-1; - } - while (seq_copied && (newseq.size()>=2) && - is_ex_exactly_of_type((*it1).rest,numeric) && - ex_to_numeric((*it1).coeff).is_equal(numONE()) && - is_ex_exactly_of_type((*it2).rest,numeric) && - ex_to_numeric((*it2).coeff).is_equal(numONE()) ) { - *it1=expair(ex_to_numeric((*it1).rest).mul_dyn(ex_to_numeric((*it2).rest)),exONE()); - newseq.pop_back(); - it2=newseq.end()-1; - it1=it2-1; - } - - // *(...,x,1) -> *(...,x) - if ((!seq_copied) && (seq_size>=1) && - (is_ex_exactly_of_type(last_expair.rest,numeric)) && - (ex_to_numeric(last_expair.rest).compare(numONE())==0)) { - newseq=seq; - seq_copied=true; - it2=newseq.end()-1; - } - if (seq_copied && (newseq.size()>=1) && - (is_ex_exactly_of_type((*it2).rest,numeric)) && - (ex_to_numeric((*it2).rest).compare(numONE())==0)) { - newseq.pop_back(); - it2=newseq.end()-1; - } - - // *(...,x,0) -> 0 - if ((!seq_copied) && (seq_size>=1) && - (is_ex_exactly_of_type(last_expair.rest,numeric)) && - (ex_to_numeric(last_expair.rest).is_zero())) { - return exZERO(); - } - if (seq_copied && (newseq.size()>=1) && - (is_ex_exactly_of_type((*it2).rest,numeric)) && - (ex_to_numeric((*it2).rest).is_zero())) { - return exZERO(); - } - - // *(+(x,y,...),c) -> +(*(x,c),*(y,c),...) (c numeric(), no powers of +()) - if ((!seq_copied) && (seq_size==2) && - is_ex_exactly_of_type(next_to_last_expair.rest,add) && - is_ex_exactly_of_type(last_expair.rest,numeric) && - ex_to_numeric(last_expair.coeff).is_equal(numONE()) && - (ex_to_numeric(next_to_last_expair.coeff).compare(numONE())==0)) { - add const & addref=ex_to_add(next_to_last_expair.rest); - epvector distrseq; - distrseq.reserve(addref.seq.size()); - for (epvector::const_iterator cit=addref.seq.begin(); cit!=addref.seq.end(); ++cit) { - distrseq.push_back(addref.combine_pair_with_coeff_to_pair(*cit, - last_expair.rest)); - } - // special treatment for the last element if it is numeric (to - // avoid terms like (2/3)*(3/2)) is no longer necessary, this - // is handled in add::combine_pair_with_coeff_to_pair() - return (new add(distrseq,1))->setflag(status_flags::dynallocated | - status_flags::evaluated ); - } - if (seq_copied && (newseq.size()==2) && - is_ex_exactly_of_type(newseq[0].rest,add) && - is_ex_exactly_of_type(newseq[1].rest,numeric) && - ex_to_numeric(newseq[1].coeff).is_equal(numONE()) && - (ex_to_numeric(newseq[0].coeff).compare(numONE())==0)) { - add const & addref=ex_to_add(newseq[0].rest); - epvector distrseq; - distrseq.reserve(addref.seq.size()); - for (epvector::const_iterator cit=addref.seq.begin(); cit!=addref.seq.end(); ++cit) { - distrseq.push_back(addref.combine_pair_with_coeff_to_pair(*cit, - newseq[1].rest)); - } - // special treatment for the last element if it is numeric (to - // avoid terms like (2/3)*(3/2)) is no longer necessary, this - // is handled in add::combine_pair_with_coeff_to_pair() - return (new add(distrseq,1))->setflag(status_flags::dynallocated | - status_flags::evaluated ); - } - - // *() -> 1 - if ((!seq_copied) && (seq_size==0)) { - return exONE(); - } else if (seq_copied && (newseq.size()==0)) { - return exONE(); - } - - // *(x) -> x - if ((!seq_copied) && (seq_size==1)) { - return recombine_pair_to_ex(*(seq.begin())); - } else if (seq_copied && (newseq.size()==1)) { - return recombine_pair_to_ex(*(newseq.begin())); - } - - if (!seq_copied) return this->hold(); - - return (new mul(newseq,1))->setflag(status_flags::dynallocated | - status_flags::evaluated ); -} -*/ - -ex mul::eval(int level) const -{ - // simplifications *(...,x;0) -> 0 - // *(+(x,y,...);c) -> *(+(*(x,c),*(y,c),...)) (c numeric()) - // *(x;1) -> x - // *(;c) -> c - - debugmsg("mul eval",LOGLEVEL_MEMBER_FUNCTION); - - epvector * evaled_seqp=evalchildren(level); - if (evaled_seqp!=0) { - // do more evaluation later - return (new mul(evaled_seqp,overall_coeff))-> - setflag(status_flags::dynallocated); - } - -#ifdef DOASSERT - for (epvector::const_iterator cit=seq.begin(); cit!=seq.end(); ++cit) { - ASSERT((!is_ex_exactly_of_type((*cit).rest,mul))|| - (!(ex_to_numeric((*cit).coeff).is_integer()))); - ASSERT(!((*cit).is_numeric_with_coeff_1())); - if (is_ex_exactly_of_type(recombine_pair_to_ex(*cit),numeric)) { - printtree(cerr,0); - } - ASSERT(!is_ex_exactly_of_type(recombine_pair_to_ex(*cit),numeric)); - /* for paranoia */ - expair p=split_ex_to_pair(recombine_pair_to_ex(*cit)); - ASSERT(p.rest.is_equal((*cit).rest)); - ASSERT(p.coeff.is_equal((*cit).coeff)); - /* end paranoia */ - } -#endif // def DOASSERT - - if (flags & status_flags::evaluated) { - ASSERT(seq.size()>0); - ASSERT((seq.size()>1)||!overall_coeff.is_equal(exONE())); - return *this; - } - - int seq_size=seq.size(); - if (overall_coeff.is_equal(exZERO())) { - // *(...,x;0) -> 0 - return exZERO(); - } else if (seq_size==0) { - // *(;c) -> c - return overall_coeff; - } else if ((seq_size==1)&&overall_coeff.is_equal(exONE())) { - // *(x;1) -> x - return recombine_pair_to_ex(*(seq.begin())); - } else if ((seq_size==1) && - is_ex_exactly_of_type((*seq.begin()).rest,add) && - ex_to_numeric((*seq.begin()).coeff).is_equal(numONE())) { - // *(+(x,y,...);c) -> +(*(x,c),*(y,c),...) (c numeric(), no powers of +()) - add const & addref=ex_to_add((*seq.begin()).rest); - epvector distrseq; - distrseq.reserve(addref.seq.size()); - for (epvector::const_iterator cit=addref.seq.begin(); cit!=addref.seq.end(); ++cit) { - distrseq.push_back(addref.combine_pair_with_coeff_to_pair(*cit, - overall_coeff)); - } - return (new add(distrseq, - ex_to_numeric(addref.overall_coeff). - mul_dyn(ex_to_numeric(overall_coeff)))) - ->setflag(status_flags::dynallocated | - status_flags::evaluated ); - } - return this->hold(); -} - -/* + switch (inf) { + case info_flags::polynomial: + case info_flags::integer_polynomial: + case info_flags::cinteger_polynomial: + case info_flags::rational_polynomial: + case info_flags::crational_polynomial: + case info_flags::rational_function: { + epvector::const_iterator i = seq.begin(), end = seq.end(); + while (i != end) { + if (!(recombine_pair_to_ex(*i).info(inf))) + return false; + ++i; + } + return overall_coeff.info(inf); + } + case info_flags::algebraic: { + epvector::const_iterator i = seq.begin(), end = seq.end(); + while (i != end) { + if ((recombine_pair_to_ex(*i).info(inf))) + return true; + ++i; + } + return false; + } + } + return inherited::info(inf); +} + +int mul::degree(const ex & s) const +{ + // Sum up degrees of factors + int deg_sum = 0; + epvector::const_iterator i = seq.begin(), end = seq.end(); + while (i != end) { + if (ex_to(i->coeff).is_integer()) + deg_sum += i->rest.degree(s) * ex_to(i->coeff).to_int(); + ++i; + } + return deg_sum; +} + +int mul::ldegree(const ex & s) const +{ + // Sum up degrees of factors + int deg_sum = 0; + epvector::const_iterator i = seq.begin(), end = seq.end(); + while (i != end) { + if (ex_to(i->coeff).is_integer()) + deg_sum += i->rest.ldegree(s) * ex_to(i->coeff).to_int(); + ++i; + } + return deg_sum; +} + +ex mul::coeff(const ex & s, int n) const +{ + exvector coeffseq; + coeffseq.reserve(seq.size()+1); + + if (n==0) { + // product of individual coeffs + // if a non-zero power of s is found, the resulting product will be 0 + epvector::const_iterator i = seq.begin(), end = seq.end(); + while (i != end) { + coeffseq.push_back(recombine_pair_to_ex(*i).coeff(s,n)); + ++i; + } + coeffseq.push_back(overall_coeff); + return (new mul(coeffseq))->setflag(status_flags::dynallocated); + } + + epvector::const_iterator i = seq.begin(), end = seq.end(); + bool coeff_found = false; + while (i != end) { + ex t = recombine_pair_to_ex(*i); + ex c = t.coeff(s, n); + if (!c.is_zero()) { + coeffseq.push_back(c); + coeff_found = 1; + } else { + coeffseq.push_back(t); + } + ++i; + } + if (coeff_found) { + coeffseq.push_back(overall_coeff); + return (new mul(coeffseq))->setflag(status_flags::dynallocated); + } + + return _ex0; +} + +/** Perform automatic term rewriting rules in this class. In the following + * x, x1, x2,... stand for a symbolic variables of type ex and c, c1, c2... + * stand for such expressions that contain a plain number. + * - *(...,x;0) -> 0 + * - *(+(x1,x2,...);c) -> *(+(*(x1,c),*(x2,c),...)) + * - *(x;1) -> x + * - *(;c) -> c + * + * @param level cut-off in recursive evaluation */ ex mul::eval(int level) const { - // simplifications: *(...,x,c1,c2) -> *(...,x,c1*c2) (c1, c2 numeric()) - // *(...,(c1,c2)) -> (...,(c1^c2,1)) (normalize) - // *(...,x,1) -> +(...,x) - // *(...,x,0) -> 0 - // *(+(x,y,...),c) -> *(+(*(x,c),*(y,c),...)) (c numeric()) - // *(x) -> x - // *() -> 1 - - debugmsg("mul eval",LOGLEVEL_MEMBER_FUNCTION); - - epvector newseq=seq; - epvector::iterator it1,it2; - - // *(...,x,c1,c2) -> *(...,x,c1*c2) (c1, c2 numeric()) - it2=newseq.end()-1; - it1=it2-1; - while ((newseq.size()>=2)&&is_exactly_of_type(*(*it1).rest.bp,numeric)&& - is_exactly_of_type(*(*it2).rest.bp,numeric)) { - *it1=expair(ex_to_numeric((*it1).rest).power(ex_to_numeric((*it1).coeff)) - .mul(ex_to_numeric((*it2).rest).power(ex_to_numeric((*it2).coeff))),exONE()); - newseq.pop_back(); - it2=newseq.end()-1; - it1=it2-1; - } - - if ((newseq.size()>=1)&&is_exactly_of_type(*(*it2).rest.bp,numeric)) { - // *(...,(c1,c2)) -> (...,(c1^c2,1)) (normalize) - *it2=expair(ex_to_numeric((*it2).rest).power(ex_to_numeric((*it2).coeff)),exONE()); - // *(...,x,1) -> *(...,x) - if (static_cast(*(*it2).rest.bp).compare(numONE())==0) { - newseq.pop_back(); - it2=newseq.end()-1; - } - } - - // *(...,x,0) -> 0 - if ((newseq.size()>=1)&&is_exactly_of_type(*(*it2).rest.bp,numeric)) { - if (static_cast(*(*it2).rest.bp).is_zero()==0) { - return exZERO(); - } - } - - // *(+(x,y,...),c) -> +(*(x,c),*(y,c),...) (c numeric(), no powers of +()) - if ((newseq.size()==2)&&is_ex_exactly_of_type(newseq[0].rest,add)&& - is_ex_exactly_of_type(newseq[1].rest,numeric)&& - (ex_to_numeric(newseq[0].coeff).compare(numONE())==0)) { - add const & addref=ex_to_add(newseq[0].rest); - numeric const & numref=ex_to_numeric(newseq[1].rest); - epvector distrseq; - distrseq.reserve(addref.seq.size()); - for (epvector::const_iterator cit=addref.seq.begin(); cit!=addref.seq.end(); ++cit) { - distrseq.push_back(expair((*cit).rest,ex_to_numeric((*cit).coeff).mul(numref))); - } - return (new add(distrseq,1))->setflag(status_flags::dynallocated | - status_flags::evaluated ); - } - - if (newseq.size()==0) { - // *() -> 1 - return exONE(); - } else if (newseq.size()==1) { - // *(x) -> x - return recombine_pair_to_ex(*newseq.begin()); - } - - return (new mul(newseq,1))->setflag(status_flags::dynallocated | - status_flags::evaluated ); -} -*/ - -exvector mul::get_indices(void) const -{ - // return union of indices of factors - exvector iv; - for (epvector::const_iterator cit=seq.begin(); cit!=seq.end(); ++cit) { - exvector subiv=(*cit).rest.get_indices(); - iv.reserve(iv.size()+subiv.size()); - for (exvector::const_iterator cit2=subiv.begin(); cit2!=subiv.end(); ++cit2) { - iv.push_back(*cit2); - } - } - return iv; -} - -ex mul::simplify_ncmul(exvector const & v) const -{ - throw(std::logic_error("mul::simplify_ncmul() should never have been called!")); + epvector *evaled_seqp = evalchildren(level); + if (evaled_seqp) { + // do more evaluation later + return (new mul(evaled_seqp,overall_coeff))-> + setflag(status_flags::dynallocated); + } + +#ifdef DO_GINAC_ASSERT + epvector::const_iterator i = seq.begin(), end = seq.end(); + while (i != end) { + GINAC_ASSERT((!is_exactly_a(i->rest)) || + (!(ex_to(i->coeff).is_integer()))); + GINAC_ASSERT(!(i->is_canonical_numeric())); + if (is_exactly_a(recombine_pair_to_ex(*i))) + print(print_tree(std::cerr)); + GINAC_ASSERT(!is_exactly_a(recombine_pair_to_ex(*i))); + /* for paranoia */ + expair p = split_ex_to_pair(recombine_pair_to_ex(*i)); + GINAC_ASSERT(p.rest.is_equal(i->rest)); + GINAC_ASSERT(p.coeff.is_equal(i->coeff)); + /* end paranoia */ + ++i; + } +#endif // def DO_GINAC_ASSERT + + if (flags & status_flags::evaluated) { + GINAC_ASSERT(seq.size()>0); + GINAC_ASSERT(seq.size()>1 || !overall_coeff.is_equal(_ex1)); + return *this; + } + + int seq_size = seq.size(); + if (overall_coeff.is_zero()) { + // *(...,x;0) -> 0 + return _ex0; + } else if (seq_size==0) { + // *(;c) -> c + return overall_coeff; + } else if (seq_size==1 && overall_coeff.is_equal(_ex1)) { + // *(x;1) -> x + return recombine_pair_to_ex(*(seq.begin())); + } else if ((seq_size==1) && + is_exactly_a((*seq.begin()).rest) && + ex_to((*seq.begin()).coeff).is_equal(_num1)) { + // *(+(x,y,...);c) -> +(*(x,c),*(y,c),...) (c numeric(), no powers of +()) + const add & addref = ex_to((*seq.begin()).rest); + epvector *distrseq = new epvector(); + distrseq->reserve(addref.seq.size()); + epvector::const_iterator i = addref.seq.begin(), end = addref.seq.end(); + while (i != end) { + distrseq->push_back(addref.combine_pair_with_coeff_to_pair(*i, overall_coeff)); + ++i; + } + return (new add(distrseq, + ex_to(addref.overall_coeff). + mul_dyn(ex_to(overall_coeff)))) + ->setflag(status_flags::dynallocated | status_flags::evaluated); + } + return this->hold(); +} + +ex mul::evalf(int level) const +{ + if (level==1) + return mul(seq,overall_coeff); + + if (level==-max_recursion_level) + throw(std::runtime_error("max recursion level reached")); + + epvector *s = new epvector(); + s->reserve(seq.size()); + + --level; + epvector::const_iterator i = seq.begin(), end = seq.end(); + while (i != end) { + s->push_back(combine_ex_with_coeff_to_pair(i->rest.evalf(level), + i->coeff)); + ++i; + } + return mul(s, overall_coeff.evalf(level)); +} + +ex mul::evalm() const +{ + // numeric*matrix + if (seq.size() == 1 && seq[0].coeff.is_equal(_ex1) + && is_a(seq[0].rest)) + return ex_to(seq[0].rest).mul(ex_to(overall_coeff)); + + // Evaluate children first, look whether there are any matrices at all + // (there can be either no matrices or one matrix; if there were more + // than one matrix, it would be a non-commutative product) + epvector *s = new epvector; + s->reserve(seq.size()); + + bool have_matrix = false; + epvector::iterator the_matrix; + + epvector::const_iterator i = seq.begin(), end = seq.end(); + while (i != end) { + const ex &m = recombine_pair_to_ex(*i).evalm(); + s->push_back(split_ex_to_pair(m)); + if (is_a(m)) { + have_matrix = true; + the_matrix = s->end() - 1; + } + ++i; + } + + if (have_matrix) { + + // The product contained a matrix. We will multiply all other factors + // into that matrix. + matrix m = ex_to(the_matrix->rest); + s->erase(the_matrix); + ex scalar = (new mul(s, overall_coeff))->setflag(status_flags::dynallocated); + return m.mul_scalar(scalar); + + } else + return (new mul(s, overall_coeff))->setflag(status_flags::dynallocated); +} + +ex mul::eval_ncmul(const exvector & v) const +{ + if (seq.empty()) + return inherited::eval_ncmul(v); + + // Find first noncommutative element and call its eval_ncmul() + epvector::const_iterator i = seq.begin(), end = seq.end(); + while (i != end) { + if (i->rest.return_type() == return_types::noncommutative) + return i->rest.eval_ncmul(v); + ++i; + } + return inherited::eval_ncmul(v); +} + +bool tryfactsubs(const ex & origfactor, const ex & patternfactor, int & nummatches, lst & repls) +{ + ex origbase; + int origexponent; + int origexpsign; + + if (is_exactly_a(origfactor) && origfactor.op(1).info(info_flags::integer)) { + origbase = origfactor.op(0); + int expon = ex_to(origfactor.op(1)).to_int(); + origexponent = expon > 0 ? expon : -expon; + origexpsign = expon > 0 ? 1 : -1; + } else { + origbase = origfactor; + origexponent = 1; + origexpsign = 1; + } + + ex patternbase; + int patternexponent; + int patternexpsign; + + if (is_exactly_a(patternfactor) && patternfactor.op(1).info(info_flags::integer)) { + patternbase = patternfactor.op(0); + int expon = ex_to(patternfactor.op(1)).to_int(); + patternexponent = expon > 0 ? expon : -expon; + patternexpsign = expon > 0 ? 1 : -1; + } else { + patternbase = patternfactor; + patternexponent = 1; + patternexpsign = 1; + } + + lst saverepls = repls; + if (origexponent < patternexponent || origexpsign != patternexpsign || !origbase.match(patternbase,saverepls)) + return false; + repls = saverepls; + + int newnummatches = origexponent / patternexponent; + if (newnummatches < nummatches) + nummatches = newnummatches; + return true; +} + +ex mul::algebraic_subs_mul(const exmap & m, unsigned options) const +{ + std::vector subsed(seq.size(), false); + exvector subsresult(seq.size()); + + for (exmap::const_iterator it = m.begin(); it != m.end(); ++it) { + + if (is_exactly_a(it->first)) { + + int nummatches = std::numeric_limits::max(); + std::vector currsubsed(seq.size(), false); + bool succeed = true; + lst repls; + + for (size_t j=0; jfirst.nops(); j++) { + bool found=false; + for (size_t k=0; kfirst.op(j), nummatches, repls)) { + currsubsed[k] = true; + found = true; + break; + } + } + if (!found) { + succeed = false; + break; + } + } + if (!succeed) + continue; + + bool foundfirstsubsedfactor = false; + for (size_t j=0; jsecond.subs(ex(repls), subs_options::subs_no_pattern) / it->first.subs(ex(repls), subs_options::subs_no_pattern), nummatches); + } + subsed[j] = true; + } + } + + } else { + + int nummatches = std::numeric_limits::max(); + lst repls; + + for (size_t j=0; jnops(); j++) { + if (!subsed[j] && tryfactsubs(op(j), it->first, nummatches, repls)) { + subsed[j] = true; + subsresult[j] = op(j) * power(it->second.subs(ex(repls), subs_options::subs_no_pattern) / it->first.subs(ex(repls), subs_options::subs_no_pattern), nummatches); + } + } + } + } + + bool subsfound = false; + for (size_t i=0; isetflag(status_flags::dynallocated); } // protected -int mul::compare_same_type(basic const & other) const -{ - return expairseq::compare_same_type(other); -} - -bool mul::is_equal_same_type(basic const & other) const -{ - return expairseq::is_equal_same_type(other); -} - -unsigned mul::return_type(void) const -{ - if (seq.size()==0) { - // mul without factors: should not happen, but commutes - return return_types::commutative; - } - - bool all_commutative=1; - unsigned rt; - epvector::const_iterator cit_noncommutative_element; // point to first found nc element - - for (epvector::const_iterator cit=seq.begin(); cit!=seq.end(); ++cit) { - rt=(*cit).rest.return_type(); - if (rt==return_types::noncommutative_composite) return rt; // one ncc -> mul also ncc - if ((rt==return_types::noncommutative)&&(all_commutative)) { - // first nc element found, remember position - cit_noncommutative_element=cit; - all_commutative=0; - } - if ((rt==return_types::noncommutative)&&(!all_commutative)) { - // another nc element found, compare type_infos - if ((*cit_noncommutative_element).rest.return_type_tinfo()!=(*cit).rest.return_type_tinfo()) { - // diffent types -> mul is ncc - return return_types::noncommutative_composite; - } - } - } - // all factors checked - return all_commutative ? return_types::commutative : return_types::noncommutative; +/** Implementation of ex::diff() for a product. It applies the product rule. + * @see ex::diff */ +ex mul::derivative(const symbol & s) const +{ + size_t num = seq.size(); + exvector addseq; + addseq.reserve(num); + + // D(a*b*c) = D(a)*b*c + a*D(b)*c + a*b*D(c) + epvector mulseq = seq; + epvector::const_iterator i = seq.begin(), end = seq.end(); + epvector::iterator i2 = mulseq.begin(); + while (i != end) { + expair ep = split_ex_to_pair(power(i->rest, i->coeff - _ex1) * + i->rest.diff(s)); + ep.swap(*i2); + addseq.push_back((new mul(mulseq, overall_coeff * i->coeff))->setflag(status_flags::dynallocated)); + ep.swap(*i2); + ++i; ++i2; + } + return (new add(addseq))->setflag(status_flags::dynallocated); +} + +int mul::compare_same_type(const basic & other) const +{ + return inherited::compare_same_type(other); +} + +unsigned mul::return_type() const +{ + if (seq.empty()) { + // mul without factors: should not happen, but commutes + return return_types::commutative; + } + + bool all_commutative = true; + epvector::const_iterator noncommutative_element; // point to first found nc element + + epvector::const_iterator i = seq.begin(), end = seq.end(); + while (i != end) { + unsigned rt = i->rest.return_type(); + if (rt == return_types::noncommutative_composite) + return rt; // one ncc -> mul also ncc + if ((rt == return_types::noncommutative) && (all_commutative)) { + // first nc element found, remember position + noncommutative_element = i; + all_commutative = false; + } + if ((rt == return_types::noncommutative) && (!all_commutative)) { + // another nc element found, compare type_infos + if (noncommutative_element->rest.return_type_tinfo() != i->rest.return_type_tinfo()) { + // diffent types -> mul is ncc + return return_types::noncommutative_composite; + } + } + ++i; + } + // all factors checked + return all_commutative ? return_types::commutative : return_types::noncommutative; } -unsigned mul::return_type_tinfo(void) const +unsigned mul::return_type_tinfo() const { - if (seq.size()==0) { - // mul without factors: should not happen - return tinfo_key; - } - // return type_info of first noncommutative element - for (epvector::const_iterator cit=seq.begin(); cit!=seq.end(); ++cit) { - if ((*cit).rest.return_type()==return_types::noncommutative) { - return (*cit).rest.return_type_tinfo(); - } - } - // no noncommutative element found, should not happen - return tinfo_key; + if (seq.empty()) + return tinfo_key; // mul without factors: should not happen + + // return type_info of first noncommutative element + epvector::const_iterator i = seq.begin(), end = seq.end(); + while (i != end) { + if (i->rest.return_type() == return_types::noncommutative) + return i->rest.return_type_tinfo(); + ++i; + } + // no noncommutative element found, should not happen + return tinfo_key; } -ex mul::thisexpairseq(epvector const & v, ex const & oc) const +ex mul::thisexpairseq(const epvector & v, const ex & oc) const { - return (new mul(v,oc))->setflag(status_flags::dynallocated); + return (new mul(v, oc))->setflag(status_flags::dynallocated); } -ex mul::thisexpairseq(epvector * vp, ex const & oc) const +ex mul::thisexpairseq(epvector * vp, const ex & oc) const { - return (new mul(vp,oc))->setflag(status_flags::dynallocated); + return (new mul(vp, oc))->setflag(status_flags::dynallocated); } -expair mul::split_ex_to_pair(ex const & e) const +expair mul::split_ex_to_pair(const ex & e) const { - if (is_ex_exactly_of_type(e,power)) { - power const & powerref=ex_to_power(e); - if (is_ex_exactly_of_type(powerref.exponent,numeric)) { - return expair(powerref.basis,powerref.exponent); - } - } - return expair(e,exONE()); + if (is_exactly_a(e)) { + const power & powerref = ex_to(e); + if (is_exactly_a(powerref.exponent)) + return expair(powerref.basis,powerref.exponent); + } + return expair(e,_ex1); } - -expair mul::combine_ex_with_coeff_to_pair(ex const & e, - ex const & c) const + +expair mul::combine_ex_with_coeff_to_pair(const ex & e, + const ex & c) const { - // to avoid duplication of power simplification rules, - // we create a temporary power object - // otherwise it would be hard to correctly simplify - // expression like (4^(1/3))^(3/2) - if (are_ex_trivially_equal(c,exONE())) { - return split_ex_to_pair(e); - } - return split_ex_to_pair(power(e,c)); + // to avoid duplication of power simplification rules, + // we create a temporary power object + // otherwise it would be hard to correctly evaluate + // expression like (4^(1/3))^(3/2) + if (c.is_equal(_ex1)) + return split_ex_to_pair(e); + + return split_ex_to_pair(power(e,c)); } - -expair mul::combine_pair_with_coeff_to_pair(expair const & p, - ex const & c) const + +expair mul::combine_pair_with_coeff_to_pair(const expair & p, + const ex & c) const { - // to avoid duplication of power simplification rules, - // we create a temporary power object - // otherwise it would be hard to correctly simplify - // expression like (4^(1/3))^(3/2) - if (are_ex_trivially_equal(c,exONE())) { - return p; - } - return split_ex_to_pair(power(recombine_pair_to_ex(p),c)); + // to avoid duplication of power simplification rules, + // we create a temporary power object + // otherwise it would be hard to correctly evaluate + // expression like (4^(1/3))^(3/2) + if (c.is_equal(_ex1)) + return p; + + return split_ex_to_pair(power(recombine_pair_to_ex(p),c)); } - -ex mul::recombine_pair_to_ex(expair const & p) const + +ex mul::recombine_pair_to_ex(const expair & p) const { - // if (p.coeff.compare(exONE())==0) { - // if (are_ex_trivially_equal(p.coeff,exONE())) { - if (ex_to_numeric(p.coeff).is_equal(numONE())) { - return p.rest; - } else { - return power(p.rest,p.coeff); - } + if (ex_to(p.coeff).is_equal(_num1)) + return p.rest; + else + return (new power(p.rest,p.coeff))->setflag(status_flags::dynallocated); } bool mul::expair_needs_further_processing(epp it) { - if (is_ex_exactly_of_type((*it).rest,mul) && - ex_to_numeric((*it).coeff).is_integer()) { - // combined pair is product with integer power -> expand it - *it=split_ex_to_pair(recombine_pair_to_ex(*it)); - return true; - } - if (is_ex_exactly_of_type((*it).rest,numeric)) { - expair ep=split_ex_to_pair(recombine_pair_to_ex(*it)); - if (!ep.is_equal(*it)) { - // combined pair is a numeric power which can be simplified - *it=ep; - return true; - } - if (ex_to_numeric((*it).coeff).is_equal(numONE())) { - // combined pair has coeff 1 and must be moved to the end - return true; - } - } - return false; + if (is_exactly_a(it->rest) && + ex_to(it->coeff).is_integer()) { + // combined pair is product with integer power -> expand it + *it = split_ex_to_pair(recombine_pair_to_ex(*it)); + return true; + } + if (is_exactly_a(it->rest)) { + expair ep = split_ex_to_pair(recombine_pair_to_ex(*it)); + if (!ep.is_equal(*it)) { + // combined pair is a numeric power which can be simplified + *it = ep; + return true; + } + if (it->coeff.is_equal(_ex1)) { + // combined pair has coeff 1 and must be moved to the end + return true; + } + } + return false; } -ex mul::default_overall_coeff(void) const +ex mul::default_overall_coeff() const { - return exONE(); + return _ex1; } -void mul::combine_overall_coeff(ex const & c) +void mul::combine_overall_coeff(const ex & c) { - ASSERT(is_ex_exactly_of_type(overall_coeff,numeric)); - ASSERT(is_ex_exactly_of_type(c,numeric)); - overall_coeff = ex_to_numeric(overall_coeff).mul_dyn(ex_to_numeric(c)); + GINAC_ASSERT(is_exactly_a(overall_coeff)); + GINAC_ASSERT(is_exactly_a(c)); + overall_coeff = ex_to(overall_coeff).mul_dyn(ex_to(c)); } -void mul::combine_overall_coeff(ex const & c1, ex const & c2) +void mul::combine_overall_coeff(const ex & c1, const ex & c2) { - ASSERT(is_ex_exactly_of_type(overall_coeff,numeric)); - ASSERT(is_ex_exactly_of_type(c1,numeric)); - ASSERT(is_ex_exactly_of_type(c2,numeric)); - overall_coeff = ex_to_numeric(overall_coeff). - mul_dyn(ex_to_numeric(c1).power(ex_to_numeric(c2))); + GINAC_ASSERT(is_exactly_a(overall_coeff)); + GINAC_ASSERT(is_exactly_a(c1)); + GINAC_ASSERT(is_exactly_a(c2)); + overall_coeff = ex_to(overall_coeff).mul_dyn(ex_to(c1).power(ex_to(c2))); } -bool mul::can_make_flat(expair const & p) const +bool mul::can_make_flat(const expair & p) const { - ASSERT(is_ex_exactly_of_type(p.coeff,numeric)); - // this assertion will probably fail somewhere - // it would require a more careful make_flat, obeying the power laws - // probably should return true only if p.coeff is integer - return ex_to_numeric(p.coeff).is_equal(numONE()); + GINAC_ASSERT(is_exactly_a(p.coeff)); + // this assertion will probably fail somewhere + // it would require a more careful make_flat, obeying the power laws + // probably should return true only if p.coeff is integer + return ex_to(p.coeff).is_equal(_num1); } ex mul::expand(unsigned options) const { - exvector sub_expanded_seq; - intvector positions_of_adds; - intvector number_of_add_operands; - - epvector * expanded_seqp=expandchildren(options); - - epvector const & expanded_seq = expanded_seqp==0 ? seq : *expanded_seqp; - - positions_of_adds.resize(expanded_seq.size()); - number_of_add_operands.resize(expanded_seq.size()); - - int number_of_adds=0; - int number_of_expanded_terms=1; - - unsigned current_position=0; - epvector::const_iterator last=expanded_seq.end(); - for (epvector::const_iterator cit=expanded_seq.begin(); cit!=last; ++cit) { - if (is_ex_exactly_of_type((*cit).rest,add)&& - (ex_to_numeric((*cit).coeff).is_equal(numONE()))) { - positions_of_adds[number_of_adds]=current_position; - add const & expanded_addref=ex_to_add((*cit).rest); - int addref_nops=expanded_addref.nops(); - number_of_add_operands[number_of_adds]=addref_nops; - number_of_expanded_terms *= addref_nops; - number_of_adds++; - } - current_position++; - } - - if (number_of_adds==0) { - if (expanded_seqp==0) { - return this->setflag(status_flags::expanded); - } - return (new mul(expanded_seqp,overall_coeff))-> - setflag(status_flags::dynallocated || - status_flags::expanded); - } - - exvector distrseq; - distrseq.reserve(number_of_expanded_terms); - - intvector k; - k.resize(number_of_adds); - - int l; - for (l=0; l - setflag(status_flags::dynallocated | - status_flags::expanded)); - - // increment k[] - l=number_of_adds-1; - while ((l>=0)&&((++k[l])>=number_of_add_operands[l])) { - k[l]=0; - l--; - } - if (l<0) break; - } - - if (expanded_seqp!=0) { - delete expanded_seqp; - } - /* - cout << "mul::expand() distrseq begin" << endl; - for (exvector::const_iterator cit=distrseq.begin(); cit!=distrseq.end(); ++cit) { - (*cit).printtree(cout); - } - cout << "mul::expand() distrseq end" << endl; - */ - - return (new add(distrseq))->setflag(status_flags::dynallocated | - status_flags::expanded); -} - -/* -ex mul::expand(unsigned options) const -{ - exvector sub_expanded_seq; - intvector positions_of_adds; - intvector number_of_add_operands; - - sub_expanded_seq.resize(seq.size()); - positions_of_adds.resize(seq.size()); - number_of_add_operands.reserve(seq.size()); - - int number_of_adds=0; - int number_of_expanded_terms=1; - for (unsigned current_position=0; current_positionsetflag(status_flags::dynallocated | - status_flags::expanded)); - - // increment k[] - l=number_of_adds-1; - while ((l>=0)&&((++k[l])>=number_of_add_operands[l])) { - k[l]=0; - l--; - } - if (l<0) break; - } - - return (new add(distrseq))->setflag(status_flags::dynallocated | - status_flags::expanded); -} -*/ - + // First, expand the children + epvector * expanded_seqp = expandchildren(options); + const epvector & expanded_seq = (expanded_seqp == NULL) ? seq : *expanded_seqp; + + // Now, look for all the factors that are sums and multiply each one out + // with the next one that is found while collecting the factors which are + // not sums + int number_of_adds = 0; + ex last_expanded = _ex1; + epvector non_adds; + non_adds.reserve(expanded_seq.size()); + epvector::const_iterator cit = expanded_seq.begin(), last = expanded_seq.end(); + while (cit != last) { + if (is_exactly_a(cit->rest) && + (cit->coeff.is_equal(_ex1))) { + ++number_of_adds; + if (is_exactly_a(last_expanded)) { + + // Expand a product of two sums, aggressive version. + // Caring for the overall coefficients in separate loops can + // sometimes give a performance gain of up to 15%! + + const int sizedifference = ex_to(last_expanded).seq.size()-ex_to(cit->rest).seq.size(); + // add2 is for the inner loop and should be the bigger of the two sums + // in the presence of asymptotically good sorting: + const add& add1 = (sizedifference<0 ? ex_to(last_expanded) : ex_to(cit->rest)); + const add& add2 = (sizedifference<0 ? ex_to(cit->rest) : ex_to(last_expanded)); + const epvector::const_iterator add1begin = add1.seq.begin(); + const epvector::const_iterator add1end = add1.seq.end(); + const epvector::const_iterator add2begin = add2.seq.begin(); + const epvector::const_iterator add2end = add2.seq.end(); + epvector distrseq; + distrseq.reserve(add1.seq.size()+add2.seq.size()); + // Multiply add2 with the overall coefficient of add1 and append it to distrseq: + if (!add1.overall_coeff.is_zero()) { + if (add1.overall_coeff.is_equal(_ex1)) + distrseq.insert(distrseq.end(),add2begin,add2end); + else + for (epvector::const_iterator i=add2begin; i!=add2end; ++i) + distrseq.push_back(expair(i->rest, ex_to(i->coeff).mul_dyn(ex_to(add1.overall_coeff)))); + } + // Multiply add1 with the overall coefficient of add2 and append it to distrseq: + if (!add2.overall_coeff.is_zero()) { + if (add2.overall_coeff.is_equal(_ex1)) + distrseq.insert(distrseq.end(),add1begin,add1end); + else + for (epvector::const_iterator i=add1begin; i!=add1end; ++i) + distrseq.push_back(expair(i->rest, ex_to(i->coeff).mul_dyn(ex_to(add2.overall_coeff)))); + } + // Compute the new overall coefficient and put it together: + ex tmp_accu = (new add(distrseq, add1.overall_coeff*add2.overall_coeff))->setflag(status_flags::dynallocated); + // Multiply explicitly all non-numeric terms of add1 and add2: + for (epvector::const_iterator i1=add1begin; i1!=add1end; ++i1) { + // We really have to combine terms here in order to compactify + // the result. Otherwise it would become waayy tooo bigg. + numeric oc; + distrseq.clear(); + for (epvector::const_iterator i2=add2begin; i2!=add2end; ++i2) { + // Don't push_back expairs which might have a rest that evaluates to a numeric, + // since that would violate an invariant of expairseq: + const ex rest = (new mul(i1->rest, i2->rest))->setflag(status_flags::dynallocated); + if (is_exactly_a(rest)) + oc += ex_to(rest).mul(ex_to(i1->coeff).mul(ex_to(i2->coeff))); + else + distrseq.push_back(expair(rest, ex_to(i1->coeff).mul_dyn(ex_to(i2->coeff)))); + } + tmp_accu += (new add(distrseq, oc))->setflag(status_flags::dynallocated); + } + last_expanded = tmp_accu; + + } else { + non_adds.push_back(split_ex_to_pair(last_expanded)); + last_expanded = cit->rest; + } + } else { + non_adds.push_back(*cit); + } + ++cit; + } + if (expanded_seqp) + delete expanded_seqp; + + // Now the only remaining thing to do is to multiply the factors which + // were not sums into the "last_expanded" sum + if (is_exactly_a(last_expanded)) { + const add & finaladd = ex_to(last_expanded); + exvector distrseq; + size_t n = finaladd.nops(); + distrseq.reserve(n); + for (size_t i=0; i + setflag(status_flags::dynallocated | (options == 0 ? status_flags::expanded : 0))); + } + return ((new add(distrseq))-> + setflag(status_flags::dynallocated | (options == 0 ? status_flags::expanded : 0))); + } + non_adds.push_back(split_ex_to_pair(last_expanded)); + return (new mul(non_adds, overall_coeff))-> + setflag(status_flags::dynallocated | (options == 0 ? status_flags::expanded : 0)); +} + + ////////// // new virtual functions which can be overridden by derived classes ////////// @@ -940,55 +940,47 @@ ex mul::expand(unsigned options) const // non-virtual functions in this class ////////// + +/** Member-wise expand the expairs representing this sequence. This must be + * overridden from expairseq::expandchildren() and done iteratively in order + * to allow for early cancallations and thus safe memory. + * + * @see mul::expand() + * @return pointer to epvector containing expanded representation or zero + * pointer, if sequence is unchanged. */ epvector * mul::expandchildren(unsigned options) const { - epvector::const_iterator last=seq.end(); - epvector::const_iterator cit=seq.begin(); - while (cit!=last) { - ex const & factor=recombine_pair_to_ex(*cit); - ex const & expanded_factor=factor.expand(options); - if (!are_ex_trivially_equal(factor,expanded_factor)) { - - // something changed, copy seq, eval and return it - epvector *s=new epvector; - s->reserve(seq.size()); - - // copy parts of seq which are known not to have changed - epvector::const_iterator cit2=seq.begin(); - while (cit2!=cit) { - s->push_back(*cit2); - ++cit2; - } - // copy first changed element - s->push_back(split_ex_to_pair(expanded_factor)); - ++cit2; - // copy rest - while (cit2!=last) { - s->push_back(split_ex_to_pair(recombine_pair_to_ex(*cit2).expand(options))); - ++cit2; - } - return s; - } - ++cit; - } - - return 0; // nothing has changed -} - -////////// -// static member variables -////////// - -// protected - -unsigned mul::precedence=50; - - -////////// -// global constants -////////// - -const mul some_mul; -type_info const & typeid_mul=typeid(some_mul); - - + const epvector::const_iterator last = seq.end(); + epvector::const_iterator cit = seq.begin(); + while (cit!=last) { + const ex & factor = recombine_pair_to_ex(*cit); + const ex & expanded_factor = factor.expand(options); + if (!are_ex_trivially_equal(factor,expanded_factor)) { + + // something changed, copy seq, eval and return it + epvector *s = new epvector; + s->reserve(seq.size()); + + // copy parts of seq which are known not to have changed + epvector::const_iterator cit2 = seq.begin(); + while (cit2!=cit) { + s->push_back(*cit2); + ++cit2; + } + // copy first changed element + s->push_back(split_ex_to_pair(expanded_factor)); + ++cit2; + // copy rest + while (cit2!=last) { + s->push_back(split_ex_to_pair(recombine_pair_to_ex(*cit2).expand(options))); + ++cit2; + } + return s; + } + ++cit; + } + + return 0; // nothing has changed +} + +} // namespace GiNaC