Source code

001/*
002 * $Id: WordResidue.java 5934 2018-09-30 11:23:44Z 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("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    @SuppressWarnings("unchecked")
384    public WordResidue<C>[] twosidedDivide(WordResidue<C> S) {
385        List<GenWordPolynomial<C>> L = new ArrayList<GenWordPolynomial<C>>(1);
386        L.add(ring.ring.getZERO());
387        List<GenWordPolynomial<C>> R = new ArrayList<GenWordPolynomial<C>>(1);
388        R.add(ring.ring.getZERO());
389        List<GenWordPolynomial<C>> V = new ArrayList<GenWordPolynomial<C>>(1);
390        V.add(S.val);
391        GenWordPolynomial<C> x = ring.bb.red.normalform(L, R, V, val);
392        GenWordPolynomial<C> y = L.get(0);
393        GenWordPolynomial<C> z = R.get(0);
394        if (!ring.bb.red.isReductionNF(L, R, V, val, x)) {
395            throw new NotDivisibleException("val != x: val = " + val + ", S.val = " + S.val);
396        }
397        WordResidue<C>[] ret = new WordResidue[2];
398        ret[0] = new WordResidue<C>(ring, y);
399        ret[1] = new WordResidue<C>(ring, z);
400        return ret;
401    }
402
403
404    /**
405     * WordResidue right division.
406     * @param S WordResidue.
407     * @return right, with S * right = this
408     */
409    public WordResidue<C> rightDivide(WordResidue<C> S) {
410        if (ring.isField()) {
411            return multiply(S.inverse());
412        }
413        try {
414            return multiply(S.inverse());
415        } catch (NotInvertibleException ignored) {
416            System.out.println("catch: " + ignored);
417            //ignored.printStackTrace();
418            // ignored
419        } catch (UnsupportedOperationException ignored) {
420            //System.out.println("catch: " + ignored);
421            //ignored.printStackTrace();
422            // ignored
423        }
424        List<GenWordPolynomial<C>> R = new ArrayList<GenWordPolynomial<C>>(1);
425        R.add(ring.ring.getZERO());
426        List<GenWordPolynomial<C>> V = new ArrayList<GenWordPolynomial<C>>(1);
427        V.add(S.val);
428        //@SuppressWarnings("unused")
429        GenWordPolynomial<C> x = ring.bb.red.rightNormalform(R, V, val);
430        GenWordPolynomial<C> y = R.get(0);
431        GenWordPolynomial<C> t = S.val.multiply(y).sum(x);
432        if (!val.equals(t)) {
433            throw new NotDivisibleException("val != t: val = " + val + ", t = " + t);
434        }
435        return new WordResidue<C>(ring, y);
436    }
437
438
439    /**
440     * WordResidue inverse.
441     * @see edu.jas.structure.RingElem#inverse()
442     * @return S with S = 1/this if defined.
443     */
444    public WordResidue<C> inverse() {
445        GenWordPolynomial<C> x = ring.ideal.inverse(val);
446        WordResidue<C> xp = new WordResidue<C>(ring, x, 1);
447        if (xp.isZERO()) {
448            throw new NotInvertibleException("(" + x + ") * (" + val + ") = " + x.multiply(val) + " = 0 mod "
449                            + ring.ideal);
450        }
451        if (!xp.multiply(this).isONE()) {
452            throw new NotInvertibleException("(" + x + ") * (" + val + ") = " + x.multiply(val)
453                            + " != 1 mod " + ring.ideal);
454        }
455        return xp;
456    }
457
458
459    /**
460     * WordResidue remainder.
461     * @param S WordResidue.
462     * @return this - (this/S) * S.
463     */
464    public WordResidue<C> remainder(WordResidue<C> S) {
465        List<GenWordPolynomial<C>> V = new ArrayList<GenWordPolynomial<C>>(1);
466        V.add(S.val);
467        GenWordPolynomial<C> x = ring.bb.red.leftNormalform(V, val);
468        return new WordResidue<C>(ring, x);
469    }
470
471
472    /**
473     * WordResidue right remainder.
474     * @param S WordResidue.
475     * @return r = this - S * (S/right), where S * right = this.
476     */
477    public WordResidue<C> rightRemainder(WordResidue<C> S) {
478        List<GenWordPolynomial<C>> V = new ArrayList<GenWordPolynomial<C>>(1);
479        V.add(S.val);
480        GenWordPolynomial<C> x = ring.bb.red.rightNormalform(V, val);
481        return new WordResidue<C>(ring, x);
482    }
483
484
485    /**
486     * WordResidue two-sided remainder.
487     * @param S WordResidue.
488     * @return r = this - left*S*right.
489     */
490    public WordResidue<C> twosidedRemainder(WordResidue<C> S) {
491        List<GenWordPolynomial<C>> V = new ArrayList<GenWordPolynomial<C>>(1);
492        V.add(S.val);
493        GenWordPolynomial<C> x = ring.bb.red.normalform(V, val);
494        WordResidue<C> ret = new WordResidue<C>(ring, x);
495        return ret;
496    }
497
498
499    /**
500     * WordResidue multiplication.
501     * @param S WordResidue.
502     * @return this*S.
503     */
504    public WordResidue<C> multiply(WordResidue<C> S) {
505        GenWordPolynomial<C> x = val.multiply(S.val);
506        int i = -1;
507        if (isunit == 1 && S.isunit == 1) {
508            i = 1;
509        } else if (isunit == 0 || S.isunit == 0) {
510            i = 0;
511        }
512        return new WordResidue<C>(ring, x, i);
513    }
514
515
516    /**
517     * WordResidue multiplication.
518     * @param S GenWordPolynomial.
519     * @return this*S.
520     */
521    public WordResidue<C> multiply(GenWordPolynomial<C> S) {
522        GenWordPolynomial<C> x = val.multiply(S);
523        int i = -1;
524        if (isunit == 1 && S.isUnit()) {
525            i = 1;
526        } else if (isunit == 0 || !S.isUnit()) {
527            i = 0;
528        }
529        return new WordResidue<C>(ring, x, i);
530    }
531
532
533    /*
534     * WordResidue multiplication.
535     * @param s coefficient.
536     * @return this*s.
537     */
538    public WordResidue<C> multiply(C s) {
539        GenWordPolynomial<C> x = val.multiply(s);
540        int i = -1;
541        if (isunit == 1 && s.isUnit()) {
542            i = 1;
543        } else if (isunit == 0 || !s.isUnit()) {
544            i = 0;
545        }
546        return new WordResidue<C>(ring, x, i);
547    }
548
549
550    /**
551     * WordResidue multiplication.
552     * @param e word.
553     * @return this*e.
554     */
555    public WordResidue<C> multiply(Word e) {
556        GenWordPolynomial<C> x = val.multiply(e);
557        int i = -1;
558        if (isunit == 1 && e.isONE()) {
559            i = 1;
560        } else if (isunit == 0 || !e.isONE()) {
561            i = 0;
562        }
563        return new WordResidue<C>(ring, x, i);
564    }
565
566
567    /**
568     * WordResidue monic.
569     * @return this with monic value part.
570     */
571    public WordResidue<C> monic() {
572        return new WordResidue<C>(ring, val.monic(), isunit);
573    }
574
575
576    /**
577     * Greatest common divisor.
578     * @param b other element.
579     * @return gcd(this,b).
580     */
581    public WordResidue<C> gcd(WordResidue<C> b) {
582        throw new UnsupportedOperationException("gcd not implemented");
583        // GenWordPolynomial<C> x = ring.engine.gcd(val, b.val);
584        // int i = -1; // gcd might become a unit
585        // if (x.isONE()) {
586        //     i = 1;
587        // } else {
588        //     System.out.println("WordResidue gcd = " + x);
589        // }
590        // if (isunit == 1 && b.isunit == 1) {
591        //     i = 1;
592        // }
593        // return new WordResidue<C>(ring, x, i);
594    }
595
596
597    /**
598     * Extended greatest common divisor. <b>Note: </b>Not implemented, throws
599     * UnsupportedOperationException.
600     * @param b other element.
601     * @return [ gcd(this,b), c1, c2 ] with c1*this + c2*b = gcd(this,b).
602     */
603    public WordResidue<C>[] egcd(WordResidue<C> b) {
604        throw new UnsupportedOperationException("egcd not implemented");
605    }
606}