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