Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.poly;
006
007
008import org.apache.logging.log4j.LogManager;
009import org.apache.logging.log4j.Logger;
010
011import edu.jas.kern.PrettyPrint;
012import edu.jas.structure.GcdRingElem;
013import edu.jas.structure.QuotPair;
014import edu.jas.structure.RingElem;
015
016
017/**
018 * Quotient element based on RingElem pairs. Objects of this class are
019 * immutable.
020 * @author Heinz Kredel
021 */
022public class Quotient<C extends RingElem<C>> implements RingElem<Quotient<C>>, QuotPair<C> {
023
024
025    private static final Logger logger = LogManager.getLogger(Quotient.class);
026
027
028    private static 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 C num;
041
042
043    /**
044     * Denominator part of the element data structure.
045     */
046    public final 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 element. The denominator is assumed to be 1.
061     * @param r ring factory.
062     * @param n numerator.
063     */
064    public Quotient(QuotientRing<C> r, 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 element.
072     * @param r ring factory.
073     * @param n numerator.
074     * @param d denominator.
075     */
076    public Quotient(QuotientRing<C> r, C n, 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 element.
084     * @param r ring factory.
085     * @param n numerator.
086     * @param d denominator.
087     * @param isred true if gcd(n,d) == 1, else false.
088     */
089    @SuppressWarnings("unchecked")
090    protected Quotient(QuotientRing<C> r, C n, 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            num = n;
101            den = d;
102            return;
103        }
104        // must reduce to lowest terms
105        if (n instanceof GcdRingElem && d instanceof GcdRingElem) {
106            GcdRingElem ng = (GcdRingElem) n;
107            GcdRingElem dg = (GcdRingElem) d;
108            C gcd = (C) ng.gcd(dg);
109            if (debug) {
110                logger.info("gcd = {}", gcd);
111            }
112            //RingElem<C> gcd = ring.ring.getONE();
113            if (gcd.isONE()) {
114                num = n;
115                den = d;
116            } else {
117                num = n.divide(gcd);
118                den = d.divide(gcd);
119            }
120            // } else { // univariate polynomial?
121        } else {
122            logger.warn("gcd = ????: {}, {}", n.getClass(), d.getClass());
123            num = n;
124            den = d;
125        }
126    }
127
128
129    /**
130     * Get the corresponding element factory.
131     * @return factory for this Element.
132     * @see edu.jas.structure.Element#factory()
133     */
134    public QuotientRing<C> factory() {
135        return ring;
136    }
137
138
139    /**
140     * Numerator.
141     * @see edu.jas.structure.QuotPair#numerator()
142     */
143    public C numerator() {
144        return num;
145    }
146
147
148    /**
149     * Denominator.
150     * @see edu.jas.structure.QuotPair#denominator()
151     */
152    public C denominator() {
153        return den;
154    }
155
156
157    /**
158     * Is Quotient a constant. Not implemented.
159     * @throws UnsupportedOperationException.
160     */
161    public boolean isConstant() {
162        throw new UnsupportedOperationException("isConstant not implemented");
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 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     * Get the String representation as RingElem.
211     * @see java.lang.Object#toString()
212     */
213    @Override
214    public String toString() {
215        if (PrettyPrint.isTrue()) {
216            String s = "{ " + num.toString();
217            if (den.isONE()) {
218                return s + " }";
219            }
220            return s + "| " + den.toString() + " }";
221        }
222        return "Quotient[ " + num.toString() + " / " + den.toString() + " ]";
223    }
224
225
226    /**
227     * Get a scripting compatible string representation.
228     * @return script compatible representation for this Element.
229     * @see edu.jas.structure.Element#toScript()
230     */
231    @Override
232    public String toScript() {
233        // Python case
234        return "Quotient( " + 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        C r = num.multiply(b.den);
261        C s = den.multiply(b.num);
262        C x = r.subtract(s);
263        return x.signum();
264    }
265
266
267    /**
268     * Comparison with any other object.
269     * @see java.lang.Object#equals(java.lang.Object)
270     */
271    @Override
272    @SuppressWarnings("unchecked")
273    public boolean equals(Object b) {
274        if (b == null) {
275            return false;
276        }
277        if (!(b instanceof Quotient)) {
278            return false;
279        }
280        Quotient<C> a = (Quotient<C>) b;
281        return (0 == compareTo(a));
282    }
283
284
285    /**
286     * Hash code for this local.
287     * @see java.lang.Object#hashCode()
288     */
289    @Override
290    public int hashCode() {
291        int h;
292        h = ring.hashCode();
293        h = 37 * h + num.hashCode();
294        h = 37 * h + den.hashCode();
295        return h;
296    }
297
298
299    /**
300     * Quotient absolute value.
301     * @return the absolute value of this.
302     * @see edu.jas.structure.RingElem#abs()
303     */
304    public Quotient<C> abs() {
305        return new Quotient<C>(ring, num.abs(), den, true);
306    }
307
308
309    /**
310     * Quotient summation.
311     * @param S Quotient.
312     * @return this+S.
313     */
314    public Quotient<C> sum(Quotient<C> S) {
315        if (S == null || S.isZERO()) {
316            return this;
317        }
318        C n = num.multiply(S.den);
319        n = n.sum(den.multiply(S.num));
320        C d = den.multiply(S.den);
321        return new Quotient<C>(ring, n, d, false);
322    }
323
324
325    /**
326     * Quotient negate.
327     * @return -this.
328     * @see edu.jas.structure.RingElem#negate()
329     */
330    public Quotient<C> negate() {
331        return new Quotient<C>(ring, num.negate(), den, true);
332    }
333
334
335    /**
336     * Quotient signum.
337     * @see edu.jas.structure.RingElem#signum()
338     * @return signum(this).
339     */
340    public int signum() {
341        return num.signum();
342    }
343
344
345    /**
346     * Quotient subtraction.
347     * @param S Quotient.
348     * @return this-S.
349     */
350    public Quotient<C> subtract(Quotient<C> S) {
351        if (S == null || S.isZERO()) {
352            return this;
353        }
354        C n = num.multiply(S.den);
355        n = n.subtract(den.multiply(S.num));
356        C d = den.multiply(S.den);
357        return new Quotient<C>(ring, n, d, false);
358    }
359
360
361    /**
362     * Quotient division.
363     * @param S Quotient.
364     * @return this/S.
365     */
366    public Quotient<C> divide(Quotient<C> S) {
367        return multiply(S.inverse());
368    }
369
370
371    /**
372     * Quotient inverse.
373     * @see edu.jas.structure.RingElem#inverse()
374     * @return S with S = 1/this.
375     */
376    public Quotient<C> inverse() {
377        return new Quotient<C>(ring, den, num, true);
378    }
379
380
381    /**
382     * Quotient remainder.
383     * @param S Quotient.
384     * @return this - (this/S)*S.
385     */
386    public Quotient<C> remainder(Quotient<C> S) {
387        if (num.isZERO()) {
388            throw new ArithmeticException("element not invertible " + this);
389        }
390        return ring.getZERO();
391    }
392
393
394    /**
395     * Quotient and remainder by division of this by S.
396     * @param S a Quotient
397     * @return [this/S, this - (this/S)*S].
398     */
399    @SuppressWarnings("unchecked")
400    public Quotient<C>[] quotientRemainder(Quotient<C> S) {
401        return new Quotient[] { divide(S), remainder(S) };
402    }
403
404
405    /**
406     * Quotient multiplication.
407     * @param S Quotient.
408     * @return this*S.
409     */
410    public Quotient<C> multiply(Quotient<C> S) {
411        if (S == null || S.isZERO()) {
412            return S;
413        }
414        if (num.isZERO()) {
415            return this;
416        }
417        if (S.isONE()) {
418            return this;
419        }
420        if (this.isONE()) {
421            return S;
422        }
423        C n = num.multiply(S.num);
424        C d = den.multiply(S.den);
425        return new Quotient<C>(ring, n, d, false);
426    }
427
428
429    /**
430     * Quotient monic.
431     * @return this with monic value part.
432     */
433    public Quotient<C> monic() {
434        logger.info("monic not implemented");
435        return this;
436    }
437
438
439    /**
440     * Greatest common divisor. <b>Note:</b> If not defined, throws
441     * UnsupportedOperationException.
442     * @param b other element.
443     * @return gcd(this,b).
444     */
445    public Quotient<C> gcd(Quotient<C> b) {
446        if (b == null || b.isZERO()) {
447            return this;
448        }
449        if (this.isZERO()) {
450            return b;
451        }
452        if (num instanceof GcdRingElem && den instanceof GcdRingElem && b.num instanceof GcdRingElem
453                        && b.den instanceof GcdRingElem) {
454            return ring.getONE();
455        }
456        throw new UnsupportedOperationException("gcd not implemented " + num.getClass().getName());
457    }
458
459
460    /**
461     * Extended greatest common divisor. <b>Note:</b> If not defined, throws
462     * UnsupportedOperationException.
463     * @param b other element.
464     * @return [ gcd(this,b), c1, c2 ] with c1*this + c2*b = gcd(this,b).
465     */
466    @SuppressWarnings("unchecked")
467    public Quotient<C>[] egcd(Quotient<C> b) {
468        Quotient<C>[] ret = (Quotient<C>[]) new Quotient[3];
469        ret[0] = null;
470        ret[1] = null;
471        ret[2] = null;
472        if (b == null || b.isZERO()) {
473            ret[0] = this;
474            return ret;
475        }
476        if (this.isZERO()) {
477            ret[0] = b;
478            return ret;
479        }
480        if (num instanceof GcdRingElem && den instanceof GcdRingElem && b.num instanceof GcdRingElem
481                        && b.den instanceof GcdRingElem) {
482            Quotient<C> two = ring.fromInteger(2);
483            ret[0] = ring.getONE();
484            ret[1] = (this.multiply(two)).inverse();
485            ret[2] = (b.multiply(two)).inverse();
486            return ret;
487        }
488        throw new UnsupportedOperationException("egcd not implemented " + num.getClass().getName());
489    }
490
491}