001    /*
002     * $Id: GreatestCommonDivisorPrimitive.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 primitive polynomial remainder
017     * sequence.
018     * @author Heinz Kredel
019     */
020    
021    public 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            r = r.abs();
064            q = q.abs();
065            C a = baseContent(r);
066            C b = baseContent(q);
067            C c = gcd(a, b); // indirection
068            r = divide(r, a); // indirection
069            q = divide(q, b); // indirection
070            if (r.isONE()) {
071                return r.multiply(c);
072            }
073            if (q.isONE()) {
074                return q.multiply(c);
075            }
076            GenPolynomial<C> x;
077            while (!r.isZERO()) {
078                x = PolyUtil.<C> basePseudoRemainder(q, r);
079                q = r;
080                r = basePrimitivePart(x);
081            }
082            return (q.multiply(c)).abs();
083        }
084    
085    
086        /**
087         * Univariate GenPolynomial recursive greatest comon divisor. Uses
088         * pseudoRemainder for remainder.
089         * @param P univariate recursive GenPolynomial.
090         * @param S univariate recursive GenPolynomial.
091         * @return gcd(P,S).
092         */
093        @Override
094        public GenPolynomial<GenPolynomial<C>> recursiveUnivariateGcd(GenPolynomial<GenPolynomial<C>> P,
095                GenPolynomial<GenPolynomial<C>> S) {
096            if (S == null || S.isZERO()) {
097                return P;
098            }
099            if (P == null || P.isZERO()) {
100                return S;
101            }
102            if (P.ring.nvar > 1) {
103                throw new IllegalArgumentException(this.getClass().getName() + " no univariate polynomial");
104            }
105            long e = P.degree(0);
106            long f = S.degree(0);
107            GenPolynomial<GenPolynomial<C>> q;
108            GenPolynomial<GenPolynomial<C>> r;
109            if (f > e) {
110                r = P;
111                q = S;
112                long g = f;
113                f = e;
114                e = g;
115            } else {
116                q = P;
117                r = S;
118            }
119            r = r.abs();
120            q = q.abs();
121            GenPolynomial<C> a = recursiveContent(r);
122            GenPolynomial<C> b = recursiveContent(q);
123    
124            GenPolynomial<C> c = gcd(a, b); // go to recursion
125            //System.out.println("rgcd c = " + c);
126            r = PolyUtil.<C> recursiveDivide(r, a);
127            q = PolyUtil.<C> recursiveDivide(q, b);
128            if (r.isONE()) {
129                return r.multiply(c);
130            }
131            if (q.isONE()) {
132                return q.multiply(c);
133            }
134            GenPolynomial<GenPolynomial<C>> x;
135            while (!r.isZERO()) {
136                x = PolyUtil.<C> recursivePseudoRemainder(q, r);
137                //System.out.println("rgcd x = " + x);
138                q = r;
139                r = recursivePrimitivePart(x);
140            }
141            return q.abs().multiply(c); //.abs();
142        }
143    
144    }