001/*
002 * $Id: FactorRational.java 5997 2020-03-17 15:34:31Z kredel $
003 */
004
005package edu.jas.ufd;
006
007
008import java.util.ArrayList;
009import java.util.List;
010import java.util.Map;
011import java.util.SortedMap;
012import java.util.TreeMap;
013
014import org.apache.logging.log4j.LogManager;
015import org.apache.logging.log4j.Logger;
016
017import edu.jas.arith.BigInteger;
018import edu.jas.arith.BigRational;
019import edu.jas.poly.GenPolynomial;
020import edu.jas.poly.GenPolynomialRing;
021import edu.jas.poly.PolyUtil;
022
023
024/**
025 * Rational number coefficients factorization algorithms. This class implements
026 * factorization methods for polynomials over rational numbers.
027 * @author Heinz Kredel
028 */
029
030public class FactorRational extends FactorAbsolute<BigRational> {
031
032
033    private static final Logger logger = LogManager.getLogger(FactorRational.class);
034
035
036    private static final boolean debug = logger.isInfoEnabled();
037
038
039    /**
040     * Factorization engine for integer base coefficients.
041     */
042    protected final FactorAbstract<BigInteger> iengine;
043
044
045    /**
046     * No argument constructor.
047     */
048    protected FactorRational() {
049        super(BigRational.ONE);
050        iengine = FactorFactory.getImplementation(BigInteger.ONE);
051    }
052
053
054    /**
055     * GenPolynomial base factorization of a squarefree polynomial.
056     * @param P squarefree GenPolynomial.
057     * @return [p_1,...,p_k] with P = prod_{i=1, ..., k} p_i.
058     */
059    @Override
060    public List<GenPolynomial<BigRational>> baseFactorsSquarefree(GenPolynomial<BigRational> P) {
061        if (P == null) {
062            throw new IllegalArgumentException(this.getClass().getName() + " P == null");
063        }
064        List<GenPolynomial<BigRational>> factors = new ArrayList<GenPolynomial<BigRational>>();
065        if (P.isZERO()) {
066            return factors;
067        }
068        if (P.isONE()) {
069            factors.add(P);
070            return factors;
071        }
072        GenPolynomialRing<BigRational> pfac = P.ring;
073        if (pfac.nvar > 1) {
074            throw new IllegalArgumentException(
075                            this.getClass().getName() + " only for univariate polynomials");
076        }
077        GenPolynomial<BigRational> Pr = P;
078        BigRational ldcf = P.leadingBaseCoefficient();
079        if (!ldcf.isONE()) {
080            //System.out.println("ldcf = " + ldcf);
081            Pr = Pr.monic();
082        }
083        BigInteger bi = BigInteger.ONE;
084        GenPolynomialRing<BigInteger> ifac = new GenPolynomialRing<BigInteger>(bi, pfac);
085        GenPolynomial<BigInteger> Pi = PolyUtil.integerFromRationalCoefficients(ifac, Pr);
086        if (debug) {
087            logger.info("Pi = " + Pi);
088        }
089        List<GenPolynomial<BigInteger>> ifacts = iengine.baseFactorsSquarefree(Pi);
090        if (logger.isInfoEnabled()) {
091            logger.info("ifacts = " + ifacts);
092        }
093        if (ifacts.size() <= 1) {
094            factors.add(P);
095            return factors;
096        }
097        List<GenPolynomial<BigRational>> rfacts = PolyUtil.fromIntegerCoefficients(pfac, ifacts);
098        //System.out.println("rfacts = " + rfacts);
099        rfacts = PolyUtil.monic(rfacts);
100        //System.out.println("rfacts = " + rfacts);
101        if (!ldcf.isONE()) {
102            GenPolynomial<BigRational> r = rfacts.get(0);
103            rfacts.remove(r);
104            r = r.multiply(ldcf);
105            rfacts.set(0, r);
106        }
107        if (logger.isInfoEnabled()) {
108            logger.info("rfacts = " + rfacts);
109        }
110        factors.addAll(rfacts);
111        return factors;
112    }
113
114
115    /**
116     * GenPolynomial factorization of a squarefree polynomial.
117     * @param P squarefree GenPolynomial.
118     * @return [p_1,...,p_k] with P = prod_{i=1, ..., k} p_i.
119     */
120    @Override
121    public List<GenPolynomial<BigRational>> factorsSquarefree(GenPolynomial<BigRational> P) {
122        if (P == null) {
123            throw new IllegalArgumentException(this.getClass().getName() + " P == null");
124        }
125        List<GenPolynomial<BigRational>> factors = new ArrayList<GenPolynomial<BigRational>>();
126        if (P.isZERO()) {
127            return factors;
128        }
129        if (P.isONE()) {
130            factors.add(P);
131            return factors;
132        }
133        GenPolynomialRing<BigRational> pfac = P.ring;
134        if (pfac.nvar == 1) {
135            return baseFactorsSquarefree(P);
136        }
137        GenPolynomial<BigRational> Pr = P;
138        BigRational ldcf = P.leadingBaseCoefficient();
139        if (!ldcf.isONE()) {
140            //System.out.println("ldcf = " + ldcf);
141            Pr = Pr.monic();
142        }
143        BigInteger bi = BigInteger.ONE;
144        GenPolynomialRing<BigInteger> ifac = new GenPolynomialRing<BigInteger>(bi, pfac);
145        GenPolynomial<BigInteger> Pi = PolyUtil.integerFromRationalCoefficients(ifac, Pr);
146        if (debug) {
147            logger.info("Pi = " + Pi);
148        }
149        List<GenPolynomial<BigInteger>> ifacts = iengine.factorsSquarefree(Pi);
150        if (logger.isInfoEnabled()) {
151            logger.info("ifacts = " + ifacts);
152        }
153        if (ifacts.size() <= 1) {
154            factors.add(P);
155            return factors;
156        }
157        List<GenPolynomial<BigRational>> rfacts = PolyUtil.fromIntegerCoefficients(pfac, ifacts);
158        //System.out.println("rfacts = " + rfacts);
159        rfacts = PolyUtil.monic(rfacts);
160        //System.out.println("rfacts = " + rfacts);
161        if (!ldcf.isONE()) {
162            GenPolynomial<BigRational> r = rfacts.get(0);
163            rfacts.remove(r);
164            r = r.multiply(ldcf);
165            rfacts.set(0, r);
166        }
167        if (logger.isInfoEnabled()) {
168            logger.info("rfacts = " + rfacts);
169        }
170        factors.addAll(rfacts);
171        return factors;
172    }
173
174
175    /**
176     * GenPolynomial factorization of a polynomial.
177     * @param P GenPolynomial.
178     * @return [p_1 -&gt; e_1, ..., p_k -&gt; e_k] with P = prod_{i=1,...,k}
179     *         p_i**e_i and p_i irreducible.
180     */
181    @Override
182    public SortedMap<GenPolynomial<BigRational>, Long> factors(GenPolynomial<BigRational> P) {
183        if (P == null) {
184            throw new IllegalArgumentException(this.getClass().getName() + " P == null");
185        }
186        GenPolynomialRing<BigRational> pfac = P.ring;
187        SortedMap<GenPolynomial<BigRational>, Long> factors = new TreeMap<GenPolynomial<BigRational>, Long>(
188                        pfac.getComparator());
189        if (P.isZERO()) {
190            return factors;
191        }
192        if (P.isONE()) {
193            factors.put(P, 1L);
194            return factors;
195        }
196        if (pfac.nvar == 1) {
197            return baseFactors(P);
198        }
199        GenPolynomial<BigRational> Pr = P;
200        BigInteger bi = BigInteger.ONE;
201        GenPolynomialRing<BigInteger> ifac = new GenPolynomialRing<BigInteger>(bi, pfac);
202        GenPolynomial<BigInteger> Pi = PolyUtil.integerFromRationalCoefficients(ifac, Pr);
203        if (debug) {
204            logger.info("Pi = " + Pi);
205        }
206        SortedMap<GenPolynomial<BigInteger>, Long> ifacts = iengine.factors(Pi);
207        if (logger.isInfoEnabled()) {
208            logger.info("ifacts = " + ifacts);
209        }
210        for (Map.Entry<GenPolynomial<BigInteger>, Long> me : ifacts.entrySet()) {
211            GenPolynomial<BigInteger> g = me.getKey();
212            if (g.isONE()) { // skip 1
213                continue;
214            }
215            Long d = me.getValue(); // facs.get(g);
216            GenPolynomial<BigRational> rp = PolyUtil.fromIntegerCoefficients(pfac, g);
217            factors.put(rp, d);
218        }
219        return factors;
220    }
221
222}