- gcd(): cofactor computation is faster in partially factorized case
[ginac.git] / ginac / normal.cpp
index fe4eb3ccc6b3b6b2e1a8667c5b0a1c89ee2a6037..f57e4f0dbb60b31c3fc7bb053b905881ffee24f2 100644 (file)
@@ -4,9 +4,10 @@
  *  multivariate polynomials and rational functions.
  *  These functions include polynomial quotient and remainder, GCD and LCM
  *  computation, square-free factorization and rational function normalization.
+ */
 
- *
- *  GiNaC Copyright (C) 1999 Johannes Gutenberg University Mainz, Germany
+/*
+ *  GiNaC Copyright (C) 1999-2000 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
@@ -24,6 +25,8 @@
  */
 
 #include <stdexcept>
+#include <algorithm>
+#include <map>
 
 #include "normal.h"
 #include "basic.h"
 #include "numeric.h"
 #include "power.h"
 #include "relational.h"
-#include "series.h"
+#include "pseries.h"
 #include "symbol.h"
+#include "utils.h"
+
+#ifndef NO_GINAC_NAMESPACE
+namespace GiNaC {
+#endif // ndef NO_GINAC_NAMESPACE
 
 // If comparing expressions (ex::compare()) is fast, you can set this to 1.
 // Some routines like quo(), rem() and gcd() will then return a quick answer
@@ -66,7 +74,7 @@ static bool get_first_symbol(const ex &e, const symbol *&x)
         x = static_cast<symbol *>(e.bp);
         return true;
     } else if (is_ex_exactly_of_type(e, add) || is_ex_exactly_of_type(e, mul)) {
-        for (int i=0; i<e.nops(); i++)
+        for (unsigned i=0; i<e.nops(); i++)
             if (get_first_symbol(e.op(i), x))
                 return true;
     } else if (is_ex_exactly_of_type(e, power)) {
@@ -81,8 +89,6 @@ static bool get_first_symbol(const ex &e, const symbol *&x)
  *  Statistical information about symbols in polynomials
  */
 
-#include <algorithm>
-
 /** This structure holds information about the highest and lowest degrees
  *  in which a symbol appears in two multivariate polynomials "a" and "b".
  *  A vector of these structures with information about all symbols in
@@ -135,7 +141,7 @@ static void collect_symbols(const ex &e, sym_desc_vec &v)
     if (is_ex_exactly_of_type(e, symbol)) {
         add_symbol(static_cast<symbol *>(e.bp), v);
     } else if (is_ex_exactly_of_type(e, add) || is_ex_exactly_of_type(e, mul)) {
-        for (int i=0; i<e.nops(); i++)
+        for (unsigned i=0; i<e.nops(); i++)
             collect_symbols(e.op(i), v);
     } else if (is_ex_exactly_of_type(e, power)) {
         collect_symbols(e.op(0), v);
@@ -184,28 +190,56 @@ static numeric lcmcoeff(const ex &e, const numeric &l)
 {
     if (e.info(info_flags::rational))
         return lcm(ex_to_numeric(e).denom(), l);
-    else if (is_ex_exactly_of_type(e, add) || is_ex_exactly_of_type(e, mul)) {
-        numeric c = numONE();
-        for (int i=0; i<e.nops(); i++) {
+    else if (is_ex_exactly_of_type(e, add)) {
+        numeric c = _num1();
+        for (unsigned i=0; i<e.nops(); i++)
             c = lcmcoeff(e.op(i), c);
-        }
+        return lcm(c, l);
+    } else if (is_ex_exactly_of_type(e, mul)) {
+        numeric c = _num1();
+        for (unsigned i=0; i<e.nops(); i++)
+            c *= lcmcoeff(e.op(i), _num1());
         return lcm(c, l);
     } else if (is_ex_exactly_of_type(e, power))
-        return lcmcoeff(e.op(0), l);
+        return pow(lcmcoeff(e.op(0), l), ex_to_numeric(e.op(1)));
     return l;
 }
 
 /** Compute LCM of denominators of coefficients of a polynomial.
  *  Given a polynomial with rational coefficients, this function computes
  *  the LCM of the denominators of all coefficients. This can be used
- *  To bring a polynomial from Q[X] to Z[X].
+ *  to bring a polynomial from Q[X] to Z[X].
  *
- *  @param e  multivariate polynomial
+ *  @param e  multivariate polynomial (need not be expanded)
  *  @return LCM of denominators of coefficients */
 
 static numeric lcm_of_coefficients_denominators(const ex &e)
 {
-    return lcmcoeff(e.expand(), numONE());
+    return lcmcoeff(e, _num1());
+}
+
+/** Bring polynomial from Q[X] to Z[X] by multiplying in the previously
+ *  determined LCM of the coefficient's denominators.
+ *
+ *  @param e  multivariate polynomial (need not be expanded)
+ *  @param lcm  LCM to multiply in */
+
+static ex multiply_lcm(const ex &e, const ex &lcm)
+{
+       if (is_ex_exactly_of_type(e, mul)) {
+               ex c = _ex1();
+               for (int i=0; i<e.nops(); i++)
+                       c *= multiply_lcm(e.op(i), lcmcoeff(e.op(i), _num1()));
+               return c;
+       } else if (is_ex_exactly_of_type(e, add)) {
+               ex c = _ex0();
+               for (int i=0; i<e.nops(); i++)
+                       c += multiply_lcm(e.op(i), lcm);
+               return c;
+       } else if (is_ex_exactly_of_type(e, power)) {
+               return pow(multiply_lcm(e.op(0), pow(lcm, 1/e.op(1))), e.op(1));
+       } else
+               return e * lcm;
 }
 
 
@@ -217,13 +251,13 @@ static numeric lcm_of_coefficients_denominators(const ex &e)
 
 numeric ex::integer_content(void) const
 {
-    ASSERT(bp!=0);
+    GINAC_ASSERT(bp!=0);
     return bp->integer_content();
 }
 
 numeric basic::integer_content(void) const
 {
-    return numONE();
+    return _num1();
 }
 
 numeric numeric::integer_content(void) const
@@ -235,29 +269,29 @@ numeric add::integer_content(void) const
 {
     epvector::const_iterator it = seq.begin();
     epvector::const_iterator itend = seq.end();
-    numeric c = numZERO();
+    numeric c = _num0();
     while (it != itend) {
-        ASSERT(!is_ex_exactly_of_type(it->rest,numeric));
-        ASSERT(is_ex_exactly_of_type(it->coeff,numeric));
+        GINAC_ASSERT(!is_ex_exactly_of_type(it->rest,numeric));
+        GINAC_ASSERT(is_ex_exactly_of_type(it->coeff,numeric));
         c = gcd(ex_to_numeric(it->coeff), c);
         it++;
     }
-    ASSERT(is_ex_exactly_of_type(overall_coeff,numeric));
+    GINAC_ASSERT(is_ex_exactly_of_type(overall_coeff,numeric));
     c = gcd(ex_to_numeric(overall_coeff),c);
     return c;
 }
 
 numeric mul::integer_content(void) const
 {
-#ifdef DOASSERT
+#ifdef DO_GINAC_ASSERT
     epvector::const_iterator it = seq.begin();
     epvector::const_iterator itend = seq.end();
     while (it != itend) {
-        ASSERT(!is_ex_exactly_of_type(recombine_pair_to_ex(*it),numeric));
+        GINAC_ASSERT(!is_ex_exactly_of_type(recombine_pair_to_ex(*it),numeric));
         ++it;
     }
-#endif // def DOASSERT
-    ASSERT(is_ex_exactly_of_type(overall_coeff,numeric));
+#endif // def DO_GINAC_ASSERT
+    GINAC_ASSERT(is_ex_exactly_of_type(overall_coeff,numeric));
     return abs(ex_to_numeric(overall_coeff));
 }
 
@@ -284,13 +318,13 @@ ex quo(const ex &a, const ex &b, const symbol &x, bool check_args)
         return a / b;
 #if FAST_COMPARE
     if (a.is_equal(b))
-        return exONE();
+        return _ex1();
 #endif
     if (check_args && (!a.info(info_flags::rational_polynomial) || !b.info(info_flags::rational_polynomial)))
         throw(std::invalid_argument("quo: arguments must be polynomials over the rationals"));
 
     // Polynomial long division
-    ex q = exZERO();
+    ex q = _ex0();
     ex r = a.expand();
     if (r.is_zero())
         return r;
@@ -333,13 +367,13 @@ ex rem(const ex &a, const ex &b, const symbol &x, bool check_args)
         throw(std::overflow_error("rem: division by zero"));
     if (is_ex_exactly_of_type(a, numeric)) {
         if  (is_ex_exactly_of_type(b, numeric))
-            return exZERO();
+            return _ex0();
         else
             return b;
     }
 #if FAST_COMPARE
     if (a.is_equal(b))
-        return exZERO();
+        return _ex0();
 #endif
     if (check_args && (!a.info(info_flags::rational_polynomial) || !b.info(info_flags::rational_polynomial)))
         throw(std::invalid_argument("rem: arguments must be polynomials over the rationals"));
@@ -385,7 +419,7 @@ ex prem(const ex &a, const ex &b, const symbol &x, bool check_args)
         throw(std::overflow_error("prem: division by zero"));
     if (is_ex_exactly_of_type(a, numeric)) {
         if (is_ex_exactly_of_type(b, numeric))
-            return exZERO();
+            return _ex0();
         else
             return b;
     }
@@ -401,18 +435,18 @@ ex prem(const ex &a, const ex &b, const symbol &x, bool check_args)
     if (bdeg <= rdeg) {
         blcoeff = eb.coeff(x, bdeg);
         if (bdeg == 0)
-            eb = exZERO();
+            eb = _ex0();
         else
             eb -= blcoeff * power(x, bdeg);
     } else
-        blcoeff = exONE();
+        blcoeff = _ex1();
 
     int delta = rdeg - bdeg + 1, i = 0;
     while (rdeg >= bdeg && !r.is_zero()) {
         ex rlcoeff = r.coeff(x, rdeg);
         ex term = (power(x, rdeg - bdeg) * eb * rlcoeff).expand();
         if (rdeg == 0)
-            r = exZERO();
+            r = _ex0();
         else
             r -= rlcoeff * power(x, rdeg);
         r = (blcoeff * r).expand() - term;
@@ -435,7 +469,7 @@ ex prem(const ex &a, const ex &b, const symbol &x, bool check_args)
 
 bool divide(const ex &a, const ex &b, ex &q, bool check_args)
 {
-    q = exZERO();
+    q = _ex0();
     if (b.is_zero())
         throw(std::overflow_error("divide: division by zero"));
     if (is_ex_exactly_of_type(b, numeric)) {
@@ -445,7 +479,7 @@ bool divide(const ex &a, const ex &b, ex &q, bool check_args)
         return false;
 #if FAST_COMPARE
     if (a.is_equal(b)) {
-        q = exONE();
+        q = _ex1();
         return true;
     }
 #endif
@@ -488,8 +522,6 @@ bool divide(const ex &a, const ex &b, ex &q, bool check_args)
  *  Remembering
  */
 
-#include <map>
-
 typedef pair<ex, ex> ex2;
 typedef pair<ex, bool> exbool;
 
@@ -522,10 +554,10 @@ typedef map<ex2, exbool, ex2_less> ex2_exbool_remember;
  *  @see get_symbol_stats, heur_gcd */
 static bool divide_in_z(const ex &a, const ex &b, ex &q, sym_desc_vec::const_iterator var)
 {
-    q = exZERO();
+    q = _ex0();
     if (b.is_zero())
         throw(std::overflow_error("divide_in_z: division by zero"));
-    if (b.is_equal(exONE())) {
+    if (b.is_equal(_ex1())) {
         q = a;
         return true;
     }
@@ -538,7 +570,7 @@ static bool divide_in_z(const ex &a, const ex &b, ex &q, sym_desc_vec::const_ite
     }
 #if FAST_COMPARE
     if (a.is_equal(b)) {
-        q = exONE();
+        q = _ex1();
         return true;
     }
 #endif
@@ -598,19 +630,19 @@ static bool divide_in_z(const ex &a, const ex &b, ex &q, sym_desc_vec::const_ite
     // Compute values at evaluation points 0..adeg
     vector<numeric> alpha; alpha.reserve(adeg + 1);
     exvector u; u.reserve(adeg + 1);
-    numeric point = numZERO();
+    numeric point = _num0();
     ex c;
     for (i=0; i<=adeg; i++) {
         ex bs = b.subs(*x == point);
         while (bs.is_zero()) {
-            point += numONE();
+            point += _num1();
             bs = b.subs(*x == point);
         }
         if (!divide_in_z(a.subs(*x == point), bs, c, var+1))
             return false;
         alpha.push_back(point);
         u.push_back(c);
-        point += numONE();
+        point += _num1();
     }
 
     // Compute inverses
@@ -662,7 +694,7 @@ ex ex::unit(const symbol &x) const
 {
     ex c = expand().lcoeff(x);
     if (is_ex_exactly_of_type(c, numeric))
-        return c < exZERO() ? exMINUSONE() : exONE();
+        return c < _ex0() ? _ex_1() : _ex1();
     else {
         const symbol *y;
         if (get_first_symbol(c, y))
@@ -683,12 +715,12 @@ ex ex::unit(const symbol &x) const
 ex ex::content(const symbol &x) const
 {
     if (is_zero())
-        return exZERO();
+        return _ex0();
     if (is_ex_exactly_of_type(*this, numeric))
         return info(info_flags::negative) ? -*this : *this;
     ex e = expand();
     if (e.is_zero())
-        return exZERO();
+        return _ex0();
 
     // First, try the integer content
     ex c = e.integer_content();
@@ -702,7 +734,7 @@ ex ex::content(const symbol &x) const
     int ldeg = e.ldegree(x);
     if (deg == ldeg)
         return e.lcoeff(x) / e.unit(x);
-    c = exZERO();
+    c = _ex0();
     for (int i=ldeg; i<=deg; i++)
         c = gcd(e.coeff(x, i), c, NULL, NULL, false);
     return c;
@@ -719,13 +751,13 @@ ex ex::content(const symbol &x) const
 ex ex::primpart(const symbol &x) const
 {
     if (is_zero())
-        return exZERO();
+        return _ex0();
     if (is_ex_exactly_of_type(*this, numeric))
-        return exONE();
+        return _ex1();
 
     ex c = content(x);
     if (c.is_zero())
-        return exZERO();
+        return _ex0();
     ex u = unit(x);
     if (is_ex_exactly_of_type(c, numeric))
         return *this / (c * u);
@@ -745,11 +777,11 @@ ex ex::primpart(const symbol &x) const
 ex ex::primpart(const symbol &x, const ex &c) const
 {
     if (is_zero())
-        return exZERO();
+        return _ex0();
     if (c.is_zero())
-        return exZERO();
+        return _ex0();
     if (is_ex_exactly_of_type(*this, numeric))
-        return exONE();
+        return _ex1();
 
     ex u = unit(x);
     if (is_ex_exactly_of_type(c, numeric))
@@ -800,7 +832,7 @@ static ex sr_gcd(const ex &a, const ex &b, const symbol *x)
     d = d.primpart(*x, cont_d);
 
     // First element of subresultant sequence
-    ex r = exZERO(), ri = exONE(), psi = exONE();
+    ex r = _ex0(), ri = _ex1(), psi = _ex1();
     int delta = cdeg - ddeg;
 
     for (;;) {
@@ -840,13 +872,13 @@ static ex sr_gcd(const ex &a, const ex &b, const symbol *x)
 
 numeric ex::max_coefficient(void) const
 {
-    ASSERT(bp!=0);
+    GINAC_ASSERT(bp!=0);
     return bp->max_coefficient();
 }
 
 numeric basic::max_coefficient(void) const
 {
-    return numONE();
+    return _num1();
 }
 
 numeric numeric::max_coefficient(void) const
@@ -858,11 +890,11 @@ numeric add::max_coefficient(void) const
 {
     epvector::const_iterator it = seq.begin();
     epvector::const_iterator itend = seq.end();
-    ASSERT(is_ex_exactly_of_type(overall_coeff,numeric));
+    GINAC_ASSERT(is_ex_exactly_of_type(overall_coeff,numeric));
     numeric cur_max = abs(ex_to_numeric(overall_coeff));
     while (it != itend) {
         numeric a;
-        ASSERT(!is_ex_exactly_of_type(it->rest,numeric));
+        GINAC_ASSERT(!is_ex_exactly_of_type(it->rest,numeric));
         a = abs(ex_to_numeric(it->coeff));
         if (a > cur_max)
             cur_max = a;
@@ -873,15 +905,15 @@ numeric add::max_coefficient(void) const
 
 numeric mul::max_coefficient(void) const
 {
-#ifdef DOASSERT
+#ifdef DO_GINAC_ASSERT
     epvector::const_iterator it = seq.begin();
     epvector::const_iterator itend = seq.end();
     while (it != itend) {
-        ASSERT(!is_ex_exactly_of_type(recombine_pair_to_ex(*it),numeric));
+        GINAC_ASSERT(!is_ex_exactly_of_type(recombine_pair_to_ex(*it),numeric));
         it++;
     }
-#endif // def DOASSERT
-    ASSERT(is_ex_exactly_of_type(overall_coeff,numeric));
+#endif // def DO_GINAC_ASSERT
+    GINAC_ASSERT(is_ex_exactly_of_type(overall_coeff,numeric));
     return abs(ex_to_numeric(overall_coeff));
 }
 
@@ -896,7 +928,7 @@ numeric mul::max_coefficient(void) const
 
 ex ex::smod(const numeric &xi) const
 {
-    ASSERT(bp!=0);
+    GINAC_ASSERT(bp!=0);
     return bp->smod(xi);
 }
 
@@ -907,7 +939,11 @@ ex basic::smod(const numeric &xi) const
 
 ex numeric::smod(const numeric &xi) const
 {
+#ifndef NO_GINAC_NAMESPACE
+    return GiNaC::smod(*this, xi);
+#else // ndef NO_GINAC_NAMESPACE
     return ::smod(*this, xi);
+#endif // ndef NO_GINAC_NAMESPACE
 }
 
 ex add::smod(const numeric &xi) const
@@ -917,37 +953,49 @@ ex add::smod(const numeric &xi) const
     epvector::const_iterator it = seq.begin();
     epvector::const_iterator itend = seq.end();
     while (it != itend) {
-        ASSERT(!is_ex_exactly_of_type(it->rest,numeric));
+        GINAC_ASSERT(!is_ex_exactly_of_type(it->rest,numeric));
+#ifndef NO_GINAC_NAMESPACE
+        numeric coeff = GiNaC::smod(ex_to_numeric(it->coeff), xi);
+#else // ndef NO_GINAC_NAMESPACE
         numeric coeff = ::smod(ex_to_numeric(it->coeff), xi);
+#endif // ndef NO_GINAC_NAMESPACE
         if (!coeff.is_zero())
             newseq.push_back(expair(it->rest, coeff));
         it++;
     }
-    ASSERT(is_ex_exactly_of_type(overall_coeff,numeric));
+    GINAC_ASSERT(is_ex_exactly_of_type(overall_coeff,numeric));
+#ifndef NO_GINAC_NAMESPACE
+    numeric coeff = GiNaC::smod(ex_to_numeric(overall_coeff), xi);
+#else // ndef NO_GINAC_NAMESPACE
     numeric coeff = ::smod(ex_to_numeric(overall_coeff), xi);
+#endif // ndef NO_GINAC_NAMESPACE
     return (new add(newseq,coeff))->setflag(status_flags::dynallocated);
 }
 
 ex mul::smod(const numeric &xi) const
 {
-#ifdef DOASSERT
+#ifdef DO_GINAC_ASSERT
     epvector::const_iterator it = seq.begin();
     epvector::const_iterator itend = seq.end();
     while (it != itend) {
-        ASSERT(!is_ex_exactly_of_type(recombine_pair_to_ex(*it),numeric));
+        GINAC_ASSERT(!is_ex_exactly_of_type(recombine_pair_to_ex(*it),numeric));
         it++;
     }
-#endif // def DOASSERT
+#endif // def DO_GINAC_ASSERT
     mul * mulcopyp=new mul(*this);
-    ASSERT(is_ex_exactly_of_type(overall_coeff,numeric));
-    mulcopyp->overall_coeff=::smod(ex_to_numeric(overall_coeff),xi);
+    GINAC_ASSERT(is_ex_exactly_of_type(overall_coeff,numeric));
+#ifndef NO_GINAC_NAMESPACE
+    mulcopyp->overall_coeff = GiNaC::smod(ex_to_numeric(overall_coeff),xi);
+#else // ndef NO_GINAC_NAMESPACE
+    mulcopyp->overall_coeff = ::smod(ex_to_numeric(overall_coeff),xi);
+#endif // ndef NO_GINAC_NAMESPACE
     mulcopyp->clearflag(status_flags::evaluated);
     mulcopyp->clearflag(status_flags::hash_calculated);
     return mulcopyp->setflag(status_flags::dynallocated);
 }
 
 
-/** Exception thrown by heur_gcd() to signal failure */
+/** Exception thrown by heur_gcd() to signal failure. */
 class gcdheu_failed {};
 
 /** Compute GCD of multivariate polynomials using the heuristic GCD algorithm.
@@ -994,9 +1042,9 @@ static ex heur_gcd(const ex &a, const ex &b, ex *ca, ex *cb, sym_desc_vec::const
     numeric mp = p.max_coefficient(), mq = q.max_coefficient();
     numeric xi;
     if (mp > mq)
-        xi = mq * numTWO() + numTWO();
+        xi = mq * _num2() + _num2();
     else
-        xi = mp * numTWO() + numTWO();
+        xi = mp * _num2() + _num2();
 
     // 6 tries maximum
     for (int t=0; t<6; t++) {
@@ -1008,7 +1056,7 @@ static ex heur_gcd(const ex &a, const ex &b, ex *ca, ex *cb, sym_desc_vec::const
         if (!is_ex_exactly_of_type(gamma, fail)) {
 
             // Reconstruct polynomial from GCD of mapped polynomials
-            ex g = exZERO();
+            ex g = _ex0();
             numeric rxi = xi.inverse();
             for (int i=0; !gamma.is_zero(); i++) {
                 ex gi = gamma.smod(xi);
@@ -1023,7 +1071,7 @@ static ex heur_gcd(const ex &a, const ex &b, ex *ca, ex *cb, sym_desc_vec::const
             if (divide_in_z(p, g, ca ? *ca : dummy, var) && divide_in_z(q, g, cb ? *cb : dummy, var)) {
                 g *= gc;
                 ex lc = g.lcoeff(*x);
-                if (is_ex_exactly_of_type(lc, numeric) && lc.compare(exZERO()) < 0)
+                if (is_ex_exactly_of_type(lc, numeric) && lc.compare(_ex0()) < 0)
                     return -g;
                 else
                     return g;
@@ -1048,48 +1096,86 @@ static ex heur_gcd(const ex &a, const ex &b, ex *ca, ex *cb, sym_desc_vec::const
 
 ex gcd(const ex &a, const ex &b, ex *ca, ex *cb, bool check_args)
 {
+       // Partially factored cases (to avoid expanding large expressions)
+       if (is_ex_exactly_of_type(a, mul)) {
+               if (is_ex_exactly_of_type(b, mul) && b.nops() > a.nops())
+                       goto factored_b;
+factored_a:
+               ex g = _ex1();
+               ex acc_ca = _ex1();
+               ex part_b = b;
+               for (int i=0; i<a.nops(); i++) {
+                       ex part_ca, part_cb;
+                       g *= gcd(a.op(i), part_b, &part_ca, &part_cb, check_args);
+                       acc_ca *= part_ca;
+                       part_b = part_cb;
+               }
+               if (ca)
+                       *ca = acc_ca;
+               if (cb)
+                       *cb = part_b;
+               return g;
+       } else if (is_ex_exactly_of_type(b, mul)) {
+               if (is_ex_exactly_of_type(a, mul) && a.nops() > b.nops())
+                       goto factored_a;
+factored_b:
+               ex g = _ex1();
+               ex acc_cb = _ex1();
+               ex part_a = a;
+               for (int i=0; i<b.nops(); i++) {
+                       ex part_ca, part_cb;
+                       g *= gcd(part_a, b.op(i), &part_ca, &part_cb, check_args);
+                       acc_cb *= part_cb;
+                       part_a = part_ca;
+               }
+               if (ca)
+                       *ca = part_a;
+               if (cb)
+                       *cb = acc_cb;
+               return g;
+       }
+
     // Some trivial cases
-    if (a.is_zero()) {
+       ex aex = a.expand(), bex = b.expand();
+    if (aex.is_zero()) {
         if (ca)
-            *ca = exZERO();
+            *ca = _ex0();
         if (cb)
-            *cb = exONE();
+            *cb = _ex1();
         return b;
     }
-    if (b.is_zero()) {
+    if (bex.is_zero()) {
         if (ca)
-            *ca = exONE();
+            *ca = _ex1();
         if (cb)
-            *cb = exZERO();
+            *cb = _ex0();
         return a;
     }
-    if (a.is_equal(exONE()) || b.is_equal(exONE())) {
+    if (aex.is_equal(_ex1()) || bex.is_equal(_ex1())) {
         if (ca)
             *ca = a;
         if (cb)
             *cb = b;
-        return exONE();
+        return _ex1();
     }
 #if FAST_COMPARE
     if (a.is_equal(b)) {
         if (ca)
-            *ca = exONE();
+            *ca = _ex1();
         if (cb)
-            *cb = exONE();
+            *cb = _ex1();
         return a;
     }
 #endif
-    if (is_ex_exactly_of_type(a, numeric) && is_ex_exactly_of_type(b, numeric)) {
-        numeric g = gcd(ex_to_numeric(a), ex_to_numeric(b));
+    if (is_ex_exactly_of_type(aex, numeric) && is_ex_exactly_of_type(bex, numeric)) {
+        numeric g = gcd(ex_to_numeric(aex), ex_to_numeric(bex));
         if (ca)
-            *ca = ex_to_numeric(a) / g;
+            *ca = ex_to_numeric(aex) / g;
         if (cb)
-            *cb = ex_to_numeric(b) / g;
+            *cb = ex_to_numeric(bex) / g;
         return g;
     }
     if (check_args && !a.info(info_flags::rational_polynomial) || !b.info(info_flags::rational_polynomial)) {
-        cerr << "a=" << a << endl;
-        cerr << "b=" << b << endl;
         throw(std::invalid_argument("gcd: arguments must be polynomials over the rationals"));
     }
 
@@ -1108,40 +1194,40 @@ ex gcd(const ex &a, const ex &b, ex *ca, ex *cb, bool check_args)
     if (min_ldeg > 0) {
         ex common = power(*x, min_ldeg);
 //clog << "trivial common factor " << common << endl;
-        return gcd((a / common).expand(), (b / common).expand(), ca, cb, false) * common;
+        return gcd((aex / common).expand(), (bex / common).expand(), ca, cb, false) * common;
     }
 
     // Try to eliminate variables
     if (var->deg_a == 0) {
 //clog << "eliminating variable " << *x << " from b" << endl;
-        ex c = b.content(*x);
-        ex g = gcd(a, c, ca, cb, false);
+        ex c = bex.content(*x);
+        ex g = gcd(aex, c, ca, cb, false);
         if (cb)
-            *cb *= b.unit(*x) * b.primpart(*x, c);
+            *cb *= bex.unit(*x) * bex.primpart(*x, c);
         return g;
     } else if (var->deg_b == 0) {
 //clog << "eliminating variable " << *x << " from a" << endl;
-        ex c = a.content(*x);
-        ex g = gcd(c, b, ca, cb, false);
+        ex c = aex.content(*x);
+        ex g = gcd(c, bex, ca, cb, false);
         if (ca)
-            *ca *= a.unit(*x) * a.primpart(*x, c);
+            *ca *= aex.unit(*x) * aex.primpart(*x, c);
         return g;
     }
 
     // Try heuristic algorithm first, fall back to PRS if that failed
     ex g;
     try {
-        g = heur_gcd(a.expand(), b.expand(), ca, cb, var);
+        g = heur_gcd(aex, bex, ca, cb, var);
     } catch (gcdheu_failed) {
         g = *new ex(fail());
     }
     if (is_ex_exactly_of_type(g, fail)) {
-//clog << "heuristics failed\n";
-        g = sr_gcd(a, b, x);
+//clog << "heuristics failed" << endl;
+        g = sr_gcd(aex, bex, x);
         if (ca)
-            divide(a, g, *ca, false);
+            divide(aex, g, *ca, false);
         if (cb)
-            divide(b, g, *cb, false);
+            divide(bex, g, *cb, false);
     }
     return g;
 }
@@ -1179,8 +1265,8 @@ static ex univariate_gcd(const ex &a, const ex &b, const symbol &x)
         return b;
     if (b.is_zero())
         return a;
-    if (a.is_equal(exONE()) || b.is_equal(exONE()))
-        return exONE();
+    if (a.is_equal(_ex1()) || b.is_equal(_ex1()))
+        return _ex1();
     if (is_ex_of_type(a, numeric) && is_ex_of_type(b, numeric))
         return gcd(ex_to_numeric(a), ex_to_numeric(b));
     if (!a.info(info_flags::rational_polynomial) || !b.info(info_flags::rational_polynomial))
@@ -1215,11 +1301,11 @@ static ex univariate_gcd(const ex &a, const ex &b, const symbol &x)
 ex sqrfree(const ex &a, const symbol &x)
 {
     int i = 1;
-    ex res = exONE();
+    ex res = _ex1();
     ex b = a.diff(x);
     ex c = univariate_gcd(a, b, x);
     ex w;
-    if (c.is_equal(exONE())) {
+    if (c.is_equal(_ex1())) {
         w = a;
     } else {
         w = quo(a, c, x);
@@ -1248,7 +1334,7 @@ ex sqrfree(const ex &a, const symbol &x)
 static ex replace_with_symbol(const ex &e, lst &sym_lst, lst &repl_lst)
 {
     // Expression already in repl_lst? Then return the assigned symbol
-    for (int i=0; i<repl_lst.nops(); i++)
+    for (unsigned i=0; i<repl_lst.nops(); i++)
         if (repl_lst.op(i).is_equal(e))
             return sym_lst.op(i);
 
@@ -1290,50 +1376,48 @@ ex numeric::normal(lst &sym_lst, lst &repl_lst, int level) const
     if (is_real())
         if (is_rational())
             return *this;
-               else
-                   return replace_with_symbol(*this, sym_lst, repl_lst);
+        else
+            return replace_with_symbol(*this, sym_lst, repl_lst);
     else { // complex
         numeric re = real(), im = imag();
-               ex re_ex = re.is_rational() ? re : replace_with_symbol(re, sym_lst, repl_lst);
-               ex im_ex = im.is_rational() ? im : replace_with_symbol(im, sym_lst, repl_lst);
-               return re_ex + im_ex * replace_with_symbol(I, sym_lst, repl_lst);
-       }
+        ex re_ex = re.is_rational() ? re : replace_with_symbol(re, sym_lst, repl_lst);
+        ex im_ex = im.is_rational() ? im : replace_with_symbol(im, sym_lst, repl_lst);
+        return re_ex + im_ex * replace_with_symbol(I, sym_lst, repl_lst);
+    }
 }
 
 
-/*
- *  Helper function for fraction cancellation (returns cancelled fraction n/d)
- */
-
+/** Fraction cancellation.
+ *  @param n  numerator
+ *  @param d  denominator
+ *  @return cancelled fraction n/d */
 static ex frac_cancel(const ex &n, const ex &d)
 {
     ex num = n;
     ex den = d;
-    ex pre_factor = exONE();
+    ex pre_factor = _ex1();
 
     // Handle special cases where numerator or denominator is 0
     if (num.is_zero())
-        return exZERO();
+        return _ex0();
     if (den.expand().is_zero())
         throw(std::overflow_error("frac_cancel: division by zero in frac_cancel"));
 
     // More special cases
     if (is_ex_exactly_of_type(den, numeric))
         return num / den;
-    if (num.is_zero())
-        return exZERO();
 
     // Bring numerator and denominator to Z[X] by multiplying with
     // LCM of all coefficients' denominators
     ex num_lcm = lcm_of_coefficients_denominators(num);
     ex den_lcm = lcm_of_coefficients_denominators(den);
-    num *= num_lcm;
-    den *= den_lcm;
+       num = multiply_lcm(num, num_lcm);
+       den = multiply_lcm(den, den_lcm);
     pre_factor = den_lcm / num_lcm;
 
     // Cancel GCD from numerator and denominator
     ex cnum, cden;
-    if (gcd(num, den, &cnum, &cden, false) != exONE()) {
+    if (gcd(num, den, &cnum, &cden, false) != _ex1()) {
                num = cnum;
                den = cden;
        }
@@ -1342,9 +1426,9 @@ static ex frac_cancel(const ex &n, const ex &d)
        // as defined by get_first_symbol() is made positive)
        const symbol *x;
        if (get_first_symbol(den, x)) {
-               if (den.unit(*x).compare(exZERO()) < 0) {
-                       num *= exMINUSONE();
-                       den *= exMINUSONE();
+               if (den.unit(*x).compare(_ex0()) < 0) {
+                       num *= _ex_1();
+                       den *= _ex_1();
                }
        }
     return pre_factor * num / den;
@@ -1376,7 +1460,7 @@ ex add::normal(lst &sym_lst, lst &repl_lst, int level) const
     o.push_back(overall_coeff.bp->normal(sym_lst, repl_lst, level-1));
 
     // Determine common denominator
-    ex den = exONE();
+    ex den = _ex1();
     exvector::const_iterator ait = o.begin(), aitend = o.end();
     while (ait != aitend) {
         den = lcm((*ait).denom(false), den, false);
@@ -1384,7 +1468,7 @@ ex add::normal(lst &sym_lst, lst &repl_lst, int level) const
     }
 
     // Add fractions
-    if (den.is_equal(exONE()))
+    if (den.is_equal(_ex1()))
         return (new add(o))->setflag(status_flags::dynallocated);
     else {
         exvector num_seq;
@@ -1443,10 +1527,10 @@ ex power::normal(lst &sym_lst, lst &repl_lst, int level) const
 }
 
 
-/** Implementation of ex::normal() for series. It normalizes each coefficient and
+/** Implementation of ex::normal() for pseries. It normalizes each coefficient and
  *  replaces the series by a temporary symbol.
  *  @see ex::normal */
-ex series::normal(lst &sym_lst, lst &repl_lst, int level) const
+ex pseries::normal(lst &sym_lst, lst &repl_lst, int level) const
 {
     epvector new_seq;
     new_seq.reserve(seq.size());
@@ -1457,7 +1541,7 @@ ex series::normal(lst &sym_lst, lst &repl_lst, int level) const
         it++;
     }
 
-    ex n = series(var, point, new_seq);
+    ex n = pseries(var, point, new_seq);
     return replace_with_symbol(n, sym_lst, repl_lst);
 }
 
@@ -1483,3 +1567,7 @@ ex ex::normal(int level) const
     else
         return e;
 }
+
+#ifndef NO_GINAC_NAMESPACE
+} // namespace GiNaC
+#endif // ndef NO_GINAC_NAMESPACE