Source code

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