Source code

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