001/*
002 * $Id: WordResidue.java 5303 2015-08-16 17:11:07Z kredel $
003 */
004
005package edu.jas.application;
006
007
008import java.util.ArrayList;
009import java.util.List;
010
011import edu.jas.kern.PrettyPrint;
012import edu.jas.poly.GenWordPolynomial;
013import edu.jas.poly.Word;
014import edu.jas.structure.GcdRingElem;
015import edu.jas.structure.NoncomRingElem;
016import edu.jas.structure.NotDivisibleException;
017import edu.jas.structure.NotInvertibleException;
018import edu.jas.structure.QuotPair;
019import edu.jas.structure.Value;
020
021
022/**
023 * WordResidue ring element based on GenWordPolynomial with GcdRingElem
024 * interface. Objects of this class are immutable.
025 * @author Heinz Kredel
026 */
027public class WordResidue<C extends GcdRingElem<C>> implements GcdRingElem<WordResidue<C>>,
028                NoncomRingElem<WordResidue<C>>, QuotPair<GenWordPolynomial<C>>, Value<GenWordPolynomial<C>> {
029
030
031    /**
032     * WordResidue class factory data structure.
033     */
034    public final WordResidueRing<C> ring;
035
036
037    /**
038     * Value part of the element data structure.
039     */
040    public final GenWordPolynomial<C> val;
041
042
043    /**
044     * Flag to remember if this residue element is a unit. -1 is unknown, 1 is
045     * unit, 0 not a unit.
046     */
047    protected int isunit = -1; // initially unknown
048
049
050    /**
051     * The constructor creates a WordResidue object from a ring factory.
052     * @param r solvable residue ring factory.
053     */
054    public WordResidue(WordResidueRing<C> r) {
055        this(r, r.ring.getZERO(), 0);
056    }
057
058
059    /**
060     * The constructor creates a WordResidue object from a ring factory and a
061     * polynomial.
062     * @param r solvable residue ring factory.
063     * @param a solvable polynomial.
064     */
065    public WordResidue(WordResidueRing<C> r, GenWordPolynomial<C> a) {
066        this(r, a, -1);
067    }
068
069
070    /**
071     * The constructor creates a WordResidue object from a ring factory, a
072     * polynomial and an indicator if a is a unit.
073     * @param r solvable residue ring factory.
074     * @param a solvable polynomial.
075     * @param u isunit indicator, -1, 0, 1.
076     */
077    public WordResidue(WordResidueRing<C> r, GenWordPolynomial<C> a, int u) {
078        ring = r;
079        val = ring.ideal.normalform(a); //.monic() no go
080        if (u == 0 || u == 1) {
081            isunit = u;
082            return;
083        }
084        if (val.isZERO()) {
085            isunit = 0;
086            return;
087        }
088        if (ring.isField()) {
089            isunit = 1;
090            return;
091        }
092        if (val.isUnit()) {
093            isunit = 1;
094            //} else { // not possible
095            //isunit = 0;
096        }
097        isunit = -1;
098    }
099
100
101    /**
102     * Get the corresponding element factory.
103     * @return factory for this Element.
104     * @see edu.jas.structure.Element#factory()
105     */
106    public WordResidueRing<C> factory() {
107        return ring;
108    }
109
110
111    /**
112     * Value. Returns the value.
113     * @see edu.jas.structure.Value#value()
114     */
115    public GenWordPolynomial<C> value() {
116        return val;
117    }
118
119
120    /**
121     * Numerator. Returns the value.
122     * @see edu.jas.structure.QuotPair#numerator()
123     */
124    public GenWordPolynomial<C> numerator() {
125        return val;
126    }
127
128
129    /**
130     * Denominator. Returns 1.
131     * @see edu.jas.structure.QuotPair#denominator()
132     */
133    public GenWordPolynomial<C> denominator() {
134        return ring.ring.getONE();
135    }
136
137
138    /**
139     * Clone this.
140     * @see java.lang.Object#clone()
141     */
142    @Override
143    public WordResidue<C> copy() {
144        return new WordResidue<C>(ring, val, isunit);
145    }
146
147
148    /**
149     * Is WordResidue zero.
150     * @return If this is 0 then true is returned, else false.
151     * @see edu.jas.structure.RingElem#isZERO()
152     */
153    public boolean isZERO() {
154        return val.isZERO();
155    }
156
157
158    /**
159     * Is WordResidue one.
160     * @return If this is 1 then true is returned, else false.
161     * @see edu.jas.structure.RingElem#isONE()
162     */
163    public boolean isONE() {
164        return val.isONE();
165    }
166
167
168    /**
169     * Is WordResidue unit.
170     * @return If this is a unit then true is returned, else false.
171     * @see edu.jas.structure.RingElem#isUnit()
172     */
173    public boolean isUnit() {
174        if (isunit > 0) {
175            return true;
176        }
177        if (isunit == 0) {
178            return false;
179        }
180        // not jet known
181        boolean u = ring.ideal.isUnit(val);
182        //System.out.println("WordResidue.isUnit " + val);
183        if (u) {
184            isunit = 1; // seems to be wrong for solvable polynomial rings
185        } else {
186            isunit = 0;
187        }
188        return isunit > 0;
189    }
190
191
192    /**
193     * Is WordResidue a constant.
194     * @return true if this.val is a constant polynomial, else false.
195     */
196    public boolean isConstant() {
197        return val.isConstant();
198    }
199
200
201    /**
202     * Get the String representation as RingElem.
203     * @see java.lang.Object#toString()
204     */
205    @Override
206    public String toString() {
207        if (PrettyPrint.isTrue()) {
208            return val.toString();
209        }
210        return "WordResidue[ " + val.toString() + " mod " + ring.toString() + " ]";
211    }
212
213
214    /**
215     * Get a scripting compatible string representation.
216     * @return script compatible representation for this Element.
217     * @see edu.jas.structure.Element#toScript()
218     */
219    @Override
220    public String toScript() {
221        // Python case
222        return val.toScript();
223        // return "PolyWordResidue( " + val.toScript() 
224        //                         + ", " + ring.toScript() + " )";
225    }
226
227
228    /**
229     * Get a scripting compatible string representation of the factory.
230     * @return script compatible representation for this ElemFactory.
231     * @see edu.jas.structure.Element#toScriptFactory()
232     */
233    @Override
234    public String toScriptFactory() {
235        // Python case
236        return factory().toScript();
237    }
238
239
240    /**
241     * WordResidue comparison.
242     * @param b WordResidue.
243     * @return sign(this-b), 0 means that this and b are equivalent in this
244     *         residue class ring.
245     */
246    @Override
247    public int compareTo(WordResidue<C> b) {
248        GenWordPolynomial<C> v = b.val;
249        if (!ring.equals(b.ring)) {
250            v = ring.ideal.normalform(v);
251        }
252        return val.compareTo(v);
253    }
254
255
256    /**
257     * Comparison with any other object.
258     * @see java.lang.Object#equals(java.lang.Object)
259     * @return true means that this and b are equivalent in this residue class
260     *         ring.
261     */
262    @Override
263    @SuppressWarnings("unchecked")
264    public boolean equals(Object b) {
265        if (!(b instanceof WordResidue)) {
266            return false;
267        }
268        WordResidue<C> a = null;
269        try {
270            a = (WordResidue<C>) b;
271        } catch (ClassCastException e) {
272        }
273        if (a == null) {
274            return false;
275        }
276        return compareTo(a) == 0;
277    }
278
279
280    /**
281     * Hash code for this residue.
282     * @see java.lang.Object#hashCode()
283     */
284    @Override
285    public int hashCode() {
286        int h;
287        h = ring.hashCode();
288        h = 37 * h + val.hashCode();
289        return h;
290    }
291
292
293    /**
294     * WordResidue absolute value.
295     * @return the absolute value of this.
296     * @see edu.jas.structure.RingElem#abs()
297     */
298    public WordResidue<C> abs() {
299        return new WordResidue<C>(ring, val.abs(), isunit);
300    }
301
302
303    /**
304     * WordResidue summation.
305     * @param S WordResidue.
306     * @return this+S.
307     */
308    public WordResidue<C> sum(WordResidue<C> S) {
309        return new WordResidue<C>(ring, val.sum(S.val));
310    }
311
312
313    /**
314     * WordResidue negate.
315     * @return -this.
316     * @see edu.jas.structure.RingElem#negate()
317     */
318    public WordResidue<C> negate() {
319        return new WordResidue<C>(ring, val.negate(), isunit);
320    }
321
322
323    /**
324     * WordResidue signum.
325     * @see edu.jas.structure.RingElem#signum()
326     * @return signum(this).
327     */
328    public int signum() {
329        return val.signum();
330    }
331
332
333    /**
334     * WordResidue subtraction.
335     * @param S WordResidue.
336     * @return this-S.
337     */
338    public WordResidue<C> subtract(WordResidue<C> S) {
339        return new WordResidue<C>(ring, val.subtract(S.val));
340    }
341
342
343    /**
344     * WordResidue left division.
345     * @param S WordResidue.
346     * @return left, with left*S = this
347     */
348    public WordResidue<C> divide(WordResidue<C> S) {
349        if (ring.isField()) {
350            return multiply(S.inverse());
351        }
352        try {
353            return multiply(S.inverse());
354        } catch (NotInvertibleException ignored) {
355            System.out.println("catch: " + ignored);
356            //ignored.printStackTrace();
357            // ignored
358        } catch (UnsupportedOperationException ignored) {
359            //System.out.println("catch: " + ignored);
360            //ignored.printStackTrace();
361            // ignored
362        }
363        List<GenWordPolynomial<C>> L = new ArrayList<GenWordPolynomial<C>>(1);
364        L.add(ring.ring.getZERO());
365        List<GenWordPolynomial<C>> V = new ArrayList<GenWordPolynomial<C>>(1);
366        V.add(S.val);
367        //@SuppressWarnings("unused")
368        GenWordPolynomial<C> x = ring.bb.red.leftNormalform(L, V, val);
369        GenWordPolynomial<C> y = L.get(0);
370        GenWordPolynomial<C> t = y.multiply(S.val).sum(x);
371        if (!val.equals(t)) {
372            throw new NotDivisibleException("TODO val != t: val = " + val + ", t = " + t);
373        }
374        return new WordResidue<C>(ring, y);
375    }
376
377
378    /**
379     * WordResidue two-sided division.
380     * @param S WordResidue.
381     * @return [left, right] with left*S*right + remainder = this.
382     */
383    public WordResidue<C>[] twosidedDivide(WordResidue<C> S) {
384        List<GenWordPolynomial<C>> L = new ArrayList<GenWordPolynomial<C>>(1);
385        L.add(ring.ring.getZERO());
386        List<GenWordPolynomial<C>> R = new ArrayList<GenWordPolynomial<C>>(1);
387        R.add(ring.ring.getZERO());
388        List<GenWordPolynomial<C>> V = new ArrayList<GenWordPolynomial<C>>(1);
389        V.add(S.val);
390        GenWordPolynomial<C> x = ring.bb.red.normalform(L, R, V, val);
391        GenWordPolynomial<C> y = L.get(0);
392        GenWordPolynomial<C> z = R.get(0);
393        if (!ring.bb.red.isReductionNF(L, R, V, val, x)) {
394            throw new NotDivisibleException("TODO val != x: val = " + val + ", S.val = " + S.val);
395        }
396        WordResidue<C>[] ret = new WordResidue[2];
397        ret[0] = new WordResidue<C>(ring, y);
398        ret[1] = new WordResidue<C>(ring, z);
399        return ret;
400    }
401
402
403    /**
404     * WordResidue right division.
405     * @param S WordResidue.
406     * @return right, with S * right = this
407     */
408    public WordResidue<C> rightDivide(WordResidue<C> S) {
409        if (ring.isField()) {
410            return multiply(S.inverse());
411        }
412        try {
413            return multiply(S.inverse());
414        } catch (NotInvertibleException ignored) {
415            System.out.println("catch: " + ignored);
416            //ignored.printStackTrace();
417            // ignored
418        } catch (UnsupportedOperationException ignored) {
419            //System.out.println("catch: " + ignored);
420            //ignored.printStackTrace();
421            // ignored
422        }
423        List<GenWordPolynomial<C>> R = new ArrayList<GenWordPolynomial<C>>(1);
424        R.add(ring.ring.getZERO());
425        List<GenWordPolynomial<C>> V = new ArrayList<GenWordPolynomial<C>>(1);
426        V.add(S.val);
427        //@SuppressWarnings("unused")
428        GenWordPolynomial<C> x = ring.bb.red.rightNormalform(R, V, val);
429        GenWordPolynomial<C> y = R.get(0);
430        GenWordPolynomial<C> t = S.val.multiply(y).sum(x);
431        if (!val.equals(t)) {
432            throw new NotDivisibleException("TODO val != t: val = " + val + ", t = " + t);
433        }
434        return new WordResidue<C>(ring, y);
435    }
436
437
438    /**
439     * WordResidue inverse.
440     * @see edu.jas.structure.RingElem#inverse()
441     * @return S with S = 1/this if defined.
442     */
443    public WordResidue<C> inverse() {
444        GenWordPolynomial<C> x = ring.ideal.inverse(val);
445        WordResidue<C> xp = new WordResidue<C>(ring, x, 1);
446        if (xp.isZERO()) {
447            throw new NotInvertibleException("(" + x + ") * (" + val + ") = " + x.multiply(val) + " = 0 mod "
448                            + ring.ideal);
449        }
450        if (!xp.multiply(this).isONE()) {
451            throw new NotInvertibleException("(" + x + ") * (" + val + ") = " + x.multiply(val)
452                            + " != 1 mod " + ring.ideal);
453        }
454        return xp;
455    }
456
457
458    /**
459     * WordResidue remainder.
460     * @param S WordResidue.
461     * @return this - (this/S) * S.
462     */
463    public WordResidue<C> remainder(WordResidue<C> S) {
464        List<GenWordPolynomial<C>> V = new ArrayList<GenWordPolynomial<C>>(1);
465        V.add(S.val);
466        GenWordPolynomial<C> x = ring.bb.red.leftNormalform(V, val);
467        return new WordResidue<C>(ring, x);
468    }
469
470
471    /**
472     * WordResidue right remainder.
473     * @param S WordResidue.
474     * @return r = this - S * (S/right), where S * right = this.
475     */
476    public WordResidue<C> rightRemainder(WordResidue<C> S) {
477        List<GenWordPolynomial<C>> V = new ArrayList<GenWordPolynomial<C>>(1);
478        V.add(S.val);
479        GenWordPolynomial<C> x = ring.bb.red.rightNormalform(V, val);
480        return new WordResidue<C>(ring, x);
481    }
482
483
484    /**
485     * WordResidue two-sided remainder.
486     * @param S WordResidue.
487     * @return r = this - left*S*right.
488     */
489    public WordResidue<C> twosidedRemainder(WordResidue<C> S) {
490        List<GenWordPolynomial<C>> V = new ArrayList<GenWordPolynomial<C>>(1);
491        V.add(S.val);
492        GenWordPolynomial<C> x = ring.bb.red.normalform(V, val);
493        WordResidue<C> ret = new WordResidue<C>(ring, x);
494        return ret;
495    }
496
497
498    /**
499     * WordResidue multiplication.
500     * @param S WordResidue.
501     * @return this*S.
502     */
503    public WordResidue<C> multiply(WordResidue<C> S) {
504        GenWordPolynomial<C> x = val.multiply(S.val);
505        int i = -1;
506        if (isunit == 1 && S.isunit == 1) {
507            i = 1;
508        } else if (isunit == 0 || S.isunit == 0) {
509            i = 0;
510        }
511        return new WordResidue<C>(ring, x, i);
512    }
513
514
515    /**
516     * WordResidue multiplication.
517     * @param S GenWordPolynomial.
518     * @return this*S.
519     */
520    public WordResidue<C> multiply(GenWordPolynomial<C> S) {
521        GenWordPolynomial<C> x = val.multiply(S);
522        int i = -1;
523        if (isunit == 1 && S.isUnit()) {
524            i = 1;
525        } else if (isunit == 0 || !S.isUnit()) {
526            i = 0;
527        }
528        return new WordResidue<C>(ring, x, i);
529    }
530
531
532    /*
533     * WordResidue multiplication.
534     * @param s coefficient.
535     * @return this*s.
536     */
537    public WordResidue<C> multiply(C s) {
538        GenWordPolynomial<C> x = val.multiply(s);
539        int i = -1;
540        if (isunit == 1 && s.isUnit()) {
541            i = 1;
542        } else if (isunit == 0 || !s.isUnit()) {
543            i = 0;
544        }
545        return new WordResidue<C>(ring, x, i);
546    }
547
548
549    /**
550     * WordResidue multiplication.
551     * @param e word.
552     * @return this*e.
553     */
554    public WordResidue<C> multiply(Word e) {
555        GenWordPolynomial<C> x = val.multiply(e);
556        int i = -1;
557        if (isunit == 1 && e.isONE()) {
558            i = 1;
559        } else if (isunit == 0 || !e.isONE()) {
560            i = 0;
561        }
562        return new WordResidue<C>(ring, x, i);
563    }
564
565
566    /**
567     * WordResidue monic.
568     * @return this with monic value part.
569     */
570    public WordResidue<C> monic() {
571        return new WordResidue<C>(ring, val.monic(), isunit);
572    }
573
574
575    /**
576     * Greatest common divisor.
577     * @param b other element.
578     * @return gcd(this,b).
579     */
580    public WordResidue<C> gcd(WordResidue<C> b) {
581        throw new UnsupportedOperationException("gcd not implemented");
582        // GenWordPolynomial<C> x = ring.engine.gcd(val, b.val);
583        // int i = -1; // gcd might become a unit
584        // if (x.isONE()) {
585        //     i = 1;
586        // } else {
587        //     System.out.println("WordResidue gcd = " + x);
588        // }
589        // if (isunit == 1 && b.isunit == 1) {
590        //     i = 1;
591        // }
592        // return new WordResidue<C>(ring, x, i);
593    }
594
595
596    /**
597     * Extended greatest common divisor. <b>Note: </b>Not implemented, throws
598     * UnsupportedOperationException.
599     * @param b other element.
600     * @return [ gcd(this,b), c1, c2 ] with c1*this + c2*b = gcd(this,b).
601     */
602    public WordResidue<C>[] egcd(WordResidue<C> b) {
603        throw new UnsupportedOperationException("egcd not implemented");
604    }
605}