Source code

001/*
002 * $Id$
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 (debug) {
103                logger.debug("gcd = {}", gcd);
104            }
105            //GenPolynomial<C> gcd = ring.ring.getONE();
106            if (!gcd.isONE()) {
107                //logger.debug("gcd = {}", gcd);
108                n = ring.divide(n, gcd);
109                d = ring.divide(d, gcd);
110            }
111        }
112        C coeff;
113        switch (QuotientRing.quoNorm) { //ring.quoNorm
114        case normNumLead:
115            coeff = n.leadingBaseCoefficient();
116            break;
117        case normNumTrail:
118            coeff = n.trailingBaseCoefficient();
119            break;
120        case normDenTrail:
121            coeff = d.trailingBaseCoefficient();
122            break;
123        case normDenLead:
124        default:
125            coeff = d.leadingBaseCoefficient();
126            break;
127        }
128        if (!coeff.isONE() && coeff.isUnit()) {
129            coeff = coeff.inverse();
130            n = n.multiply(coeff);
131            d = d.multiply(coeff);
132        }
133        num = n;
134        den = d;
135    }
136
137
138    /**
139     * Get the corresponding element factory.
140     * @return factory for this Element.
141     * @see edu.jas.structure.Element#factory()
142     */
143    public QuotientRing<C> factory() {
144        return ring;
145    }
146
147
148    /**
149     * Numerator.
150     * @see edu.jas.structure.QuotPair#numerator()
151     */
152    public GenPolynomial<C> numerator() {
153        return num;
154    }
155
156
157    /**
158     * Denominator.
159     * @see edu.jas.structure.QuotPair#denominator()
160     */
161    public GenPolynomial<C> denominator() {
162        return den;
163    }
164
165
166    /**
167     * Clone this.
168     * @see java.lang.Object#clone()
169     */
170    @Override
171    public Quotient<C> copy() {
172        return new Quotient<C>(ring, num, den, true);
173    }
174
175
176    /**
177     * Is Quotient zero.
178     * @return If this is 0 then true is returned, else false.
179     * @see edu.jas.structure.RingElem#isZERO()
180     */
181    public boolean isZERO() {
182        return num.isZERO();
183    }
184
185
186    /**
187     * Is Quotient one.
188     * @return If this is 1 then true is returned, else false.
189     * @see edu.jas.structure.RingElem#isONE()
190     */
191    public boolean isONE() {
192        return num.equals(den);
193    }
194
195
196    /**
197     * Is Quotient a unit.
198     * @return If this is a unit then true is returned, else false.
199     * @see edu.jas.structure.RingElem#isUnit()
200     */
201    public boolean isUnit() {
202        if (num.isZERO()) {
203            return false;
204        }
205        return true;
206    }
207
208
209    /**
210     * Is Qoutient a constant.
211     * @return true, if this has constant numerator and denominator, else false.
212     */
213    public boolean isConstant() {
214        return num.isConstant() && den.isConstant();
215    }
216
217
218    /**
219     * Get the String representation as RingElem.
220     * @see java.lang.Object#toString()
221     */
222    @Override
223    public String toString() {
224        if (PrettyPrint.isTrue()) {
225            String s = "{ " + num.toString(ring.ring.getVars());
226            if (!den.isONE()) {
227                s += " | " + den.toString(ring.ring.getVars());
228            }
229            return s + " }";
230        }
231        return "Quotient[ " + num.toString() + " | " + den.toString() + " ]";
232    }
233
234
235    /**
236     * Get a scripting compatible string representation.
237     * @return script compatible representation for this Element.
238     * @see edu.jas.structure.Element#toScript()
239     */
240    @Override
241    public String toScript() {
242        // Python case
243        if (den.isONE()) {
244            return num.toScript();
245        }
246        if (den.length() == 1 && den.totalDegree() > 1) {
247            return num.toScript() + " / (" + den.toScript() + " )";
248        }
249        return num.toScript() + " / " + den.toScript();
250    }
251
252
253    /**
254     * Get a scripting compatible string representation of the factory.
255     * @return script compatible representation for this ElemFactory.
256     * @see edu.jas.structure.Element#toScriptFactory()
257     */
258    @Override
259    public String toScriptFactory() {
260        // Python case
261        return factory().toScript();
262    }
263
264
265    /**
266     * Quotient comparison.
267     * @param b Quotient.
268     * @return sign(this-b).
269     */
270    @Override
271    public int compareTo(Quotient<C> b) {
272        if (b == null || b.isZERO()) {
273            return this.signum();
274        }
275        if (this.isZERO()) {
276            return -b.signum();
277        }
278        // assume sign(den,b.den) > 0
279        int s1 = num.signum();
280        int s2 = b.num.signum();
281        int t = (s1 - s2) / 2;
282        if (t != 0) {
283            return t;
284        }
285        if (den.compareTo(b.den) == 0) {
286            return num.compareTo(b.num);
287        }
288        GenPolynomial<C> r = num.multiply(b.den);
289        GenPolynomial<C> s = den.multiply(b.num);
290        return r.compareTo(s);
291    }
292
293
294    /**
295     * Comparison with any other object.
296     * @see java.lang.Object#equals(java.lang.Object)
297     */
298    @SuppressWarnings("unchecked")
299    @Override
300    public boolean equals(Object b) {
301        if (b == null) {
302            return false;
303        }
304        if (!(b instanceof Quotient)) {
305            return false;
306        }
307        Quotient<C> a = (Quotient<C>) b;
308        return compareTo(a) == 0;
309        //return num.equals(a.num) && den.equals(a.den);
310    }
311
312
313    /**
314     * Hash code for this quotient.
315     * @see java.lang.Object#hashCode()
316     */
317    @Override
318    public int hashCode() {
319        int h;
320        h = ring.hashCode();
321        h = 37 * h + num.hashCode();
322        h = 37 * h + den.hashCode();
323        return h;
324    }
325
326
327    /**
328     * Quotient absolute value.
329     * @return the absolute value of this.
330     * @see edu.jas.structure.RingElem#abs()
331     */
332    public Quotient<C> abs() {
333        return new Quotient<C>(ring, num.abs(), den, true);
334    }
335
336
337    /**
338     * Quotient summation.
339     * @param S Quotient.
340     * @return this+S.
341     */
342    public Quotient<C> sum(Quotient<C> S) {
343        if (S == null || S.isZERO()) {
344            return this;
345        }
346        if (this.isZERO()) {
347            return S;
348        }
349        GenPolynomial<C> n;
350        if (den.isONE() && S.den.isONE()) {
351            n = num.sum(S.num);
352            return new Quotient<C>(ring, n);
353        }
354        if (den.isONE()) {
355            n = num.multiply(S.den);
356            n = n.sum(S.num);
357            return new Quotient<C>(ring, n, S.den, false);
358        }
359        if (S.den.isONE()) {
360            n = S.num.multiply(den);
361            n = n.sum(num);
362            return new Quotient<C>(ring, n, den, false);
363        }
364        if (den.compareTo(S.den) == 0) {
365            n = num.sum(S.num);
366            return new Quotient<C>(ring, n, den, false);
367        }
368        GenPolynomial<C> d;
369        GenPolynomial<C> sd;
370        GenPolynomial<C> g;
371        g = ring.gcd(den, S.den);
372        if (g.isONE()) {
373            d = den;
374            sd = S.den;
375        } else {
376            d = ring.divide(den, g);
377            sd = ring.divide(S.den, g);
378        }
379        n = num.multiply(sd);
380        n = n.sum(d.multiply(S.num));
381        if (n.isZERO()) {
382            return ring.getZERO();
383        }
384        GenPolynomial<C> f;
385        GenPolynomial<C> dd;
386        dd = den;
387        if (!g.isONE()) {
388            f = ring.gcd(n, g);
389            if (!f.isONE()) {
390                n = ring.divide(n, f);
391                dd = ring.divide(den, f);
392            }
393        }
394        d = dd.multiply(sd);
395        return new Quotient<C>(ring, n, d, true);
396    }
397
398
399    /**
400     * Quotient negate.
401     * @return -this.
402     * @see edu.jas.structure.RingElem#negate()
403     */
404    public Quotient<C> negate() {
405        return new Quotient<C>(ring, num.negate(), den, true);
406    }
407
408
409    /**
410     * Quotient signum.
411     * @see edu.jas.structure.RingElem#signum()
412     * @return signum(this).
413     */
414    public int signum() {
415        // assume sign(den) > 0
416        return num.signum();
417    }
418
419
420    /**
421     * Quotient subtraction.
422     * @param S Quotient.
423     * @return this-S.
424     */
425    public Quotient<C> subtract(Quotient<C> S) {
426        return sum(S.negate());
427    }
428
429
430    /**
431     * Quotient division.
432     * @param S Quotient.
433     * @return this/S.
434     */
435    public Quotient<C> divide(Quotient<C> S) {
436        return multiply(S.inverse());
437    }
438
439
440    /**
441     * Quotient inverse.
442     * @see edu.jas.structure.RingElem#inverse()
443     * @return S with S = 1/this.
444     */
445    public Quotient<C> inverse() {
446        if (num.isZERO()) {
447            throw new ArithmeticException("element not invertible " + this);
448        }
449        return new Quotient<C>(ring, den, num, true);
450    }
451
452
453    /**
454     * Quotient remainder.
455     * @param S Quotient.
456     * @return this - (this/S)*S.
457     */
458    public Quotient<C> remainder(Quotient<C> S) {
459        if (S.isZERO()) {
460            throw new ArithmeticException("element not invertible " + S);
461        }
462        return ring.getZERO();
463    }
464
465
466    /**
467     * Quotient and remainder by division of this by S.
468     * @param S a Quotient
469     * @return [this/S, this - (this/S)*S].
470     */
471    @SuppressWarnings("unchecked")
472    public Quotient<C>[] quotientRemainder(Quotient<C> S) {
473        return new Quotient[] { divide(S), remainder(S) };
474    }
475
476
477    /**
478     * Quotient multiplication.
479     * @param S Quotient.
480     * @return this*S.
481     */
482    public Quotient<C> multiply(Quotient<C> S) {
483        if (S == null || S.isZERO()) {
484            return S;
485        }
486        if (num.isZERO()) {
487            return this;
488        }
489        if (S.isONE()) {
490            return this;
491        }
492        if (this.isONE()) {
493            return S;
494        }
495        GenPolynomial<C> n;
496        if (den.isONE() && S.den.isONE()) {
497            n = num.multiply(S.num);
498            return new Quotient<C>(ring, n, den, true);
499        }
500        GenPolynomial<C> g;
501        GenPolynomial<C> d;
502        if (den.isONE()) {
503            g = ring.gcd(num, S.den);
504            n = ring.divide(num, g);
505            d = ring.divide(S.den, g);
506            n = n.multiply(S.num);
507            return new Quotient<C>(ring, n, d, true);
508        }
509        if (S.den.isONE()) {
510            g = ring.gcd(S.num, den);
511            n = ring.divide(S.num, g);
512            d = ring.divide(den, g);
513            n = n.multiply(num);
514            return new Quotient<C>(ring, n, d, true);
515        }
516        if (den.compareTo(S.den) == 0) { // correct ?
517            d = den.multiply(den);
518            n = num.multiply(S.num);
519            return new Quotient<C>(ring, n, d, true);
520        }
521        GenPolynomial<C> f;
522        GenPolynomial<C> sd;
523        GenPolynomial<C> sn;
524        g = ring.gcd(num, S.den);
525        n = ring.divide(num, g);
526        sd = ring.divide(S.den, g);
527        f = ring.gcd(den, S.num);
528        d = ring.divide(den, f);
529        sn = ring.divide(S.num, f);
530        n = n.multiply(sn);
531        d = d.multiply(sd);
532        return new Quotient<C>(ring, n, d, true);
533    }
534
535
536    /**
537     * Quotient multiplication by GenPolynomial.
538     * @param b GenPolynomial<C>.
539     * @return this*b.
540     */
541    public Quotient<C> multiply(GenPolynomial<C> b) {
542        if (b == null || b.isZERO()) {
543            return ring.getZERO();
544        }
545        if (num.isZERO()) {
546            return this;
547        }
548        if (b.isONE()) {
549            return this;
550        }
551        GenPolynomial<C> gcd = ring.gcd(b, den);
552        GenPolynomial<C> d = den;
553        if (!gcd.isONE()) {
554            b = ring.divide(b, gcd);
555            d = ring.divide(d, gcd);
556        }
557        if (this.isONE()) {
558            return new Quotient<C>(ring, b, d, true);
559        }
560        GenPolynomial<C> n = num.multiply(b);
561        return new Quotient<C>(ring, n, d, true);
562    }
563
564
565    /**
566     * Quotient multiplication by coefficient.
567     * @param b coefficient.
568     * @return this*b.
569     */
570    public Quotient<C> multiply(C b) {
571        if (b == null || b.isZERO()) {
572            return ring.getZERO();
573        }
574        if (num.isZERO()) {
575            return this;
576        }
577        if (b.isONE()) {
578            return this;
579        }
580        GenPolynomial<C> n = num.multiply(b);
581        return new Quotient<C>(ring, n, den, true);
582    }
583
584
585    /**
586     * Quotient monic.
587     * @return this with monic value part.
588     */
589    public Quotient<C> monic() {
590        if (num.isZERO()) {
591            return this;
592        }
593        C lbc = num.leadingBaseCoefficient();
594        if (!lbc.isUnit()) {
595            return this;
596        }
597        lbc = lbc.inverse();
598        //lbc = lbc.abs();
599        GenPolynomial<C> n = num.multiply(lbc);
600        //GenPolynomial<C> d = den.multiply(lbc);
601        return new Quotient<C>(ring, n, den, true);
602    }
603
604
605    /**
606     * Greatest common divisor.
607     * @param b other element.
608     * @return gcd(this,b).
609     */
610    public Quotient<C> gcd(Quotient<C> b) {
611        if (b == null || b.isZERO()) {
612            return this;
613        }
614        if (this.isZERO()) {
615            return b;
616        }
617        if (this.equals(b)) {
618            return this;
619        }
620        return ring.getONE();
621    }
622
623
624    /**
625     * Extended greatest common divisor.
626     * @param b other element.
627     * @return [ gcd(this,b), c1, c2 ] with c1*this + c2*b = gcd(this,b).
628     */
629    @SuppressWarnings("unchecked")
630    public Quotient<C>[] egcd(Quotient<C> b) {
631        Quotient<C>[] ret = (Quotient<C>[]) new Quotient[3];
632        ret[0] = null;
633        ret[1] = null;
634        ret[2] = null;
635        if (b == null || b.isZERO()) {
636            ret[0] = this;
637            return ret;
638        }
639        if (this.isZERO()) {
640            ret[0] = b;
641            return ret;
642        }
643        GenPolynomial<C> two = ring.ring.fromInteger(2);
644        ret[0] = ring.getONE();
645        ret[1] = (this.multiply(two)).inverse();
646        ret[2] = (b.multiply(two)).inverse();
647        return ret;
648    }
649}