X-Git-Url: https://www.ginac.de/ginac.git//ginac.git?p=ginac.git;a=blobdiff_plain;f=ginac%2Ffactor.cpp;h=2b77d1b0110f3e327216a11a20510b901a6b93ee;hp=e9b2569b57f6f654d7e1f48819d9c2c28f09cbf1;hb=8cffcdf13d817a47f217f1a1043317d95969e070;hpb=792cda15eb0089edccdc0a89e7c39e58e940b87b

diff --git a/ginac/factor.cpp b/ginac/factor.cpp
index e9b2569b..2b77d1b0 100644
--- a/ginac/factor.cpp
+++ b/ginac/factor.cpp
@@ -33,7 +33,7 @@
  */
 
 /*
- *  GiNaC Copyright (C) 1999-2015 Johannes Gutenberg University Mainz, Germany
+ *  GiNaC Copyright (C) 1999-2019 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
@@ -66,7 +66,6 @@
 #include "add.h"
 
 #include <algorithm>
-#include <cmath>
 #include <limits>
 #include <list>
 #include <vector>
@@ -916,8 +915,7 @@ static void berlekamp(const umodpoly& a, upvec& upv)
 		return;
 	}
 
-	list<umodpoly> factors;
-	factors.push_back(a);
+	list<umodpoly> factors = {a};
 	unsigned int size = 1;
 	unsigned int r = 1;
 	unsigned int q = cl_I_to_uint(R->modulus);
@@ -937,8 +935,7 @@ static void berlekamp(const umodpoly& a, upvec& upv)
 				div(*u, g, uo);
 				if ( equal_one(uo) ) {
 					throw logic_error("berlekamp: unexpected divisor.");
-				}
-				else {
+				} else {
 					*u = uo;
 				}
 				factors.push_back(g);
@@ -1021,8 +1018,7 @@ static void modsqrfree(const umodpoly& a, upvec& factors, vector<int>& mult)
 				mult[i] *= prime;
 			}
 		}
-	}
-	else {
+	} else {
 		umodpoly ap;
 		expt_1_over_p(a, prime, ap);
 		size_t previ = mult.size();
@@ -1107,8 +1103,7 @@ static void same_degree_factor(const umodpoly& a, upvec& upv)
 	for ( size_t i=0; i<degrees.size(); ++i ) {
 		if ( degrees[i] == degree(ddfactors[i]) ) {
 			upv.push_back(ddfactors[i]);
-		}
-		else {
+		} else {
 			berlekamp(ddfactors[i], upv);
 		}
 	}
@@ -1314,8 +1309,7 @@ static void hensel_univar(const upoly& a_, unsigned int p, const umodpoly& u1_,
 		if ( alpha != 1 ) {
 			w = w / alpha;
 		}
-	}
-	else {
+	} else {
 		u.clear();
 	}
 }
@@ -1328,20 +1322,22 @@ static void hensel_univar(const upoly& a_, unsigned int p, const umodpoly& u1_,
 static unsigned int next_prime(unsigned int p)
 {
 	static vector<unsigned int> primes;
-	if ( primes.size() == 0 ) {
-		primes.push_back(3); primes.push_back(5); primes.push_back(7);
+	if (primes.empty()) {
+		primes = {3, 5, 7};
 	}
 	if ( p >= primes.back() ) {
 		unsigned int candidate = primes.back() + 2;
 		while ( true ) {
 			size_t n = primes.size()/2;
 			for ( size_t i=0; i<n; ++i ) {
-				if ( candidate % primes[i] ) continue;
+				if (candidate % primes[i])
+					continue;
 				candidate += 2;
 				i=-1;
 			}
 			primes.push_back(candidate);
-			if ( candidate > p ) break;
+			if (candidate > p)
+				break;
 		}
 		return candidate;
 	}
@@ -1405,8 +1401,7 @@ public:
 			if ( len > n/2 ) return false;
 			fill(k.begin(), k.begin()+len, 1);
 			fill(k.begin()+len+1, k.end(), 0);
-		}
-		else {
+		} else {
 			k[last++] = 0;
 			k[last] = 1;
 		}
@@ -1429,8 +1424,7 @@ private:
 			if ( d ) {
 				if ( cache[pos].size() >= d ) {
 					lr[group] = lr[group] * cache[pos][d-1];
-				}
-				else {
+				} else {
 					if ( cache[pos].size() == 0 ) {
 						cache[pos].push_back(factors[pos] * factors[pos+1]);
 					}
@@ -1444,8 +1438,7 @@ private:
 					}
 					lr[group] = lr[group] * cache[pos].back();
 				}
-			}
-			else {
+			} else {
 				lr[group] = lr[group] * factors[pos];
 			}
 		} while ( i < n );
@@ -1456,8 +1449,7 @@ private:
 		lr[1] = one;
 		if ( n > 6 ) {
 			split_cached();
-		}
-		else {
+		} else {
 			for ( size_t i=0; i<n; ++i ) {
 				lr[k[i]] = lr[k[i]] * factors[i];
 			}
@@ -1542,8 +1534,7 @@ static ex factor_univariate(const ex& poly, const ex& x, unsigned int& prime)
 			minfactors = trialfactors.size();
 			lastp = prime;
 			trials = 1;
-		}
-		else {
+		} else {
 			++trials;
 		}
 	}
@@ -1597,15 +1588,13 @@ static ex factor_univariate(const ex& poly, const ex& x, unsigned int& prime)
 						}
 					}
 					break;
-				}
-				else {
+				} else {
 					upvec newfactors1(part.size_left()), newfactors2(part.size_right());
 					auto i1 = newfactors1.begin(), i2 = newfactors2.begin();
 					for ( size_t i=0; i<n; ++i ) {
 						if ( part[i] ) {
 							*i2++ = tocheck.top().factors[i];
-						}
-						else {
+						} else {
 							*i1++ = tocheck.top().factors[i];
 						}
 					}
@@ -1617,8 +1606,7 @@ static ex factor_univariate(const ex& poly, const ex& x, unsigned int& prime)
 					tocheck.push(mf);
 					break;
 				}
-			}
-			else {
+			} else {
 				// not successful
 				if ( !part.next() ) {
 					// if no more combinations left, return polynomial as
@@ -1808,8 +1796,7 @@ static upvec univar_diophant(const upvec& a, const ex& x, unsigned int m, unsign
 			rem(bmod, a[j], buf);
 			result.push_back(buf);
 		}
-	}
-	else {
+	} else {
 		umodpoly s, t;
 		eea_lift(a[1], a[0], x, p, k, s, t);
 		umodpoly bmod = umodpoly_to_umodpoly(s, R, m);
@@ -1831,7 +1818,7 @@ static upvec univar_diophant(const upvec& a, const ex& x, unsigned int m, unsign
 struct make_modular_map : public map_function {
 	cl_modint_ring R;
 	make_modular_map(const cl_modint_ring& R_) : R(R_) { }
-	ex operator()(const ex& e)
+	ex operator()(const ex& e) override
 	{
 		if ( is_a<add>(e) || is_a<mul>(e) ) {
 			return e.map(*this);
@@ -1843,8 +1830,7 @@ struct make_modular_map : public map_function {
 			numeric n(R->retract(emod));
 			if ( n > halfmod ) {
 				return n-mod;
-			}
-			else {
+			} else {
 				return n;
 			}
 		}
@@ -1887,7 +1873,8 @@ static vector<ex> multivar_diophant(const vector<ex>& a_, const ex& x, const ex&
 {
 	vector<ex> a = a_;
 
-	const cl_modint_ring R = find_modint_ring(expt_pos(cl_I(p),k));
+	const cl_I modulus = expt_pos(cl_I(p),k);
+	const cl_modint_ring R = find_modint_ring(modulus);
 	const size_t r = a.size();
 	const size_t nu = I.size() + 1;
 
@@ -1937,8 +1924,7 @@ static vector<ex> multivar_diophant(const vector<ex>& a_, const ex& x, const ex&
 				e = make_modular(buf, R);
 			}
 		}
-	}
-	else {
+	} else {
 		upvec amod;
 		for ( size_t i=0; i<a.size(); ++i ) {
 			umodpoly up;
@@ -1952,8 +1938,7 @@ static vector<ex> multivar_diophant(const vector<ex>& a_, const ex& x, const ex&
 		if ( is_a<add>(c) ) {
 			nterms = c.nops();
 			z = c.op(0);
-		}
-		else {
+		} else {
 			nterms = 1;
 			z = c;
 		}
@@ -1962,16 +1947,13 @@ static vector<ex> multivar_diophant(const vector<ex>& a_, const ex& x, const ex&
 			cl_I cm = the<cl_I>(ex_to<numeric>(z.lcoeff(x)).to_cl_N());
 			upvec delta_s = univar_diophant(amod, x, m, p, k);
 			cl_MI modcm;
-			cl_I poscm = cm;
-			while ( poscm < 0 ) {
-				poscm = poscm + expt_pos(cl_I(p),k);
-			}
+			cl_I poscm = plusp(cm) ? cm : mod(cm, modulus);
 			modcm = cl_MI(R, poscm);
 			for ( size_t j=0; j<delta_s.size(); ++j ) {
 				delta_s[j] = delta_s[j] * modcm;
 				sigma[j] = sigma[j] + umodpoly_to_ex(delta_s[j], x);
 			}
-			if ( nterms > 1 ) {
+			if ( nterms > 1 && i+1 != nterms ) {
 				z = c.op(i+1);
 			}
 		}
@@ -2085,15 +2067,9 @@ static ex hensel_multivar(const ex& a, const ex& x, const vector<EvalPoint>& I,
 		acand *= U[i];
 	}
 	if ( expand(a-acand).is_zero() ) {
-		lst res;
-		for ( size_t i=0; i<U.size(); ++i ) {
-			res.append(U[i]);
-		}
-		return res;
-	}
-	else {
-		lst res;
-		return lst();
+		return lst(U.begin(), U.end());
+	} else {
+		return lst{};
 	}
 }
 
@@ -2267,7 +2243,7 @@ static ex factor_multivariate(const ex& poly, const exset& syms)
 	ex vn = pp.collect(x).lcoeff(x);
 	ex vnlst;
 	if ( is_a<numeric>(vn) ) {
-		vnlst = lst(vn);
+		vnlst = lst{vn};
 	}
 	else {
 		ex vnfactors = factor(vn);
@@ -2325,8 +2301,7 @@ static ex factor_multivariate(const ex& poly, const exset& syms)
 			for ( size_t i=1; i<ufaclst.nops(); ++i ) {
 				C[i-1] = ufaclst.op(i).lcoeff(x);
 			}
-		}
-		else {
+		} else {
 			// difficult case.
 			// we use the property of the ftilde having a unique prime factor.
 			// details can be found in [Wan].
@@ -2361,8 +2336,7 @@ static ex factor_multivariate(const ex& poly, const exset& syms)
 					}
 					C[i] = D[i] * prefac;
 				}
-			}
-			else {
+			} else {
 				for ( int i=0; i<factor_count; ++i ) {
 					numeric prefac = ex_to<numeric>(ufaclst.op(i+1).lcoeff(x));
 					for ( int j=ftilde.size()-1; j>=0; --j ) {
@@ -2441,7 +2415,7 @@ static ex factor_multivariate(const ex& poly, const exset& syms)
 
 		// try Hensel lifting
 		ex res = hensel_multivar(pp, x, epv, prime, l, modfactors, C);
-		if ( res != lst() ) {
+		if ( res != lst{} ) {
 			ex result = cont * unit;
 			for ( size_t i=0; i<res.nops(); ++i ) {
 				result *= res.op(i).content(x) * res.op(i).unit(x);
@@ -2456,7 +2430,7 @@ static ex factor_multivariate(const ex& poly, const exset& syms)
  */
 struct find_symbols_map : public map_function {
 	exset syms;
-	ex operator()(const ex& e)
+	ex operator()(const ex& e) override
 	{
 		if ( is_a<symbol>(e) ) {
 			syms.insert(e);
@@ -2486,8 +2460,7 @@ static ex factor_sqrfree(const ex& poly)
 			int ld = poly.ldegree(x);
 			ex res = factor_univariate(expand(poly/pow(x, ld)), x);
 			return res * pow(x,ld);
-		}
-		else {
+		} else {
 			ex res = factor_univariate(poly, x);
 			return res;
 		}
@@ -2504,7 +2477,7 @@ static ex factor_sqrfree(const ex& poly)
 struct apply_factor_map : public map_function {
 	unsigned options;
 	apply_factor_map(unsigned options_) : options(options_) { }
-	ex operator()(const ex& e)
+	ex operator()(const ex& e) override
 	{
 		if ( e.info(info_flags::polynomial) ) {
 			return factor(e, options);
@@ -2514,26 +2487,51 @@ struct apply_factor_map : public map_function {
 			for ( size_t i=0; i<e.nops(); ++i ) {
 				if ( e.op(i).info(info_flags::polynomial) ) {
 					s1 += e.op(i);
-				}
-				else {
+				} else {
 					s2 += e.op(i);
 				}
 			}
-			s1 = s1.eval();
-			s2 = s2.eval();
 			return factor(s1, options) + s2.map(*this);
 		}
 		return e.map(*this);
 	}
 };
 
-} // anonymous namespace
+/** Iterate through explicit factors of e, call yield(f, k) for
+ *  each factor of the form f^k.
+ *
+ *  Note that this function doesn't factor e itself, it only
+ *  iterates through the factors already explicitly present.
+ */
+template <typename F> void
+factor_iter(const ex &e, F yield)
+{
+	if (is_a<mul>(e)) {
+		for (const auto &f : e) {
+			if (is_a<power>(f)) {
+				yield(f.op(0), f.op(1));
+			} else {
+				yield(f, ex(1));
+			}
+		}
+	} else {
+		if (is_a<power>(e)) {
+			yield(e.op(0), e.op(1));
+		} else {
+			yield(e, ex(1));
+		}
+	}
+}
 
-/** Interface function to the outside world. It checks the arguments, tries a
- *  square free factorization, and then calls factor_sqrfree to do the hard
- *  work.
+/** This function factorizes a polynomial. It checks the arguments,
+ *  tries a square free factorization, and then calls factor_sqrfree
+ *  to do the hard work.
+ *
+ *  This function expands its argument, so for polynomials with
+ *  explicit factors it's better to call it on each one separately
+ *  (or use factor() which does just that).
  */
-ex factor(const ex& poly, unsigned options)
+static ex factor1(const ex& poly, unsigned options)
 {
 	// check arguments
 	if ( !poly.info(info_flags::polynomial) ) {
@@ -2560,47 +2558,35 @@ ex factor(const ex& poly, unsigned options)
 	ex sfpoly = sqrfree(poly.expand(), syms);
 
 	// factorize the square free components
-	if ( is_a<power>(sfpoly) ) {
-		// case: (polynomial)^exponent
-		const ex& base = sfpoly.op(0);
-		if ( !is_a<add>(base) ) {
-			// simple case: (monomial)^exponent
-			return sfpoly;
-		}
-		ex f = factor_sqrfree(base);
-		return pow(f, sfpoly.op(1));
-	}
-	if ( is_a<mul>(sfpoly) ) {
-		// case: multiple factors
-		ex res = 1;
-		for ( size_t i=0; i<sfpoly.nops(); ++i ) {
-			const ex& t = sfpoly.op(i);
-			if ( is_a<power>(t) ) {
-				const ex& base = t.op(0);
-				if ( !is_a<add>(base) ) {
-					res *= t;
-				}
-				else {
-					ex f = factor_sqrfree(base);
-					res *= pow(f, t.op(1));
-				}
-			}
-			else if ( is_a<add>(t) ) {
-				ex f = factor_sqrfree(t);
-				res *= f;
+	ex res = 1;
+	factor_iter(sfpoly,
+		[&](const ex &f, const ex &k) {
+			if ( is_a<add>(f) ) {
+				res *= pow(factor_sqrfree(f), k);
+			} else {
+				// simple case: (monomial)^exponent
+				res *= pow(f, k);
 			}
-			else {
-				res *= t;
-			}
-		}
-		return res;
-	}
-	if ( is_a<symbol>(sfpoly) ) {
-		return poly;
-	}
-	// case: (polynomial)
-	ex f = factor_sqrfree(sfpoly);
-	return f;
+		});
+	return res;
+}
+
+} // anonymous namespace
+
+/** Interface function to the outside world. It uses factor1()
+ *  on each of the explicitly present factors of poly.
+ */
+ex factor(const ex& poly, unsigned options)
+{
+	ex result = 1;
+	factor_iter(poly,
+		[&](const ex &f1, const ex &k1) {
+			factor_iter(factor1(f1, options),
+				[&](const ex &f2, const ex &k2) {
+					result *= pow(f2, k1*k2);
+				});
+		});
+	return result;
 }
 
 } // namespace GiNaC