001/*
002 * $Id: SolvableLocalResidue.java 5868 2018-07-20 15:44:13Z kredel $
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 = " + n + ", NF(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 = FDUtil.<C> 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 = FDUtil.<C> 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] + ") ("
425                            + S.den + ")");
426        }
427        d = oc[0].multiply(den);
428        n1 = oc[0].multiply(num);
429        n2 = oc[1].multiply(S.num);
430        n = (GenSolvablePolynomial<C>) n1.sum(n2);
431        //logger.info("n = " + n + ", d = " + d);
432        return new SolvableLocalResidue<C>(ring, n, d, false);
433    }
434
435
436    /**
437     * SolvableLocalResidue negate.
438     * @return -this.
439     * @see edu.jas.structure.RingElem#negate()
440     */
441    public SolvableLocalResidue<C> negate() {
442        return new SolvableLocalResidue<C>(ring, (GenSolvablePolynomial<C>) num.negate(), den, true);
443    }
444
445
446    /**
447     * SolvableLocalResidue signum.
448     * @see edu.jas.structure.RingElem#signum()
449     * @return signum(this).
450     */
451    public int signum() {
452        // assume sign(den) > 0
453        return num.signum();
454    }
455
456
457    /**
458     * SolvableLocalResidue subtraction.
459     * @param S SolvableLocalResidue.
460     * @return this-S.
461     */
462    public SolvableLocalResidue<C> subtract(SolvableLocalResidue<C> S) {
463        return sum(S.negate());
464    }
465
466
467    /**
468     * SolvableLocalResidue division.
469     * @param S SolvableLocalResidue.
470     * @return this/S.
471     */
472    public SolvableLocalResidue<C> divide(SolvableLocalResidue<C> S) {
473        return multiply(S.inverse());
474    }
475
476
477    /**
478     * SolvableLocalResidue inverse.
479     * @see edu.jas.structure.RingElem#inverse()
480     * @return S with S = 1/this.
481     */
482    public SolvableLocalResidue<C> inverse() {
483        if (num.isZERO()) {
484            throw new ArithmeticException("element not invertible " + this);
485        }
486        return new SolvableLocalResidue<C>(ring, den, num, false); // true
487    }
488
489
490    /**
491     * SolvableLocalResidue remainder.
492     * @param S SolvableLocalResidue.
493     * @return this - (this/S)*S.
494     */
495    public SolvableLocalResidue<C> remainder(SolvableLocalResidue<C> S) {
496        if (S.isZERO()) {
497            throw new ArithmeticException("element not invertible " + S);
498        }
499        return ring.getZERO();
500    }
501
502
503    /**
504     * SolvableLocalResidue multiplication.
505     * @param S SolvableLocalResidue.
506     * @return this*S.
507     */
508    public SolvableLocalResidue<C> multiply(SolvableLocalResidue<C> S) {
509        if (S == null || S.isZERO()) {
510            return S;
511        }
512        if (num.isZERO()) {
513            return this;
514        }
515        if (S.isONE()) {
516            return this;
517        }
518        if (this.isONE()) {
519            return S;
520        }
521        GenSolvablePolynomial<C> n, d;
522        if (den.isONE() && S.den.isONE()) {
523            n = num.multiply(S.num);
524            return new SolvableLocalResidue<C>(ring, n, den, false); // true
525        }
526        /* wrong:
527        if (den.isONE()) { }
528        if (S.den.isONE()) { }
529        if ( den.compareTo(S.den) == 0 ) { }
530        */
531        GenSolvablePolynomial<C>[] oc = ring.engine.leftOreCond(num, S.den);
532        if (debug) {
533            System.out.println("oc[0] num =mult= oc[1] S.den: (" + oc[0] + ") (" + num + ") = (" + oc[1]
534                            + ") (" + S.den + ")");
535        }
536        n = oc[1].multiply(S.num);
537        d = oc[0].multiply(den);
538        return new SolvableLocalResidue<C>(ring, n, d, false);
539    }
540
541
542    /**
543     * SolvableLocalResidue multiplication by GenSolvablePolynomial.
544     * @param b GenSolvablePolynomial<C>.
545     * @return this*b.
546     */
547    public SolvableLocalResidue<C> multiply(GenSolvablePolynomial<C> b) {
548        if (b == null || b.isZERO()) {
549            return ring.getZERO();
550        }
551        if (num.isZERO()) {
552            return this;
553        }
554        if (b.isONE()) {
555            return this;
556        }
557        SolvableLocalResidue<C> B = new SolvableLocalResidue<C>(ring, b);
558        return multiply(B);
559    }
560
561
562    /**
563     * SolvableLocalResidue multiplication by coefficient.
564     * @param b coefficient.
565     * @return this*b.
566     */
567    public SolvableLocalResidue<C> multiply(C b) {
568        if (b == null || b.isZERO()) {
569            return ring.getZERO();
570        }
571        if (num.isZERO()) {
572            return this;
573        }
574        if (b.isONE()) {
575            return this;
576        }
577        GenSolvablePolynomial<C> B = ring.ring.getONE().multiply(b);
578        return multiply(B);
579    }
580
581
582    /**
583     * SolvableLocalResidue multiplication by exponent.
584     * @param e exponent vector.
585     * @return this*b.
586     */
587    public SolvableLocalResidue<C> multiply(ExpVector e) {
588        if (e == null || e.isZERO()) {
589            return this;
590        }
591        if (num.isZERO()) {
592            return this;
593        }
594        GenSolvablePolynomial<C> B = ring.ring.getONE().multiply(e);
595        return multiply(B);
596    }
597
598
599    /**
600     * SolvableLocalResidue monic.
601     * @return this with monic value part.
602     */
603    public SolvableLocalResidue<C> monic() {
604        if (num.isZERO()) {
605            return this;
606        }
607        return this;
608    }
609
610
611    /**
612     * Greatest common divisor.
613     * @param b other element.
614     * @return gcd(this,b).
615     */
616    public SolvableLocalResidue<C> gcd(SolvableLocalResidue<C> b) {
617        if (b == null || b.isZERO()) {
618            return this;
619        }
620        if (this.isZERO()) {
621            return b;
622        }
623        return ring.getONE();
624    }
625
626
627    /**
628     * Extended greatest common divisor.
629     * @param b other element.
630     * @return [ gcd(this,b), c1, c2 ] with c1*this + c2*b = gcd(this,b).
631     */
632    @SuppressWarnings("unchecked")
633    public SolvableLocalResidue<C>[] egcd(SolvableLocalResidue<C> b) {
634        SolvableLocalResidue<C>[] ret = (SolvableLocalResidue<C>[]) new SolvableLocalResidue[3];
635        ret[0] = null;
636        ret[1] = null;
637        ret[2] = null;
638        if (b == null || b.isZERO()) {
639            ret[0] = this;
640            return ret;
641        }
642        if (this.isZERO()) {
643            ret[0] = b;
644            return ret;
645        }
646        GenSolvablePolynomial<C> two = ring.ring.fromInteger(2);
647        ret[0] = ring.getONE();
648        ret[1] = (this.multiply(two)).inverse();
649        ret[2] = (b.multiply(two)).inverse();
650        return ret;
651    }
652
653}