Source code

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