Source code

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