001 /*
002 * $Id: GreatestCommonDivisorSimple.java 3290 2010-08-26 09:18:48Z kredel $
003 */
004
005 package edu.jas.ufd;
006
007
008 import org.apache.log4j.Logger;
009
010 import edu.jas.poly.GenPolynomial;
011 import edu.jas.poly.PolyUtil;
012 import edu.jas.structure.GcdRingElem;
013
014
015 /**
016 * Greatest common divisor algorithms with monic polynomial remainder sequence.
017 * If C is a field, then the monic PRS (on coefficients) is computed otherwise
018 * no simplifications in the reduction are made.
019 * @author Heinz Kredel
020 */
021
022 public class GreatestCommonDivisorSimple<C extends GcdRingElem<C>> extends GreatestCommonDivisorAbstract<C> {
023
024
025 private static final Logger logger = Logger.getLogger(GreatestCommonDivisorSimple.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 boolean field = P.ring.coFac.isField();
050 long e = P.degree(0);
051 long f = S.degree(0);
052 GenPolynomial<C> q;
053 GenPolynomial<C> r;
054 if (f > e) {
055 r = P;
056 q = S;
057 long g = f;
058 f = e;
059 e = g;
060 } else {
061 q = P;
062 r = S;
063 }
064 C c;
065 if (field) {
066 r = r.monic();
067 q = q.monic();
068 c = P.ring.getONECoefficient();
069 } else {
070 r = r.abs();
071 q = q.abs();
072 C a = baseContent(r);
073 C b = baseContent(q);
074 c = gcd(a, b); // indirection
075 r = divide(r, a); // indirection
076 q = divide(q, b); // indirection
077 }
078 if (r.isONE()) {
079 return r.multiply(c);
080 }
081 if (q.isONE()) {
082 return q.multiply(c);
083 }
084 GenPolynomial<C> x;
085 //System.out.println("q = " + q);
086 //System.out.println("r = " + r);
087 while (!r.isZERO()) {
088 x = PolyUtil.<C> basePseudoRemainder(q, r);
089 q = r;
090 if (field) {
091 r = x.monic();
092 } else {
093 r = x;
094 }
095 //System.out.println("q = " + q);
096 //System.out.println("r = " + r);
097 }
098 q = basePrimitivePart(q);
099 return (q.multiply(c)).abs();
100 }
101
102
103 /**
104 * Univariate GenPolynomial recursive greatest comon divisor. Uses
105 * pseudoRemainder for remainder.
106 * @param P univariate recursive GenPolynomial.
107 * @param S univariate recursive GenPolynomial.
108 * @return gcd(P,S).
109 */
110 @Override
111 public GenPolynomial<GenPolynomial<C>> recursiveUnivariateGcd(GenPolynomial<GenPolynomial<C>> P,
112 GenPolynomial<GenPolynomial<C>> S) {
113 if (S == null || S.isZERO()) {
114 return P;
115 }
116 if (P == null || P.isZERO()) {
117 return S;
118 }
119 if (P.ring.nvar > 1) {
120 throw new IllegalArgumentException(this.getClass().getName() + " no univariate polynomial");
121 }
122 boolean field = P.leadingBaseCoefficient().ring.coFac.isField();
123 long e = P.degree(0);
124 long f = S.degree(0);
125 GenPolynomial<GenPolynomial<C>> q;
126 GenPolynomial<GenPolynomial<C>> r;
127 if (f > e) {
128 r = P;
129 q = S;
130 long g = f;
131 f = e;
132 e = g;
133 } else {
134 q = P;
135 r = S;
136 }
137 if (field) {
138 r = PolyUtil.<C> monic(r);
139 q = PolyUtil.<C> monic(q);
140 } else {
141 r = r.abs();
142 q = q.abs();
143 }
144 GenPolynomial<C> a = recursiveContent(r);
145 GenPolynomial<C> b = recursiveContent(q);
146
147 GenPolynomial<C> c = gcd(a, b); // go to recursion
148 //System.out.println("rgcd c = " + c);
149 r = PolyUtil.<C> recursiveDivide(r, a);
150 q = PolyUtil.<C> recursiveDivide(q, b);
151 if (r.isONE()) {
152 return r.multiply(c);
153 }
154 if (q.isONE()) {
155 return q.multiply(c);
156 }
157 GenPolynomial<GenPolynomial<C>> x;
158 while (!r.isZERO()) {
159 x = PolyUtil.<C> recursivePseudoRemainder(q, r);
160 q = r;
161 if (field) {
162 r = PolyUtil.<C> monic(x);
163 } else {
164 r = x;
165 }
166 }
167 q = recursivePrimitivePart(q);
168 q = q.abs().multiply(c);
169 return q;
170 }
171
172 }