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}