Source code

001/*
002 * $Id: Quotient.java 5997 2020-03-17 15:34:31Z kredel $
003 */
004
005package edu.jas.ufd;
006
007
008import org.apache.logging.log4j.LogManager;
009import org.apache.logging.log4j.Logger;
010
011import edu.jas.kern.PrettyPrint;
012import edu.jas.poly.GenPolynomial;
013import edu.jas.structure.GcdRingElem;
014import edu.jas.structure.QuotPair;
015
016
017/**
018 * Quotient, that is a rational function, based on GenPolynomial with RingElem
019 * interface. Objects of this class are immutable.
020 * @author Heinz Kredel
021 */
022public class Quotient<C extends GcdRingElem<C>>
023                implements GcdRingElem<Quotient<C>>, QuotPair<GenPolynomial<C>> {
024
025
026    private static final Logger logger = LogManager.getLogger(Quotient.class);
027
028
029    private static final boolean debug = logger.isDebugEnabled();
030
031
032    /**
033     * Quotient class factory data structure.
034     */
035    public final QuotientRing<C> ring;
036
037
038    /**
039     * Numerator part of the element data structure.
040     */
041    public final GenPolynomial<C> num;
042
043
044    /**
045     * Denominator part of the element data structure.
046     */
047    public final GenPolynomial<C> den;
048
049
050    /**
051     * The constructor creates a Quotient object from a ring factory.
052     * @param r ring factory.
053     */
054    public Quotient(QuotientRing<C> r) {
055        this(r, r.ring.getZERO());
056    }
057
058
059    /**
060     * The constructor creates a Quotient object from a ring factory and a
061     * numerator polynomial. The denominator is assumed to be 1.
062     * @param r ring factory.
063     * @param n numerator polynomial.
064     */
065    public Quotient(QuotientRing<C> r, GenPolynomial<C> n) {
066        this(r, n, r.ring.getONE(), true);
067    }
068
069
070    /**
071     * The constructor creates a Quotient object from a ring factory and a
072     * numerator and denominator polynomial.
073     * @param r ring factory.
074     * @param n numerator polynomial.
075     * @param d denominator polynomial.
076     */
077    public Quotient(QuotientRing<C> r, GenPolynomial<C> n, GenPolynomial<C> d) {
078        this(r, n, d, false);
079    }
080
081
082    /**
083     * The constructor creates a Quotient object from a ring factory and a
084     * numerator and denominator polynomial.
085     * @param r ring factory.
086     * @param n numerator polynomial.
087     * @param d denominator polynomial.
088     * @param isred true if gcd(n,d) == 1, else false.
089     */
090    protected Quotient(QuotientRing<C> r, GenPolynomial<C> n, GenPolynomial<C> d, boolean isred) {
091        if (d == null || d.isZERO()) {
092            throw new IllegalArgumentException("denominator may not be zero");
093        }
094        ring = r;
095        if (d.signum() < 0) {
096            n = n.negate();
097            d = d.negate();
098        }
099        if (!isred) {
100            // must reduce to lowest terms
101            GenPolynomial<C> gcd = ring.gcd(n, d);
102            if (false || debug) {
103                logger.info("gcd = " + gcd);
104            }
105            //GenPolynomial<C> gcd = ring.ring.getONE();
106            if (!gcd.isONE()) {
107                //logger.info("gcd = " + gcd);
108                n = ring.divide(n, gcd);
109                d = ring.divide(d, gcd);
110            }
111        }
112        C lc = d.leadingBaseCoefficient();
113        if (!lc.isONE() && lc.isUnit()) {
114            lc = lc.inverse();
115            n = n.multiply(lc);
116            d = d.multiply(lc);
117        }
118        num = n;
119        den = d;
120    }
121
122
123    /**
124     * Get the corresponding element factory.
125     * @return factory for this Element.
126     * @see edu.jas.structure.Element#factory()
127     */
128    public QuotientRing<C> factory() {
129        return ring;
130    }
131
132
133    /**
134     * Numerator.
135     * @see edu.jas.structure.QuotPair#numerator()
136     */
137    public GenPolynomial<C> numerator() {
138        return num;
139    }
140
141
142    /**
143     * Denominator.
144     * @see edu.jas.structure.QuotPair#denominator()
145     */
146    public GenPolynomial<C> denominator() {
147        return den;
148    }
149
150
151    /**
152     * Clone this.
153     * @see java.lang.Object#clone()
154     */
155    @Override
156    public Quotient<C> copy() {
157        return new Quotient<C>(ring, num, den, true);
158    }
159
160
161    /**
162     * Is Quotient zero.
163     * @return If this is 0 then true is returned, else false.
164     * @see edu.jas.structure.RingElem#isZERO()
165     */
166    public boolean isZERO() {
167        return num.isZERO();
168    }
169
170
171    /**
172     * Is Quotient one.
173     * @return If this is 1 then true is returned, else false.
174     * @see edu.jas.structure.RingElem#isONE()
175     */
176    public boolean isONE() {
177        return num.equals(den);
178    }
179
180
181    /**
182     * Is Quotient a unit.
183     * @return If this is a unit then true is returned, else false.
184     * @see edu.jas.structure.RingElem#isUnit()
185     */
186    public boolean isUnit() {
187        if (num.isZERO()) {
188            return false;
189        }
190        return true;
191    }
192
193
194    /**
195     * Is Qoutient a constant.
196     * @return true, if this has constant numerator and denominator, else false.
197     */
198    public boolean isConstant() {
199        return num.isConstant() && den.isConstant();
200    }
201
202
203    /**
204     * Get the String representation as RingElem.
205     * @see java.lang.Object#toString()
206     */
207    @Override
208    public String toString() {
209        if (PrettyPrint.isTrue()) {
210            String s = "{ " + num.toString(ring.ring.getVars());
211            if (!den.isONE()) {
212                s += " | " + den.toString(ring.ring.getVars());
213            }
214            return s + " }";
215        }
216        return "Quotient[ " + num.toString() + " | " + den.toString() + " ]";
217    }
218
219
220    /**
221     * Get a scripting compatible string representation.
222     * @return script compatible representation for this Element.
223     * @see edu.jas.structure.Element#toScript()
224     */
225    @Override
226    public String toScript() {
227        // Python case
228        if (den.isONE()) {
229            return num.toScript();
230        }
231        if (den.length() == 1 && den.totalDegree() > 1) {
232            return num.toScript() + " / (" + den.toScript() + " )";
233        }
234        return num.toScript() + " / " + den.toScript();
235    }
236
237
238    /**
239     * Get a scripting compatible string representation of the factory.
240     * @return script compatible representation for this ElemFactory.
241     * @see edu.jas.structure.Element#toScriptFactory()
242     */
243    @Override
244    public String toScriptFactory() {
245        // Python case
246        return factory().toScript();
247    }
248
249
250    /**
251     * Quotient comparison.
252     * @param b Quotient.
253     * @return sign(this-b).
254     */
255    @Override
256    public int compareTo(Quotient<C> b) {
257        if (b == null || b.isZERO()) {
258            return this.signum();
259        }
260        if (this.isZERO()) {
261            return -b.signum();
262        }
263        // assume sign(den,b.den) > 0
264        int s1 = num.signum();
265        int s2 = b.num.signum();
266        int t = (s1 - s2) / 2;
267        if (t != 0) {
268            return t;
269        }
270        if (den.compareTo(b.den) == 0) {
271            return num.compareTo(b.num);
272        }
273        GenPolynomial<C> r = num.multiply(b.den);
274        GenPolynomial<C> s = den.multiply(b.num);
275        return r.compareTo(s);
276    }
277
278
279    /**
280     * Comparison with any other object.
281     * @see java.lang.Object#equals(java.lang.Object)
282     */
283    @SuppressWarnings("unchecked")
284    @Override
285    public boolean equals(Object b) {
286        if (b == null) {
287            return false;
288        }
289        if (!(b instanceof Quotient)) {
290            return false;
291        }
292        Quotient<C> a = (Quotient<C>) b;
293        return compareTo(a) == 0;
294        //return num.equals(a.num) && den.equals(a.den);
295    }
296
297
298    /**
299     * Hash code for this quotient.
300     * @see java.lang.Object#hashCode()
301     */
302    @Override
303    public int hashCode() {
304        int h;
305        h = ring.hashCode();
306        h = 37 * h + num.hashCode();
307        h = 37 * h + den.hashCode();
308        return h;
309    }
310
311
312    /**
313     * Quotient absolute value.
314     * @return the absolute value of this.
315     * @see edu.jas.structure.RingElem#abs()
316     */
317    public Quotient<C> abs() {
318        return new Quotient<C>(ring, num.abs(), den, true);
319    }
320
321
322    /**
323     * Quotient summation.
324     * @param S Quotient.
325     * @return this+S.
326     */
327    public Quotient<C> sum(Quotient<C> S) {
328        if (S == null || S.isZERO()) {
329            return this;
330        }
331        if (this.isZERO()) {
332            return S;
333        }
334        GenPolynomial<C> n;
335        if (den.isONE() && S.den.isONE()) {
336            n = num.sum(S.num);
337            return new Quotient<C>(ring, n);
338        }
339        if (den.isONE()) {
340            n = num.multiply(S.den);
341            n = n.sum(S.num);
342            return new Quotient<C>(ring, n, S.den, false);
343        }
344        if (S.den.isONE()) {
345            n = S.num.multiply(den);
346            n = n.sum(num);
347            return new Quotient<C>(ring, n, den, false);
348        }
349        if (den.compareTo(S.den) == 0) {
350            n = num.sum(S.num);
351            return new Quotient<C>(ring, n, den, false);
352        }
353        GenPolynomial<C> d;
354        GenPolynomial<C> sd;
355        GenPolynomial<C> g;
356        g = ring.gcd(den, S.den);
357        if (g.isONE()) {
358            d = den;
359            sd = S.den;
360        } else {
361            d = ring.divide(den, g);
362            sd = ring.divide(S.den, g);
363        }
364        n = num.multiply(sd);
365        n = n.sum(d.multiply(S.num));
366        if (n.isZERO()) {
367            return ring.getZERO();
368        }
369        GenPolynomial<C> f;
370        GenPolynomial<C> dd;
371        dd = den;
372        if (!g.isONE()) {
373            f = ring.gcd(n, g);
374            if (!f.isONE()) {
375                n = ring.divide(n, f);
376                dd = ring.divide(den, f);
377            }
378        }
379        d = dd.multiply(sd);
380        return new Quotient<C>(ring, n, d, true);
381    }
382
383
384    /**
385     * Quotient negate.
386     * @return -this.
387     * @see edu.jas.structure.RingElem#negate()
388     */
389    public Quotient<C> negate() {
390        return new Quotient<C>(ring, num.negate(), den, true);
391    }
392
393
394    /**
395     * Quotient signum.
396     * @see edu.jas.structure.RingElem#signum()
397     * @return signum(this).
398     */
399    public int signum() {
400        // assume sign(den) > 0
401        return num.signum();
402    }
403
404
405    /**
406     * Quotient subtraction.
407     * @param S Quotient.
408     * @return this-S.
409     */
410    public Quotient<C> subtract(Quotient<C> S) {
411        return sum(S.negate());
412    }
413
414
415    /**
416     * Quotient division.
417     * @param S Quotient.
418     * @return this/S.
419     */
420    public Quotient<C> divide(Quotient<C> S) {
421        return multiply(S.inverse());
422    }
423
424
425    /**
426     * Quotient inverse.
427     * @see edu.jas.structure.RingElem#inverse()
428     * @return S with S = 1/this.
429     */
430    public Quotient<C> inverse() {
431        if (num.isZERO()) {
432            throw new ArithmeticException("element not invertible " + this);
433        }
434        return new Quotient<C>(ring, den, num, true);
435    }
436
437
438    /**
439     * Quotient remainder.
440     * @param S Quotient.
441     * @return this - (this/S)*S.
442     */
443    public Quotient<C> remainder(Quotient<C> S) {
444        if (S.isZERO()) {
445            throw new ArithmeticException("element not invertible " + S);
446        }
447        return ring.getZERO();
448    }
449
450
451    /**
452     * Quotient and remainder by division of this by S.
453     * @param S a Quotient
454     * @return [this/S, this - (this/S)*S].
455     */
456    @SuppressWarnings("unchecked")
457    public Quotient<C>[] quotientRemainder(Quotient<C> S) {
458        return new Quotient[] { divide(S), remainder(S) };
459    }
460
461
462    /**
463     * Quotient multiplication.
464     * @param S Quotient.
465     * @return this*S.
466     */
467    public Quotient<C> multiply(Quotient<C> S) {
468        if (S == null || S.isZERO()) {
469            return S;
470        }
471        if (num.isZERO()) {
472            return this;
473        }
474        if (S.isONE()) {
475            return this;
476        }
477        if (this.isONE()) {
478            return S;
479        }
480        GenPolynomial<C> n;
481        if (den.isONE() && S.den.isONE()) {
482            n = num.multiply(S.num);
483            return new Quotient<C>(ring, n, den, true);
484        }
485        GenPolynomial<C> g;
486        GenPolynomial<C> d;
487        if (den.isONE()) {
488            g = ring.gcd(num, S.den);
489            n = ring.divide(num, g);
490            d = ring.divide(S.den, g);
491            n = n.multiply(S.num);
492            return new Quotient<C>(ring, n, d, true);
493        }
494        if (S.den.isONE()) {
495            g = ring.gcd(S.num, den);
496            n = ring.divide(S.num, g);
497            d = ring.divide(den, g);
498            n = n.multiply(num);
499            return new Quotient<C>(ring, n, d, true);
500        }
501        if (den.compareTo(S.den) == 0) { // correct ?
502            d = den.multiply(den);
503            n = num.multiply(S.num);
504            return new Quotient<C>(ring, n, d, true);
505        }
506        GenPolynomial<C> f;
507        GenPolynomial<C> sd;
508        GenPolynomial<C> sn;
509        g = ring.gcd(num, S.den);
510        n = ring.divide(num, g);
511        sd = ring.divide(S.den, g);
512        f = ring.gcd(den, S.num);
513        d = ring.divide(den, f);
514        sn = ring.divide(S.num, f);
515        n = n.multiply(sn);
516        d = d.multiply(sd);
517        return new Quotient<C>(ring, n, d, true);
518    }
519
520
521    /**
522     * Quotient multiplication by GenPolynomial.
523     * @param b GenPolynomial<C>.
524     * @return this*b.
525     */
526    public Quotient<C> multiply(GenPolynomial<C> b) {
527        if (b == null || b.isZERO()) {
528            return ring.getZERO();
529        }
530        if (num.isZERO()) {
531            return this;
532        }
533        if (b.isONE()) {
534            return this;
535        }
536        GenPolynomial<C> gcd = ring.gcd(b, den);
537        GenPolynomial<C> d = den;
538        if (!gcd.isONE()) {
539            b = ring.divide(b, gcd);
540            d = ring.divide(d, gcd);
541        }
542        if (this.isONE()) {
543            return new Quotient<C>(ring, b, d, true);
544        }
545        GenPolynomial<C> n = num.multiply(b);
546        return new Quotient<C>(ring, n, d, true);
547    }
548
549
550    /**
551     * Quotient multiplication by coefficient.
552     * @param b coefficient.
553     * @return this*b.
554     */
555    public Quotient<C> multiply(C b) {
556        if (b == null || b.isZERO()) {
557            return ring.getZERO();
558        }
559        if (num.isZERO()) {
560            return this;
561        }
562        if (b.isONE()) {
563            return this;
564        }
565        GenPolynomial<C> n = num.multiply(b);
566        return new Quotient<C>(ring, n, den, true);
567    }
568
569
570    /**
571     * Quotient monic.
572     * @return this with monic value part.
573     */
574    public Quotient<C> monic() {
575        if (num.isZERO()) {
576            return this;
577        }
578        C lbc = num.leadingBaseCoefficient();
579        if (!lbc.isUnit()) {
580            return this;
581        }
582        lbc = lbc.inverse();
583        //lbc = lbc.abs();
584        GenPolynomial<C> n = num.multiply(lbc);
585        //GenPolynomial<C> d = den.multiply(lbc);
586        return new Quotient<C>(ring, n, den, true);
587    }
588
589
590    /**
591     * Greatest common divisor.
592     * @param b other element.
593     * @return gcd(this,b).
594     */
595    public Quotient<C> gcd(Quotient<C> b) {
596        if (b == null || b.isZERO()) {
597            return this;
598        }
599        if (this.isZERO()) {
600            return b;
601        }
602        if (this.equals(b)) {
603            return this;
604        }
605        return ring.getONE();
606    }
607
608
609    /**
610     * Extended greatest common divisor.
611     * @param b other element.
612     * @return [ gcd(this,b), c1, c2 ] with c1*this + c2*b = gcd(this,b).
613     */
614    @SuppressWarnings("unchecked")
615    public Quotient<C>[] egcd(Quotient<C> b) {
616        Quotient<C>[] ret = (Quotient<C>[]) new Quotient[3];
617        ret[0] = null;
618        ret[1] = null;
619        ret[2] = null;
620        if (b == null || b.isZERO()) {
621            ret[0] = this;
622            return ret;
623        }
624        if (this.isZERO()) {
625            ret[0] = b;
626            return ret;
627        }
628        GenPolynomial<C> two = ring.ring.fromInteger(2);
629        ret[0] = ring.getONE();
630        ret[1] = (this.multiply(two)).inverse();
631        ret[2] = (b.multiply(two)).inverse();
632        return ret;
633    }
634}