Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.poly;
006
007
008import org.apache.logging.log4j.LogManager;
009import org.apache.logging.log4j.Logger;
010
011import edu.jas.kern.PrettyPrint;
012import edu.jas.structure.GcdRingElem;
013import edu.jas.structure.NotInvertibleException;
014import edu.jas.structure.RingElem;
015
016
017/**
018 * Residue element based on RingElem residue. Objects of this class are (nearly)
019 * immutable.
020 * @author Heinz Kredel
021 */
022public class Residue<C extends RingElem<C>> implements RingElem<Residue<C>> {
023
024
025    private static final Logger logger = LogManager.getLogger(Residue.class);
026
027
028    private static final boolean debug = logger.isDebugEnabled();
029
030
031    /**
032     * Residue class factory data structure.
033     */
034    protected final ResidueRing<C> ring;
035
036
037    /**
038     * Value part of the element data structure.
039     */
040    protected final 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 Residue object from a ring factory.
052     * @param r ring factory.
053     */
054    public Residue(ResidueRing<C> r) {
055        this(r, r.ring.getZERO(), 0);
056    }
057
058
059    /**
060     * The constructor creates a Residue object from a ring factory and a ring
061     * element.
062     * @param r ring factory.
063     * @param a ring element.
064     */
065    public Residue(ResidueRing<C> r, C a) {
066        this(r, a, -1);
067    }
068
069
070    /**
071     * The constructor creates a Residue object from a ring factory, a ring
072     * element and an indicator if a is a unit.
073     * @param r ring factory.
074     * @param a ring element.
075     * @param u isunit indicator, -1, 0, 1.
076     */
077    public Residue(ResidueRing<C> r, C a, int u) {
078        ring = r;
079        C v = a.remainder(ring.modul);
080        if (v.signum() < 0) {
081            v = v.sum(ring.modul);
082        }
083        val = v;
084        if (u == 0 || u == 1) {
085            isunit = u;
086            return;
087        }
088        if (val.isZERO()) {
089            isunit = 0;
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 ResidueRing<C> factory() {
107        return ring;
108    }
109
110
111    /**
112     * Copy this.
113     * @see edu.jas.structure.Element#copy()
114     */
115    @Override
116    public Residue<C> copy() {
117        return new Residue<C>(ring, val);
118    }
119
120
121    /**
122     * Is Residue zero.
123     * @return If this is 0 then true is returned, else false.
124     * @see edu.jas.structure.RingElem#isZERO()
125     */
126    public boolean isZERO() {
127        return val.equals(ring.ring.getZERO());
128    }
129
130
131    /**
132     * Is Residue one.
133     * @return If this is 1 then true is returned, else false.
134     * @see edu.jas.structure.RingElem#isONE()
135     */
136    public boolean isONE() {
137        return val.equals(ring.ring.getONE());
138    }
139
140
141    /**
142     * Is Residue unit.
143     * @return If this is a unit then true is returned, else false.
144     * @see edu.jas.structure.RingElem#isUnit()
145     */
146    @SuppressWarnings("unchecked")
147    public boolean isUnit() {
148        if (isunit == 1) {
149            return true;
150        }
151        if (isunit == 0) {
152            return false;
153        }
154        // val.isUnit() already tested
155        // not jet known
156        if (val instanceof GcdRingElem && ring.modul instanceof GcdRingElem) {
157            GcdRingElem v = (GcdRingElem) val;
158            GcdRingElem m = (GcdRingElem) ring.modul;
159            C gcd = (C) v.gcd(m);
160            if (debug) {
161                logger.info("gcd = {}", gcd);
162            }
163            boolean u = gcd.isONE();
164            if (u) {
165                isunit = 1;
166            } else {
167                isunit = 0;
168            }
169            return u;
170        }
171        // still unknown
172        return false;
173    }
174
175
176    /**
177     * Get the String representation as RingElem.
178     * @see java.lang.Object#toString()
179     */
180    @Override
181    public String toString() {
182        if (PrettyPrint.isTrue()) {
183            String s = "{ " + val.toString() + " }";
184            return s;
185        }
186        return "Residue[ " + val.toString() + " mod " + ring.toString() + " ]";
187    }
188
189
190    /**
191     * Get a scripting compatible string representation.
192     * @return script compatible representation for this Element.
193     * @see edu.jas.structure.Element#toScript()
194     */
195    @Override
196    public String toScript() {
197        // Python case
198        return "Residue( " + val.toScript() + " , " + ring.toScript() + " )";
199    }
200
201
202    /**
203     * Get a scripting compatible string representation of the factory.
204     * @return script compatible representation for this ElemFactory.
205     * @see edu.jas.structure.Element#toScriptFactory()
206     */
207    @Override
208    public String toScriptFactory() {
209        // Python case
210        return factory().toScript();
211    }
212
213
214    /**
215     * Residue comparison.
216     * @param b Residue.
217     * @return sign(this-b), 0 means that this and b are equivalent in this
218     *         residue class ring.
219     */
220    @Override
221    public int compareTo(Residue<C> b) {
222        C v = b.val;
223        if (!ring.equals(b.ring)) {
224            v = v.remainder(ring.modul);
225        }
226        return val.compareTo(v);
227    }
228
229
230    /**
231     * Comparison with any other object.
232     * @see java.lang.Object#equals(java.lang.Object)
233     * @return true means that this and b are equivalent in this residue class
234     *         ring.
235     */
236    @Override
237    @SuppressWarnings("unchecked")
238    public boolean equals(Object b) {
239        if (b == null) {
240            return false;
241        }
242        if (!(b instanceof Residue)) {
243            return false;
244        }
245        Residue<C> a = (Residue<C>) b;
246        return (0 == compareTo(a));
247    }
248
249
250    /**
251     * Hash code for this local.
252     * @see java.lang.Object#hashCode()
253     */
254    @Override
255    public int hashCode() {
256        int h;
257        h = ring.hashCode();
258        h = 37 * h + val.hashCode();
259        return h;
260    }
261
262
263    /**
264     * Residue absolute value.
265     * @return the absolute value of this.
266     * @see edu.jas.structure.RingElem#abs()
267     */
268    public Residue<C> abs() {
269        return new Residue<C>(ring, val.abs());
270    }
271
272
273    /**
274     * Residue summation.
275     * @param S Residue.
276     * @return this+S.
277     */
278    public Residue<C> sum(Residue<C> S) {
279        return new Residue<C>(ring, val.sum(S.val));
280    }
281
282
283    /**
284     * Residue negate.
285     * @return -this.
286     * @see edu.jas.structure.RingElem#negate()
287     */
288    public Residue<C> negate() {
289        return new Residue<C>(ring, val.negate());
290    }
291
292
293    /**
294     * Residue signum.
295     * @see edu.jas.structure.RingElem#signum()
296     * @return signum(this).
297     */
298    public int signum() {
299        return val.signum();
300    }
301
302
303    /**
304     * Residue subtraction.
305     * @param S Residue.
306     * @return this-S.
307     */
308    public Residue<C> subtract(Residue<C> S) {
309        return new Residue<C>(ring, val.subtract(S.val));
310    }
311
312
313    /**
314     * Residue division.
315     * @param S Residue.
316     * @return this/S.
317     */
318    public Residue<C> divide(Residue<C> S) {
319        return multiply(S.inverse());
320    }
321
322
323    /**
324     * Residue inverse.
325     * @see edu.jas.structure.RingElem#inverse()
326     * @return S with S = 1/this if defined.
327     */
328    @SuppressWarnings("unchecked")
329    public Residue<C> inverse() {
330        if (isunit == 0) {
331            throw new NotInvertibleException("element not invertible (0) " + this);
332        }
333        if (val instanceof GcdRingElem && ring.modul instanceof GcdRingElem) {
334            GcdRingElem v = (GcdRingElem) val;
335            GcdRingElem m = (GcdRingElem) ring.modul;
336            C[] egcd = (C[]) v.egcd(m);
337            //System.out.println("v = " + v + ", m = " + m + ", e[0] = " + egcd[0] + ", e[1] = " + egcd[1]);
338            if (debug) {
339                logger.info("egcd = {}, f = {}", egcd[0], egcd[1]);
340            }
341            if (!egcd[0].isONE()) {
342                isunit = 0;
343                throw new NotInvertibleException("element not invertible (gcd)" + this);
344            }
345            isunit = 1;
346            C x = egcd[1];
347            return new Residue<C>(ring, x);
348        }
349        if (val.isUnit()) {
350            C x = val.inverse();
351            return new Residue<C>(ring, x);
352        }
353        //System.out.println("isunit = " + isunit + ", isUnit() = " + this.isUnit());
354        throw new NotInvertibleException("element not invertible (!gcd)" + this);
355    }
356
357
358    /**
359     * Residue remainder.
360     * @param S Residue.
361     * @return this - (this/S)*S.
362     */
363    public Residue<C> remainder(Residue<C> S) {
364        C x = val.remainder(S.val);
365        return new Residue<C>(ring, x);
366    }
367
368
369    /**
370     * Quotient and remainder by division of this by S.
371     * @param S a Residue
372     * @return [this/S, this - (this/S)*S].
373     */
374    @SuppressWarnings("unchecked")
375    public Residue<C>[] quotientRemainder(Residue<C> S) {
376        return new Residue[] { divide(S), remainder(S) };
377    }
378
379
380    /**
381     * Residue multiplication.
382     * @param S Residue.
383     * @return this*S.
384     */
385    public Residue<C> multiply(Residue<C> S) {
386        return new Residue<C>(ring, val.multiply(S.val));
387    }
388
389
390    /**
391     * Greatest common divisor. <b>Note: </b>Not implemented, throws
392     * UnsupportedOperationException.
393     * @param b other element.
394     * @return gcd(this,b).
395     */
396    public Residue<C> gcd(Residue<C> b) {
397        throw new UnsupportedOperationException("gcd not implemented " + this.getClass().getName());
398    }
399
400
401    /**
402     * Extended greatest common divisor. <b>Note: </b>Not implemented, throws
403     * UnsupportedOperationException.
404     * @param b other element.
405     * @return [ gcd(this,b), c1, c2 ] with c1*this + c2*b = gcd(this,b).
406     */
407    public Residue<C>[] egcd(Residue<C> b) {
408        throw new UnsupportedOperationException("egcd not implemented " + this.getClass().getName());
409    }
410
411}