001/* 002 * $Id$ 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 logger.info("ifacts = {}", ifacts); 091 if (ifacts.size() <= 1) { 092 factors.add(P); 093 return factors; 094 } 095 List<GenPolynomial<BigRational>> rfacts = PolyUtil.fromIntegerCoefficients(pfac, ifacts); 096 //System.out.println("rfacts = " + rfacts); 097 rfacts = PolyUtil.monic(rfacts); 098 //System.out.println("rfacts = " + rfacts); 099 if (!ldcf.isONE()) { 100 GenPolynomial<BigRational> r = rfacts.get(0); 101 rfacts.remove(r); 102 r = r.multiply(ldcf); 103 rfacts.set(0, r); 104 } 105 logger.info("rfacts = {}", rfacts); 106 factors.addAll(rfacts); 107 return factors; 108 } 109 110 111 /** 112 * GenPolynomial factorization of a squarefree polynomial. 113 * @param P squarefree GenPolynomial. 114 * @return [p_1,...,p_k] with P = prod_{i=1, ..., k} p_i. 115 */ 116 @Override 117 public List<GenPolynomial<BigRational>> factorsSquarefree(GenPolynomial<BigRational> P) { 118 if (P == null) { 119 throw new IllegalArgumentException(this.getClass().getName() + " P == null"); 120 } 121 List<GenPolynomial<BigRational>> factors = new ArrayList<GenPolynomial<BigRational>>(); 122 if (P.isZERO()) { 123 return factors; 124 } 125 if (P.isONE()) { 126 factors.add(P); 127 return factors; 128 } 129 GenPolynomialRing<BigRational> pfac = P.ring; 130 if (pfac.nvar == 1) { 131 return baseFactorsSquarefree(P); 132 } 133 GenPolynomial<BigRational> Pr = P; 134 BigRational ldcf = P.leadingBaseCoefficient(); 135 if (!ldcf.isONE()) { 136 //System.out.println("ldcf = " + ldcf); 137 Pr = Pr.monic(); 138 } 139 BigInteger bi = BigInteger.ONE; 140 GenPolynomialRing<BigInteger> ifac = new GenPolynomialRing<BigInteger>(bi, pfac); 141 GenPolynomial<BigInteger> Pi = PolyUtil.integerFromRationalCoefficients(ifac, Pr); 142 if (debug) { 143 logger.info("Pi = {}", Pi); 144 } 145 List<GenPolynomial<BigInteger>> ifacts = iengine.factorsSquarefree(Pi); 146 logger.info("ifacts = {}", ifacts); 147 if (ifacts.size() <= 1) { 148 factors.add(P); 149 return factors; 150 } 151 List<GenPolynomial<BigRational>> rfacts = PolyUtil.fromIntegerCoefficients(pfac, ifacts); 152 //System.out.println("rfacts = " + rfacts); 153 rfacts = PolyUtil.monic(rfacts); 154 //System.out.println("rfacts = " + rfacts); 155 if (!ldcf.isONE()) { 156 GenPolynomial<BigRational> r = rfacts.get(0); 157 rfacts.remove(r); 158 r = r.multiply(ldcf); 159 rfacts.set(0, r); 160 } 161 logger.info("rfacts = {}", rfacts); 162 factors.addAll(rfacts); 163 return factors; 164 } 165 166 167 /** 168 * GenPolynomial factorization of a polynomial. 169 * @param P GenPolynomial. 170 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} 171 * p_i**e_i and p_i irreducible. 172 */ 173 @Override 174 public SortedMap<GenPolynomial<BigRational>, Long> factors(GenPolynomial<BigRational> P) { 175 if (P == null) { 176 throw new IllegalArgumentException(this.getClass().getName() + " P == null"); 177 } 178 GenPolynomialRing<BigRational> pfac = P.ring; 179 SortedMap<GenPolynomial<BigRational>, Long> factors = new TreeMap<GenPolynomial<BigRational>, Long>( 180 pfac.getComparator()); 181 if (P.isZERO()) { 182 return factors; 183 } 184 if (P.isONE()) { 185 factors.put(P, 1L); 186 return factors; 187 } 188 if (pfac.nvar == 1) { 189 return baseFactors(P); 190 } 191 GenPolynomial<BigRational> Pr = P; 192 BigInteger bi = BigInteger.ONE; 193 GenPolynomialRing<BigInteger> ifac = new GenPolynomialRing<BigInteger>(bi, pfac); 194 GenPolynomial<BigInteger> Pi = PolyUtil.integerFromRationalCoefficients(ifac, Pr); 195 if (debug) { 196 logger.info("Pi = {}", Pi); 197 } 198 SortedMap<GenPolynomial<BigInteger>, Long> ifacts = iengine.factors(Pi); 199 logger.info("ifacts = {}", ifacts); 200 for (Map.Entry<GenPolynomial<BigInteger>, Long> me : ifacts.entrySet()) { 201 GenPolynomial<BigInteger> g = me.getKey(); 202 if (g.isONE()) { // skip 1 203 continue; 204 } 205 Long d = me.getValue(); // facs.get(g); 206 GenPolynomial<BigRational> rp = PolyUtil.fromIntegerCoefficients(pfac, g); 207 factors.put(rp, d); 208 } 209 return factors; 210 } 211 212}