Source code

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