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