001/* 002 * $Id: GreatestCommonDivisorPrimitive.java 4026 2012-07-23 16:52:28Z kredel $ 003 */ 004 005package edu.jas.ufd; 006 007 008import org.apache.log4j.Logger; 009 010import edu.jas.poly.GenPolynomial; 011import edu.jas.poly.PolyUtil; 012import edu.jas.structure.GcdRingElem; 013 014 015/** 016 * Greatest common divisor algorithms with primitive polynomial remainder 017 * sequence. 018 * @author Heinz Kredel 019 */ 020 021public class GreatestCommonDivisorPrimitive<C extends GcdRingElem<C>> extends 022 GreatestCommonDivisorAbstract<C> { 023 024 025 private static final Logger logger = Logger.getLogger(GreatestCommonDivisorPrimitive.class); 026 027 028 private final boolean debug = logger.isDebugEnabled(); 029 030 031 /** 032 * Univariate GenPolynomial greatest comon divisor. Uses pseudoRemainder for 033 * remainder. 034 * @param P univariate GenPolynomial. 035 * @param S univariate GenPolynomial. 036 * @return gcd(P,S). 037 */ 038 @Override 039 public GenPolynomial<C> baseGcd(GenPolynomial<C> P, GenPolynomial<C> S) { 040 if (S == null || S.isZERO()) { 041 return P; 042 } 043 if (P == null || P.isZERO()) { 044 return S; 045 } 046 if (P.ring.nvar > 1) { 047 throw new IllegalArgumentException(this.getClass().getName() + " no univariate polynomial"); 048 } 049 long e = P.degree(0); 050 long f = S.degree(0); 051 GenPolynomial<C> q; 052 GenPolynomial<C> r; 053 if (f > e) { 054 r = P; 055 q = S; 056 long g = f; 057 f = e; 058 e = g; 059 } else { 060 q = P; 061 r = S; 062 } 063 if (debug) { 064 logger.debug("degrees: e = " + e + ", f = " + f); 065 } 066 r = r.abs(); 067 q = q.abs(); 068 C a = baseContent(r); 069 C b = baseContent(q); 070 C c = gcd(a, b); // indirection 071 r = divide(r, a); // indirection 072 q = divide(q, b); // indirection 073 if (r.isONE()) { 074 return r.multiply(c); 075 } 076 if (q.isONE()) { 077 return q.multiply(c); 078 } 079 GenPolynomial<C> x; 080 while (!r.isZERO()) { 081 x = PolyUtil.<C> baseSparsePseudoRemainder(q, r); 082 q = r; 083 r = basePrimitivePart(x); 084 } 085 return (q.multiply(c)).abs(); 086 } 087 088 089 /** 090 * Univariate GenPolynomial recursive greatest comon divisor. Uses 091 * pseudoRemainder for remainder. 092 * @param P univariate recursive GenPolynomial. 093 * @param S univariate recursive GenPolynomial. 094 * @return gcd(P,S). 095 */ 096 @Override 097 public GenPolynomial<GenPolynomial<C>> recursiveUnivariateGcd(GenPolynomial<GenPolynomial<C>> P, 098 GenPolynomial<GenPolynomial<C>> S) { 099 if (S == null || S.isZERO()) { 100 return P; 101 } 102 if (P == null || P.isZERO()) { 103 return S; 104 } 105 if (P.ring.nvar > 1) { 106 throw new IllegalArgumentException(this.getClass().getName() + " no univariate polynomial"); 107 } 108 long e = P.degree(0); 109 long f = S.degree(0); 110 GenPolynomial<GenPolynomial<C>> q; 111 GenPolynomial<GenPolynomial<C>> r; 112 if (f > e) { 113 r = P; 114 q = S; 115 long g = f; 116 f = e; 117 e = g; 118 } else { 119 q = P; 120 r = S; 121 } 122 if (debug) { 123 logger.debug("degrees: e = " + e + ", f = " + f); 124 } 125 r = r.abs(); 126 q = q.abs(); 127 GenPolynomial<C> a = recursiveContent(r); 128 GenPolynomial<C> b = recursiveContent(q); 129 130 GenPolynomial<C> c = gcd(a, b); // go to recursion 131 //System.out.println("rgcd c = " + c); 132 r = PolyUtil.<C> recursiveDivide(r, a); 133 q = PolyUtil.<C> recursiveDivide(q, b); 134 if (r.isONE()) { 135 return r.multiply(c); 136 } 137 if (q.isONE()) { 138 return q.multiply(c); 139 } 140 GenPolynomial<GenPolynomial<C>> x; 141 while (!r.isZERO()) { 142 x = PolyUtil.<C> recursivePseudoRemainder(q, r); 143 //System.out.println("rgcd x = " + x); 144 q = r; 145 r = recursivePrimitivePart(x); 146 } 147 return q.abs().multiply(c); //.abs(); 148 } 149 150}