Source code

001/*
002 * $Id: Quotient.java 4957 2014-10-16 23:03:23Z kredel $
003 */
004
005package edu.jas.poly;
006
007
008import org.apache.log4j.Logger;
009
010import edu.jas.structure.GcdRingElem;
011import edu.jas.structure.QuotPair;
012import edu.jas.structure.RingElem;
013
014
015/**
016 * Quotient element based on RingElem pairs. Objects of this class are
017 * immutable.
018 * @author Heinz Kredel
019 */
020public class Quotient<C extends RingElem<C>> implements RingElem<Quotient<C>>, QuotPair<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 C num;
039
040
041    /**
042     * Denominator part of the element data structure.
043     */
044    public final 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 element. The denominator is assumed to be 1.
059     * @param r ring factory.
060     * @param n numerator.
061     */
062    public Quotient(QuotientRing<C> r, 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 element.
070     * @param r ring factory.
071     * @param n numerator.
072     * @param d denominator.
073     */
074    public Quotient(QuotientRing<C> r, C n, 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 element.
082     * @param r ring factory.
083     * @param n numerator.
084     * @param d denominator.
085     * @param isred true if gcd(n,d) == 1, else false.
086     */
087    @SuppressWarnings("unchecked")
088    protected Quotient(QuotientRing<C> r, C n, C d, boolean isred) {
089        if (d == null || d.isZERO()) {
090            throw new IllegalArgumentException("denominator may not be zero");
091        }
092        ring = r;
093        if (d.signum() < 0) {
094            n = n.negate();
095            d = d.negate();
096        }
097        if (isred) {
098            num = n;
099            den = d;
100            return;
101        }
102        // must reduce to lowest terms
103        if (n instanceof GcdRingElem && d instanceof GcdRingElem) {
104            GcdRingElem ng = (GcdRingElem) n;
105            GcdRingElem dg = (GcdRingElem) d;
106            C gcd = (C) ng.gcd(dg);
107            if (debug) {
108                logger.info("gcd = " + gcd);
109            }
110            //RingElem<C> gcd = ring.ring.getONE();
111            if (gcd.isONE()) {
112                num = n;
113                den = d;
114            } else {
115                num = n.divide(gcd);
116                den = d.divide(gcd);
117            }
118            // } else { // univariate polynomial?
119        } else {
120            logger.warn("gcd = ????");
121            num = n;
122            den = d;
123        }
124    }
125
126
127    /**
128     * Get the corresponding element factory.
129     * @return factory for this Element.
130     * @see edu.jas.structure.Element#factory()
131     */
132    public QuotientRing<C> factory() {
133        return ring;
134    }
135
136
137    /**
138     * Numerator.
139     * @see edu.jas.structure.QuotPair#numerator()
140     */
141    public C numerator() {
142        return num;
143    }
144
145
146    /**
147     * Denominator.
148     * @see edu.jas.structure.QuotPair#denominator()
149     */
150    public C denominator() {
151        return den;
152    }
153
154
155    /**
156     * Is Quotient a constant. Not implemented.
157     * @throws UnsupportedOperationException.
158     */
159    public boolean isConstant() {
160        throw new UnsupportedOperationException("isConstant not implemented");
161    }
162
163
164    /**
165     * Clone this.
166     * @see java.lang.Object#clone()
167     */
168    @Override
169    public Quotient<C> copy() {
170        return new Quotient<C>(ring, num, den, true);
171    }
172
173
174    /**
175     * Is Quotient zero.
176     * @return If this is 0 then true is returned, else false.
177     * @see edu.jas.structure.RingElem#isZERO()
178     */
179    public boolean isZERO() {
180        return num.isZERO();
181    }
182
183
184    /**
185     * Is Quotient one.
186     * @return If this is 1 then true is returned, else false.
187     * @see edu.jas.structure.RingElem#isONE()
188     */
189    public boolean isONE() {
190        return num.equals(den);
191    }
192
193
194    /**
195     * Is Quotient unit.
196     * @return If this is a unit then true is returned, else false.
197     * @see edu.jas.structure.RingElem#isUnit()
198     */
199    public boolean isUnit() {
200        if (num.isZERO()) {
201            return false;
202        }
203        return true;
204    }
205
206
207    /**
208     * Get the String representation as RingElem.
209     * @see java.lang.Object#toString()
210     */
211    @Override
212    public String toString() {
213        return "Quotient[ " + num.toString() + " / " + den.toString() + " ]";
214    }
215
216
217    /**
218     * Get a scripting compatible string representation.
219     * @return script compatible representation for this Element.
220     * @see edu.jas.structure.Element#toScript()
221     */
222    @Override
223    public String toScript() {
224        // Python case
225        return "Quotient( " + num.toScript() + " , " + den.toScript() + " )";
226    }
227
228
229    /**
230     * Get a scripting compatible string representation of the factory.
231     * @return script compatible representation for this ElemFactory.
232     * @see edu.jas.structure.Element#toScriptFactory()
233     */
234    @Override
235    public String toScriptFactory() {
236        // Python case
237        return factory().toScript();
238    }
239
240
241    /**
242     * Quotient comparison.
243     * @param b Quotient.
244     * @return sign(this-b).
245     */
246    @Override
247    public int compareTo(Quotient<C> b) {
248        if (b == null || b.isZERO()) {
249            return this.signum();
250        }
251        C r = num.multiply(b.den);
252        C s = den.multiply(b.num);
253        C x = r.subtract(s);
254        return x.signum();
255    }
256
257
258    /**
259     * Comparison with any other object.
260     * @see java.lang.Object#equals(java.lang.Object)
261     */
262    @Override
263    @SuppressWarnings("unchecked")
264    public boolean equals(Object b) {
265        if (b == null) {
266            return false;
267        }
268        if (!(b instanceof Quotient)) {
269            return false;
270        }
271        Quotient<C> a = (Quotient<C>) b;
272        return (0 == compareTo(a));
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        C n = num.multiply(S.den);
310        n = n.sum(den.multiply(S.num));
311        C d = den.multiply(S.den);
312        return new Quotient<C>(ring, n, d, false);
313    }
314
315
316    /**
317     * Quotient negate.
318     * @return -this.
319     * @see edu.jas.structure.RingElem#negate()
320     */
321    public Quotient<C> negate() {
322        return new Quotient<C>(ring, num.negate(), den, true);
323    }
324
325
326    /**
327     * Quotient signum.
328     * @see edu.jas.structure.RingElem#signum()
329     * @return signum(this).
330     */
331    public int signum() {
332        return num.signum();
333    }
334
335
336    /**
337     * Quotient subtraction.
338     * @param S Quotient.
339     * @return this-S.
340     */
341    public Quotient<C> subtract(Quotient<C> S) {
342        if (S == null || S.isZERO()) {
343            return this;
344        }
345        C n = num.multiply(S.den);
346        n = n.subtract(den.multiply(S.num));
347        C d = den.multiply(S.den);
348        return new Quotient<C>(ring, n, d, false);
349    }
350
351
352    /**
353     * Quotient division.
354     * @param S Quotient.
355     * @return this/S.
356     */
357    public Quotient<C> divide(Quotient<C> S) {
358        return multiply(S.inverse());
359    }
360
361
362    /**
363     * Quotient inverse.
364     * @see edu.jas.structure.RingElem#inverse()
365     * @return S with S = 1/this.
366     */
367    public Quotient<C> inverse() {
368        return new Quotient<C>(ring, den, num, true);
369    }
370
371
372    /**
373     * Quotient remainder.
374     * @param S Quotient.
375     * @return this - (this/S)*S.
376     */
377    public Quotient<C> remainder(Quotient<C> S) {
378        if (num.isZERO()) {
379            throw new ArithmeticException("element not invertible " + this);
380        }
381        return ring.getZERO();
382    }
383
384
385    /**
386     * Quotient and remainder by division of this by S.
387     * @param S a Quotient
388     * @return [this/S, this - (this/S)*S].
389     */
390    public Quotient<C>[] quotientRemainder(Quotient<C> S) {
391        return new Quotient[] { divide(S), remainder(S) };
392    }
393
394
395    /**
396     * Quotient multiplication.
397     * @param S Quotient.
398     * @return this*S.
399     */
400    public Quotient<C> multiply(Quotient<C> S) {
401        if (S == null || S.isZERO()) {
402            return S;
403        }
404        if (num.isZERO()) {
405            return this;
406        }
407        if (S.isONE()) {
408            return this;
409        }
410        if (this.isONE()) {
411            return S;
412        }
413        C n = num.multiply(S.num);
414        C d = den.multiply(S.den);
415        return new Quotient<C>(ring, n, d, false);
416    }
417
418
419    /**
420     * Quotient monic.
421     * @return this with monic value part.
422     */
423    public Quotient<C> monic() {
424        logger.info("monic not implemented");
425        return this;
426    }
427
428
429    /**
430     * Greatest common divisor. <b>Note:</b> If not defined, throws
431     * UnsupportedOperationException.
432     * @param b other element.
433     * @return gcd(this,b).
434     */
435    public Quotient<C> gcd(Quotient<C> b) {
436        if (b == null || b.isZERO()) {
437            return this;
438        }
439        if (this.isZERO()) {
440            return b;
441        }
442        if (num instanceof GcdRingElem && den instanceof GcdRingElem && b.num instanceof GcdRingElem
443                        && b.den instanceof GcdRingElem) {
444            return ring.getONE();
445        }
446        throw new UnsupportedOperationException("gcd not implemented " + num.getClass().getName());
447    }
448
449
450    /**
451     * Extended greatest common divisor. <b>Note:</b> If not defined, throws
452     * UnsupportedOperationException.
453     * @param b other element.
454     * @return [ gcd(this,b), c1, c2 ] with c1*this + c2*b = gcd(this,b).
455     */
456    public Quotient<C>[] egcd(Quotient<C> b) {
457        @SuppressWarnings("cast")
458        Quotient<C>[] ret = (Quotient<C>[]) new Quotient[3];
459        ret[0] = null;
460        ret[1] = null;
461        ret[2] = null;
462        if (b == null || b.isZERO()) {
463            ret[0] = this;
464            return ret;
465        }
466        if (this.isZERO()) {
467            ret[0] = b;
468            return ret;
469        }
470        if (num instanceof GcdRingElem && den instanceof GcdRingElem && b.num instanceof GcdRingElem
471                        && b.den instanceof GcdRingElem) {
472            Quotient<C> two = ring.fromInteger(2);
473            ret[0] = ring.getONE();
474            ret[1] = (this.multiply(two)).inverse();
475            ret[2] = (b.multiply(two)).inverse();
476            return ret;
477        }
478        throw new UnsupportedOperationException("egcd not implemented " + num.getClass().getName());
479    }
480
481}