001/* 002 * $Id$ 003 */ 004 005package edu.jas.fd; 006 007 008import org.apache.logging.log4j.Logger; 009import org.apache.logging.log4j.LogManager; 010 011import edu.jas.poly.GenPolynomial; 012import edu.jas.poly.GenSolvablePolynomial; 013import edu.jas.poly.PolyUtil; 014import edu.jas.structure.GcdRingElem; 015import edu.jas.structure.RingFactory; 016 017 018/** 019 * (Non-unique) factorization domain greatest common divisor common algorithms 020 * with primitive polynomial remainder sequence. 021 * @param <C> coefficient type 022 * @author Heinz Kredel 023 */ 024 025public class GreatestCommonDivisorPrimitive<C extends GcdRingElem<C>> extends 026 GreatestCommonDivisorAbstract<C> { 027 028 029 private static final Logger logger = LogManager.getLogger(GreatestCommonDivisorPrimitive.class); 030 031 032 private static final boolean debug = logger.isDebugEnabled(); 033 034 035 /** 036 * Constructor. 037 * @param cf coefficient ring. 038 */ 039 public GreatestCommonDivisorPrimitive(RingFactory<C> cf) { 040 super(cf); 041 } 042 043 044 /** 045 * Univariate GenSolvablePolynomial greatest common divisor. Uses 046 * pseudoRemainder for remainder. 047 * @param P univariate GenSolvablePolynomial. 048 * @param S univariate GenSolvablePolynomial. 049 * @return gcd(P,S) with P = P'*gcd(P,S) and S = S'*gcd(P,S). 050 */ 051 @Override 052 public GenSolvablePolynomial<C> leftBaseGcd(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) { 053 if (S == null || S.isZERO()) { 054 return P; 055 } 056 if (P == null || P.isZERO()) { 057 return S; 058 } 059 if (P.ring.nvar > 1) { 060 throw new IllegalArgumentException(this.getClass().getName() + " no univariate polynomial"); 061 } 062 boolean field = P.ring.coFac.isField(); 063 System.out.println("baseGcd: field = " + field + ", is " + P.ring.coFac.toScript()); 064 long e = P.degree(0); 065 long f = S.degree(0); 066 GenSolvablePolynomial<C> q; 067 GenSolvablePolynomial<C> r; 068 if (f > e) { 069 r = P; 070 q = S; 071 long g = f; 072 f = e; 073 e = g; 074 } else { 075 q = P; 076 r = S; 077 } 078 if (debug) { 079 logger.debug("degrees: e = {}, f = {}", e, f); 080 } 081 C c; 082 if (field) { 083 r = r.monic(); 084 q = q.monic(); 085 c = P.ring.getONECoefficient(); 086 } else { 087 r = (GenSolvablePolynomial<C>) r.abs(); 088 q = (GenSolvablePolynomial<C>) q.abs(); 089 C a = leftBaseContent(r); 090 C b = leftBaseContent(q); 091 r = divide(r, a); // indirection 092 q = divide(q, b); // indirection 093 c = gcd(a, b); // indirection 094 } 095 System.out.println("baseCont: gcd(cont) = " + c); 096 if (r.isONE()) { 097 return r.multiplyLeft(c); 098 } 099 if (q.isONE()) { 100 return q.multiplyLeft(c); 101 } 102 GenSolvablePolynomial<C> x; 103 logger.info("baseGCD: q = {}", q); 104 logger.info("baseGCD: r = {}", r); 105 System.out.println("baseGcd: rem = " + r); 106 while (!r.isZERO()) { 107 x = FDUtil.<C> leftBaseSparsePseudoRemainder(q, r); 108 q = r; 109 if (field) { 110 r = x.monic(); 111 } else { 112 r = leftBasePrimitivePart(x); 113 } 114 System.out.println("baseGcd: rem = " + r); 115 logger.info("baseGCD: q = {}", q); 116 logger.info("baseGCD: r = {}", r); 117 } 118 System.out.println("baseGcd: quot = " + q); 119 q = leftBasePrimitivePart(q); 120 logger.info("baseGCD: pp(q) = {}", q); 121 return (GenSolvablePolynomial<C>) (q.multiply(c)).abs(); 122 } 123 124 125 /** 126 * Univariate GenSolvablePolynomial right greatest common divisor. Uses 127 * pseudoRemainder for remainder. 128 * @param P univariate GenSolvablePolynomial. 129 * @param S univariate GenSolvablePolynomial. 130 * @return gcd(P,S) with P = gcd(P,S)*P' and S = gcd(P,S)*S'. 131 */ 132 @Override 133 public GenSolvablePolynomial<C> rightBaseGcd(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) { 134 if (S == null || S.isZERO()) { 135 return P; 136 } 137 if (P == null || P.isZERO()) { 138 return S; 139 } 140 if (P.ring.nvar > 1) { 141 throw new IllegalArgumentException(this.getClass().getName() + " no univariate polynomial"); 142 } 143 boolean field = P.ring.coFac.isField(); 144 long e = P.degree(0); 145 long f = S.degree(0); 146 GenSolvablePolynomial<C> q; 147 GenSolvablePolynomial<C> r; 148 if (f > e) { 149 r = P; 150 q = S; 151 long g = f; 152 f = e; 153 e = g; 154 } else { 155 q = P; 156 r = S; 157 } 158 if (debug) { 159 logger.debug("degrees: e = {}, f = {}", e, f); 160 } 161 C c; 162 if (field) { 163 r = r.monic(); 164 q = q.monic(); 165 c = P.ring.getONECoefficient(); 166 } else { 167 r = (GenSolvablePolynomial<C>) r.abs(); 168 q = (GenSolvablePolynomial<C>) q.abs(); 169 C a = leftBaseContent(r); 170 C b = leftBaseContent(q); 171 r = divide(r, a); // indirection 172 q = divide(q, b); // indirection 173 c = gcd(a, b); // indirection 174 } 175 //System.out.println("baseCont: gcd(cont) = " + b); 176 if (r.isONE()) { 177 return r.multiply(c); 178 } 179 if (q.isONE()) { 180 return q.multiply(c); 181 } 182 GenSolvablePolynomial<C> x; 183 //System.out.println("baseGCD: q = " + q); 184 //System.out.println("baseGCD: r = " + r); 185 while (!r.isZERO()) { 186 x = FDUtil.<C> rightBaseSparsePseudoRemainder(q, r); 187 q = r; 188 if (field) { 189 r = x.monic(); 190 } else { 191 r = rightBasePrimitivePart(x); 192 } 193 //System.out.println("baseGCD: q = " + q); 194 //System.out.println("baseGCD: r = " + r); 195 } 196 q = leftBasePrimitivePart(q); // todo 197 return (GenSolvablePolynomial<C>) (q.multiplyLeft(c)).abs(); 198 } 199 200 201 /** 202 * Univariate GenSolvablePolynomial left recursive greatest common divisor. 203 * Uses pseudoRemainder for remainder. 204 * @param P univariate recursive GenSolvablePolynomial. 205 * @param S univariate recursive GenSolvablePolynomial. 206 * @return gcd(P,S) with P = P'*gcd(P,S)*p and S = S'*gcd(P,S)*s, where 207 * deg_main(p) = deg_main(s) == 0. 208 */ 209 @Override 210 public GenSolvablePolynomial<GenPolynomial<C>> leftRecursiveUnivariateGcd( 211 GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<GenPolynomial<C>> S) { 212 if (S == null || S.isZERO()) { 213 return P; 214 } 215 if (P == null || P.isZERO()) { 216 return S; 217 } 218 if (P.ring.nvar > 1) { 219 throw new IllegalArgumentException("no univariate polynomial"); 220 } 221 //boolean field = P.leadingBaseCoefficient().ring.coFac.isField(); 222 boolean field = P.ring.coFac.isField(); 223 System.out.println("recursiveUnivGcd: field = " + field); 224 long e = P.degree(0); 225 long f = S.degree(0); 226 GenSolvablePolynomial<GenPolynomial<C>> q, r, x, qs, rs; 227 if (f > e) { 228 r = P; 229 q = S; 230 long g = f; 231 f = e; 232 e = g; 233 } else if (f < e) { 234 q = P; 235 r = S; 236 } else { // f == e 237 if (P.leadingBaseCoefficient().degree() > S.leadingBaseCoefficient().degree()) { 238 q = P; 239 r = S; 240 } else { 241 r = P; 242 q = S; 243 } 244 } 245 logger.debug("degrees: e = {}, f = {}", e, f); 246 if (field) { 247 r = PolyUtil.<C> monic(r); 248 q = PolyUtil.<C> monic(q); 249 } else { 250 r = (GenSolvablePolynomial<GenPolynomial<C>>) r.abs(); 251 q = (GenSolvablePolynomial<GenPolynomial<C>>) q.abs(); 252 } 253 GenSolvablePolynomial<C> a = leftRecursiveContent(r); 254 System.out.println("recursiveUnivGcd: a = " + a); 255 rs = FDUtil.<C> recursiveLeftDivide(r, a); 256 System.out.println("recursiveUnivGcd: rs = " + rs); 257 //logger.info("recCont a = {}, r = {}", a, r); 258 if (!r.equals(rs.multiplyLeft(a))) { // todo: should be rs.multiplyLeft(a)) 259 System.out.println("recursiveUnivGcd: r = " + r); 260 System.out.println("recursiveUnivGcd: cont(r) = " + a); 261 System.out.println("recursiveUnivGcd: pp(r) = " + rs); 262 System.out.println("recursiveUnivGcd: pp(r)c(r) = " + rs.multiply(a)); 263 System.out.println("recursiveUnivGcd: c(r)pp(r) = " + rs.multiplyLeft(a)); 264 throw new RuntimeException("recursiveUnivGcd: r: not divisible"); 265 } 266 r = rs; 267 GenSolvablePolynomial<C> b = leftRecursiveContent(q); 268 System.out.println("recursiveUnivGcd: b = " + b); 269 qs = FDUtil.<C> recursiveLeftDivide(q, b); 270 System.out.println("recursiveUnivGcd: qs = " + qs); 271 //logger.info("recCont b = {}, q = {}", b, q); 272 if (!q.equals(qs.multiplyLeft(b))) { // todo: should be qs.multiplyLeft(b)) 273 System.out.println("recursiveUnivGcd: q = " + q); 274 System.out.println("recursiveUnivGcd: cont(q) = " + b); 275 System.out.println("recursiveUnivGcd: pp(q) = " + qs); 276 System.out.println("recursiveUnivGcd: pp(q)c(q) = " + qs.multiply(b)); 277 System.out.println("recursiveUnivGcd: c(q)pp(q) = " + qs.multiplyLeft(b)); 278 throw new RuntimeException("recursiveUnivGcd: q: not divisible"); 279 } 280 q = qs; 281 GenSolvablePolynomial<C> c = leftGcd(a, b); // go to recursion 282 //GenSolvablePolynomial<C> c = rightGcd(a, b); // go to recursion 283 logger.info("Gcd(contents) c = {}, a = {}, b = {}", c, a, b); 284 if (r.isONE()) { 285 return r.multiplyLeft(c); 286 } 287 if (q.isONE()) { 288 return q.multiplyLeft(c); 289 } 290 logger.info("r.ring = {}", r.ring.toScript()); 291 System.out.println("recursiveUnivGcd: r = " + r); 292 while (!r.isZERO()) { 293 x = FDUtil.<C> recursiveSparsePseudoRemainder(q, r); 294 q = r; 295 if (field) { 296 r = PolyUtil.<C> monic(x); 297 } else { 298 r = leftRecursivePrimitivePart(x); 299 } 300 System.out.println("recursiveUnivGcd: r = " + r); 301 } 302 if (debug) { 303 logger.info("gcd(pp) = {}, ring = {}", q, P.ring.toScript()); 304 } 305 q = leftRecursivePrimitivePart(q); 306 q = (GenSolvablePolynomial<GenPolynomial<C>>) q.multiplyLeft(c).abs(); 307 return q; 308 } 309 310 311 /** 312 * Univariate GenSolvablePolynomial right recursive greatest common divisor. 313 * Uses pseudoRemainder for remainder. 314 * @param P univariate recursive GenSolvablePolynomial. 315 * @param S univariate recursive GenSolvablePolynomial. 316 * @return gcd(P,S) with P = p*gcd(P,S)*P' and S = s*gcd(P,S)*S', where 317 * deg_main(p) = deg_main(s) == 0. 318 */ 319 @Override 320 public GenSolvablePolynomial<GenPolynomial<C>> rightRecursiveUnivariateGcd( 321 GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<GenPolynomial<C>> S) { 322 if (S == null || S.isZERO()) { 323 return P; 324 } 325 if (P == null || P.isZERO()) { 326 return S; 327 } 328 if (P.ring.nvar > 1) { 329 throw new IllegalArgumentException("no univariate polynomial"); 330 } 331 boolean field = P.leadingBaseCoefficient().ring.coFac.isField(); 332 //boolean field = P.ring.coFac.isField(); 333 long e = P.degree(0); 334 long f = S.degree(0); 335 GenSolvablePolynomial<GenPolynomial<C>> q, r, x, qs, rs; 336 if (f > e) { 337 r = P; 338 q = S; 339 long g = f; 340 f = e; 341 e = g; 342 } else if (f < e) { 343 q = P; 344 r = S; 345 } else { // f == e 346 if (P.leadingBaseCoefficient().degree() > S.leadingBaseCoefficient().degree()) { 347 q = P; 348 r = S; 349 } else { 350 r = P; 351 q = S; 352 } 353 } 354 if (debug) { 355 logger.debug("RI-degrees: e = {}, f = {}", e, f); 356 } 357 if (field) { 358 r = PolyUtil.<C> monic(r); 359 q = PolyUtil.<C> monic(q); 360 } else { 361 r = (GenSolvablePolynomial<GenPolynomial<C>>) r.abs(); 362 q = (GenSolvablePolynomial<GenPolynomial<C>>) q.abs(); 363 } 364 GenSolvablePolynomial<C> a = leftRecursiveContent(r); 365 rs = FDUtil.<C> recursiveRightDivide(r, a); 366 if (debug) { 367 logger.info("RI-recCont a = {}, r = {}", a, r); 368 logger.info("RI-recCont r/a = {}, r%a = {}", r, r.subtract(rs.multiplyLeft(a))); 369 if (!r.equals(rs.multiplyLeft(a))) { 370 System.out.println("RI-recGcd: r = " + r); 371 System.out.println("RI-recGcd: cont(r) = " + a); 372 System.out.println("RI-recGcd: pp(r) = " + rs); 373 System.out.println("RI-recGcd: pp(r)c(r) = " + rs.multiply(a)); 374 System.out.println("RI-recGcd: c(r)pp(r) = " + rs.multiplyLeft(a)); 375 throw new RuntimeException("RI-recGcd: pp: not divisible"); 376 } 377 } 378 r = rs; 379 GenSolvablePolynomial<C> b = leftRecursiveContent(q); 380 qs = FDUtil.<C> recursiveRightDivide(q, b); 381 if (debug) { 382 logger.info("RI-recCont b = {}, q = {}", b, q); 383 logger.info("RI-recCont q/b = {}, q%b = {}", qs, q.subtract(qs.multiplyLeft(b))); 384 if (!q.equals(qs.multiplyLeft(b))) { 385 System.out.println("RI-recGcd: q = " + q); 386 System.out.println("RI-recGcd: cont(q) = " + b); 387 System.out.println("RI-recGcd: pp(q) = " + qs); 388 System.out.println("RI-recGcd: pp(q)c(q) = " + qs.multiply(b)); 389 System.out.println("RI-recGcd: c(q)pp(q) = " + qs.multiplyLeft(b)); 390 throw new RuntimeException("RI-recGcd: pp: not divisible"); 391 } 392 } 393 q = qs; 394 //no: GenSolvablePolynomial<C> c = rightGcd(a, b); // go to recursion 395 GenSolvablePolynomial<C> c = leftGcd(a, b); // go to recursion 396 logger.info("RI-Gcd(contents) c = {}, a = {}, b = {}", c, a, b); 397 if (r.isONE()) { 398 return r.multiplyLeft(c); 399 } 400 if (q.isONE()) { 401 return q.multiplyLeft(c); 402 } 403 if (debug) { 404 logger.info("RI-r.ring = {}", r.ring.toScript()); 405 } 406 while (!r.isZERO()) { 407 x = FDUtil.<C> recursiveRightSparsePseudoRemainder(q, r); 408 q = r; 409 if (field) { 410 r = PolyUtil.<C> monic(x); 411 } else { 412 r = leftRecursivePrimitivePart(x); 413 } 414 } 415 logger.info("RI-recGcd(P,S) pre pp okay: q = {}", q); 416 //q = rightRecursivePrimitivePart(q); 417 q = leftRecursivePrimitivePart(q); // sic 418 System.out.println("RI-recGcd: pp(q) = " + q); 419 if (debug) { 420 logger.info("RI-gcd(pp) = {}, ring = {}", q, P.ring.toScript()); 421 } 422 q = (GenSolvablePolynomial<GenPolynomial<C>>) q.multiplyLeft(c).abs(); 423 return q; 424 } 425 426}