X-Git-Url: https://www.ginac.de/ginac.git//ginac.git?p=ginac.git;a=blobdiff_plain;f=ginac%2Fmul.cpp;h=2c8456510a44d35201f5659dec50f27f32206e02;hp=47f74f6f4c1b920050adf85a66154029bb42808c;hb=5ef801553eb39aed7bd2df9dd1aff9d752c3ea9d;hpb=3a63743e24046766b37c3d1bd38605542ee0a536 diff --git a/ginac/mul.cpp b/ginac/mul.cpp index 47f74f6f..2c845651 100644 --- a/ginac/mul.cpp +++ b/ginac/mul.cpp @@ -3,7 +3,7 @@ * Implementation of GiNaC's products of expressions. */ /* - * GiNaC Copyright (C) 1999-2001 Johannes Gutenberg University Mainz, Germany + * 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 @@ -23,11 +23,14 @@ #include #include #include +#include #include "mul.h" #include "add.h" #include "power.h" +#include "operators.h" #include "matrix.h" +#include "lst.h" #include "archive.h" #include "utils.h" @@ -36,7 +39,7 @@ namespace GiNaC { GINAC_IMPLEMENT_REGISTERED_CLASS(mul, expairseq) ////////// -// default ctor, dtor, copy ctor, assignment operator and helpers +// default constructor ////////// mul::mul() @@ -44,11 +47,8 @@ mul::mul() tinfo_key = TINFO_mul; } -DEFAULT_COPY(mul) -DEFAULT_DESTROY(mul) - ////////// -// other ctors +// other constructors ////////// // public @@ -119,7 +119,6 @@ DEFAULT_ARCHIVING(mul) ////////// // public - void mul::print(const print_context & c, unsigned level) const { if (is_a(c)) { @@ -141,25 +140,32 @@ void mul::print(const print_context & c, unsigned level) const while (it != itend) { // If the first argument is a negative integer power, it gets printed as "1.0/" - if (it == seq.begin() && ex_to(it->coeff).is_integer() && it->coeff.compare(_num0) < 0) { - if (is_a(c)) + bool needclosingparenthesis = false; + if (it == seq.begin() && it->coeff.info(info_flags::negint)) { + if (is_a(c)) { c.s << "recip("; - else + needclosingparenthesis = true; + } else c.s << "1.0/"; } // If the exponent is 1 or -1, it is left out - if (it->coeff.compare(_ex1) == 0 || it->coeff.compare(_num_1) == 0) + if (it->coeff.is_equal(_ex1) || it->coeff.is_equal(_ex_1)) it->rest.print(c, precedence()); - else { - // Outer parens around ex needed for broken gcc-2.95 parser: - (ex(power(it->rest, abs(ex_to(it->coeff))))).print(c, level); - } + 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 (ex_to(it->coeff).is_integer() && it->coeff.compare(_num0) < 0) + if (it->coeff.info(info_flags::negint)) c.s << "/"; else c.s << "*"; @@ -171,10 +177,8 @@ void mul::print(const print_context & c, unsigned level) const } else if (is_a(c)) { c.s << class_name() << '('; - unsigned end = nops(); - if (end) - op(0).print(c); - for (unsigned i=1; i(overall_coeff); + const numeric &coeff = ex_to(overall_coeff); if (coeff.csgn() == -1) c.s << '-'; if (!coeff.is_equal(_num1) && @@ -215,17 +217,51 @@ void mul::print(const print_context & c, unsigned level) const // Then proceed with the remaining factors epvector::const_iterator it = seq.begin(), itend = seq.end(); - while (it != itend) { - if (!first) { - if (is_a(c)) - c.s << ' '; + 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 - c.s << '*'; + 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 { - first = false; + + // 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; } - recombine_pair_to_ex(*it).print(c, precedence()); - ++it; } if (precedence() <= level) { @@ -355,7 +391,7 @@ ex mul::eval(int level) const GINAC_ASSERT((!is_exactly_a(i->rest)) || (!(ex_to(i->coeff).is_integer()))); GINAC_ASSERT(!(i->is_canonical_numeric())); - if (is_ex_exactly_of_type(recombine_pair_to_ex(*i), 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 */ @@ -384,7 +420,7 @@ ex mul::eval(int level) const // *(x;1) -> x return recombine_pair_to_ex(*(seq.begin())); } else if ((seq_size==1) && - is_ex_exactly_of_type((*seq.begin()).rest,add) && + 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); @@ -424,11 +460,11 @@ ex mul::evalf(int level) const return mul(s, overall_coeff.evalf(level)); } -ex mul::evalm(void) const +ex mul::evalm() const { // numeric*matrix if (seq.size() == 1 && seq[0].coeff.is_equal(_ex1) - && is_ex_of_type(seq[0].rest, matrix)) + && 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 @@ -444,7 +480,7 @@ ex mul::evalm(void) const while (i != end) { const ex &m = recombine_pair_to_ex(*i).evalm(); s->push_back(split_ex_to_pair(m)); - if (is_ex_of_type(m, matrix)) { + if (is_a(m)) { have_matrix = true; the_matrix = s->end() - 1; } @@ -464,19 +500,143 @@ ex mul::evalm(void) const return (new mul(s, overall_coeff))->setflag(status_flags::dynallocated); } -ex mul::simplify_ncmul(const exvector & v) const +ex mul::eval_ncmul(const exvector & v) const { if (seq.empty()) - return inherited::simplify_ncmul(v); + return inherited::eval_ncmul(v); - // Find first noncommutative element and call its simplify_ncmul() + // 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.simplify_ncmul(v); + return i->rest.eval_ncmul(v); ++i; } - return inherited::simplify_ncmul(v); + 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 @@ -485,7 +645,7 @@ ex mul::simplify_ncmul(const exvector & v) const * @see ex::diff */ ex mul::derivative(const symbol & s) const { - unsigned num = seq.size(); + size_t num = seq.size(); exvector addseq; addseq.reserve(num); @@ -509,12 +669,7 @@ int mul::compare_same_type(const basic & other) const return inherited::compare_same_type(other); } -bool mul::is_equal_same_type(const basic & other) const -{ - return inherited::is_equal_same_type(other); -} - -unsigned mul::return_type(void) const +unsigned mul::return_type() const { if (seq.empty()) { // mul without factors: should not happen, but commutes @@ -547,7 +702,7 @@ unsigned mul::return_type(void) const return all_commutative ? return_types::commutative : return_types::noncommutative; } -unsigned mul::return_type_tinfo(void) const +unsigned mul::return_type_tinfo() const { if (seq.empty()) return tinfo_key; // mul without factors: should not happen @@ -575,9 +730,9 @@ ex mul::thisexpairseq(epvector * vp, const ex & oc) const expair mul::split_ex_to_pair(const ex & e) const { - if (is_ex_exactly_of_type(e,power)) { + if (is_exactly_a(e)) { const power & powerref = ex_to(e); - if (is_ex_exactly_of_type(powerref.exponent,numeric)) + if (is_exactly_a(powerref.exponent)) return expair(powerref.basis,powerref.exponent); } return expair(e,_ex1); @@ -588,11 +743,11 @@ expair mul::combine_ex_with_coeff_to_pair(const ex & e, { // to avoid duplication of power simplification rules, // we create a temporary power object - // otherwise it would be hard to correctly simplify + // otherwise it would be hard to correctly evaluate // expression like (4^(1/3))^(3/2) - if (are_ex_trivially_equal(c,_ex1)) + if (c.is_equal(_ex1)) return split_ex_to_pair(e); - + return split_ex_to_pair(power(e,c)); } @@ -601,11 +756,11 @@ expair mul::combine_pair_with_coeff_to_pair(const expair & p, { // to avoid duplication of power simplification rules, // we create a temporary power object - // otherwise it would be hard to correctly simplify + // otherwise it would be hard to correctly evaluate // expression like (4^(1/3))^(3/2) - if (are_ex_trivially_equal(c,_ex1)) + if (c.is_equal(_ex1)) return p; - + return split_ex_to_pair(power(recombine_pair_to_ex(p),c)); } @@ -614,25 +769,25 @@ ex mul::recombine_pair_to_ex(const expair & p) const if (ex_to(p.coeff).is_equal(_num1)) return p.rest; else - return power(p.rest,p.coeff); + 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((*it).coeff).is_integer()) { + 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_ex_exactly_of_type((*it).rest,numeric)) { - expair ep=split_ex_to_pair(recombine_pair_to_ex(*it)); + 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 (ex_to((*it).coeff).is_equal(_num1)) { + if (it->coeff.is_equal(_ex1)) { // combined pair has coeff 1 and must be moved to the end return true; } @@ -640,7 +795,7 @@ bool mul::expair_needs_further_processing(epp it) return false; } -ex mul::default_overall_coeff(void) const +ex mul::default_overall_coeff() const { return _ex1; } @@ -684,23 +839,63 @@ ex mul::expand(unsigned options) const non_adds.reserve(expanded_seq.size()); epvector::const_iterator cit = expanded_seq.begin(), last = expanded_seq.end(); while (cit != last) { - if (is_ex_exactly_of_type(cit->rest, add) && + if (is_exactly_a(cit->rest) && (cit->coeff.is_equal(_ex1))) { ++number_of_adds; - if (is_ex_exactly_of_type(last_expanded, add)) { - const add & add1 = ex_to(last_expanded); - const add & add2 = ex_to(cit->rest); - int n1 = add1.nops(); - int n2 = add2.nops(); - exvector distrseq; - distrseq.reserve(n1*n2); - for (int i1=0; i1(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 = (new add(distrseq))-> - setflag(status_flags::dynallocated | (options == 0 ? status_flags::expanded : 0)); + last_expanded = tmp_accu; + } else { non_adds.push_back(split_ex_to_pair(last_expanded)); last_expanded = cit->rest; @@ -715,12 +910,12 @@ ex mul::expand(unsigned options) const // Now the only remaining thing to do is to multiply the factors which // were not sums into the "last_expanded" sum - if (is_ex_exactly_of_type(last_expanded, add)) { + if (is_exactly_a(last_expanded)) { const add & finaladd = ex_to(last_expanded); exvector distrseq; - int n = finaladd.nops(); + size_t n = finaladd.nops(); distrseq.reserve(n); - for (int i=0; i