Source code

001/*
002 * $Id: AlgebraicNumber.java 4148 2012-08-31 19:49:27Z kredel $
003 */
004
005package edu.jas.poly;
006
007
008import edu.jas.kern.PrettyPrint;
009import edu.jas.structure.RingElem;
010import edu.jas.structure.GcdRingElem;
011import edu.jas.structure.NotInvertibleException;
012
013
014/**
015 * Algebraic number class based on GenPolynomial with RingElem interface.
016 * Objects of this class are immutable.
017 * @author Heinz Kredel
018 */
019
020public class AlgebraicNumber<C extends RingElem<C>> implements GcdRingElem<AlgebraicNumber<C>> {
021
022
023    /**
024     * Ring part of the data structure.
025     */
026    public final AlgebraicNumberRing<C> ring;
027
028
029    /**
030     * Value part of the element data structure.
031     */
032    public final GenPolynomial<C> val;
033
034
035    /**
036     * Flag to remember if this algebraic number is a unit. -1 is unknown, 1 is
037     * unit, 0 not a unit.
038     */
039    protected int isunit = -1; // initially unknown
040
041
042    /**
043     * The constructor creates a AlgebraicNumber object from AlgebraicNumberRing
044     * modul and a GenPolynomial value.
045     * @param r ring AlgebraicNumberRing<C>.
046     * @param a value GenPolynomial<C>.
047     */
048    public AlgebraicNumber(AlgebraicNumberRing<C> r, GenPolynomial<C> a) {
049        ring = r; // assert r != 0
050        val = a.remainder(ring.modul); //.monic() no go
051        if (val.isZERO()) {
052            isunit = 0;
053        }
054        if (ring.isField()) {
055            isunit = 1;
056        }
057    }
058
059
060    /**
061     * The constructor creates a AlgebraicNumber object from a GenPolynomial
062     * object module.
063     * @param r ring AlgebraicNumberRing<C>.
064     */
065    public AlgebraicNumber(AlgebraicNumberRing<C> r) {
066        this(r, r.ring.getZERO());
067    }
068
069
070    /**
071     * Get the value part.
072     * @return val.
073     */
074    public GenPolynomial<C> getVal() {
075        return val;
076    }
077
078
079    /**
080     * Get the corresponding element factory.
081     * @return factory for this Element.
082     * @see edu.jas.structure.Element#factory()
083     */
084    public AlgebraicNumberRing<C> factory() {
085        return ring;
086    }
087
088
089    /**
090     * Clone this.
091     * @see java.lang.Object#clone()
092     */
093    @Override
094    public AlgebraicNumber<C> copy() {
095        return new AlgebraicNumber<C>(ring, val);
096    }
097
098
099    /**
100     * Is AlgebraicNumber zero.
101     * @return If this is 0 then true is returned, else false.
102     * @see edu.jas.structure.RingElem#isZERO()
103     */
104    public boolean isZERO() {
105        return val.equals(ring.ring.getZERO());
106    }
107
108
109    /**
110     * Is AlgebraicNumber one.
111     * @return If this is 1 then true is returned, else false.
112     * @see edu.jas.structure.RingElem#isONE()
113     */
114    public boolean isONE() {
115        return val.equals(ring.ring.getONE());
116    }
117
118
119    /**
120     * Is AlgebraicNumber unit.
121     * @return If this is a unit then true is returned, else false.
122     * @see edu.jas.structure.RingElem#isUnit()
123     */
124    public boolean isUnit() {
125        if (isunit > 0) {
126            return true;
127        }
128        if (isunit == 0) {
129            return false;
130        }
131        // not jet known
132        if (val.isZERO()) {
133            isunit = 0;
134            return false;
135        }
136        if (ring.isField()) {
137            isunit = 1;
138            return true;
139        }
140        boolean u = val.gcd(ring.modul).isUnit();
141        if (u) {
142            isunit = 1;
143        } else {
144            isunit = 0;
145        }
146        return (u);
147    }
148
149
150    /**
151     * Get the String representation as RingElem.
152     * @see java.lang.Object#toString()
153     */
154    @Override
155    public String toString() {
156        if (PrettyPrint.isTrue()) {
157            return val.toString(ring.ring.vars);
158        }
159        return "AlgebraicNumber[ " + val.toString() + " ]";
160    }
161
162
163    /**
164     * Get a scripting compatible string representation.
165     * @return script compatible representation for this Element.
166     * @see edu.jas.structure.Element#toScript()
167     */
168    //JAVA6only: @Override
169    public String toScript() {
170        // Python case
171        return val.toScript();
172    }
173
174
175    /**
176     * Get a scripting compatible string representation of the factory.
177     * @return script compatible representation for this ElemFactory.
178     * @see edu.jas.structure.Element#toScriptFactory()
179     */
180    //JAVA6only: @Override
181    public String toScriptFactory() {
182        // Python case
183        return factory().toScript();
184    }
185
186
187    /**
188     * AlgebraicNumber comparison.
189     * @param b AlgebraicNumber.
190     * @return sign(this-b).
191     */
192    //JAVA6only: @Override
193    public int compareTo(AlgebraicNumber<C> b) {
194        int s = 0;
195        if (ring.modul != b.ring.modul) { // avoid compareTo if possible
196            s = ring.modul.compareTo(b.ring.modul);
197        }
198        if (s != 0) {
199            return s;
200        }
201        return val.compareTo(b.val);
202    }
203
204
205    /**
206     * Comparison with any other object.
207     * @see java.lang.Object#equals(java.lang.Object)
208     */
209    @Override
210    @SuppressWarnings("unchecked")
211    // not jet working
212    public boolean equals(Object b) {
213        if (!(b instanceof AlgebraicNumber)) {
214            return false;
215        }
216        AlgebraicNumber<C> a = null;
217        try {
218            a = (AlgebraicNumber<C>) b;
219        } catch (ClassCastException e) {
220        }
221        if (a == null) {
222            return false;
223        }
224        if (!ring.equals(a.ring)) {
225            return false;
226        }
227        return (0 == compareTo(a));
228    }
229
230
231    /**
232     * Hash code for this AlgebraicNumber.
233     * @see java.lang.Object#hashCode()
234     */
235    @Override
236    public int hashCode() {
237        return 37 * val.hashCode() + ring.hashCode();
238    }
239
240
241    /**
242     * AlgebraicNumber absolute value.
243     * @return the absolute value of this.
244     * @see edu.jas.structure.RingElem#abs()
245     */
246    public AlgebraicNumber<C> abs() {
247        return new AlgebraicNumber<C>(ring, val.abs());
248    }
249
250
251    /**
252     * AlgebraicNumber summation.
253     * @param S AlgebraicNumber.
254     * @return this+S.
255     */
256    public AlgebraicNumber<C> sum(AlgebraicNumber<C> S) {
257        return new AlgebraicNumber<C>(ring, val.sum(S.val));
258    }
259
260
261    /**
262     * AlgebraicNumber summation.
263     * @param c coefficient.
264     * @return this+c.
265     */
266    public AlgebraicNumber<C> sum(GenPolynomial<C> c) {
267        return new AlgebraicNumber<C>(ring, val.sum(c));
268    }
269
270
271    /**
272     * AlgebraicNumber summation.
273     * @param c polynomial.
274     * @return this+c.
275     */
276    public AlgebraicNumber<C> sum(C c) {
277        return new AlgebraicNumber<C>(ring, val.sum(c));
278    }
279
280
281    /**
282     * AlgebraicNumber negate.
283     * @return -this.
284     * @see edu.jas.structure.RingElem#negate()
285     */
286    public AlgebraicNumber<C> negate() {
287        return new AlgebraicNumber<C>(ring, val.negate());
288    }
289
290
291    /**
292     * AlgebraicNumber signum.
293     * @see edu.jas.structure.RingElem#signum()
294     * @return signum(this).
295     */
296    public int signum() {
297        return val.signum();
298    }
299
300
301    /**
302     * AlgebraicNumber subtraction.
303     * @param S AlgebraicNumber.
304     * @return this-S.
305     */
306    public AlgebraicNumber<C> subtract(AlgebraicNumber<C> S) {
307        return new AlgebraicNumber<C>(ring, val.subtract(S.val));
308    }
309
310
311    /**
312     * AlgebraicNumber division.
313     * @param S AlgebraicNumber.
314     * @return this/S.
315     */
316    public AlgebraicNumber<C> divide(AlgebraicNumber<C> S) {
317        return multiply(S.inverse());
318    }
319
320
321    /**
322     * AlgebraicNumber inverse.
323     * @see edu.jas.structure.RingElem#inverse()
324     * @throws NotInvertibleException if the element is not invertible.
325     * @return S with S = 1/this if defined.
326     */
327    public AlgebraicNumber<C> inverse() {
328        try {
329            return new AlgebraicNumber<C>(ring, val.modInverse(ring.modul));
330        } catch (AlgebraicNotInvertibleException e) {
331            //System.out.println(e);
332            throw e;
333        } catch (NotInvertibleException e) {
334            throw new AlgebraicNotInvertibleException(e + ", val = " + val + ", modul = " + ring.modul + ", gcd = "
335                                                      + val.gcd(ring.modul),e);
336        }
337    }
338
339
340    /**
341     * AlgebraicNumber remainder.
342     * @param S AlgebraicNumber.
343     * @return this - (this/S)*S.
344     */
345    public AlgebraicNumber<C> remainder(AlgebraicNumber<C> S) {
346        if (S == null || S.isZERO()) {
347            throw new ArithmeticException("division by zero");
348        }
349        if (S.isONE()) {
350            return ring.getZERO();
351        }
352        if (S.isUnit()) {
353            return ring.getZERO();
354        }
355        GenPolynomial<C> x = val.remainder(S.val);
356        return new AlgebraicNumber<C>(ring, x);
357    }
358
359
360    /**
361     * AlgebraicNumber multiplication.
362     * @param S AlgebraicNumber.
363     * @return this*S.
364     */
365    public AlgebraicNumber<C> multiply(AlgebraicNumber<C> S) {
366        GenPolynomial<C> x = val.multiply(S.val);
367        return new AlgebraicNumber<C>(ring, x);
368    }
369
370
371    /**
372     * AlgebraicNumber multiplication.
373     * @param c coefficient.
374     * @return this*c.
375     */
376    public AlgebraicNumber<C> multiply(C c) {
377        GenPolynomial<C> x = val.multiply(c);
378        return new AlgebraicNumber<C>(ring, x);
379    }
380
381
382    /**
383     * AlgebraicNumber multiplication.
384     * @param c polynomial.
385     * @return this*c.
386     */
387    public AlgebraicNumber<C> multiply(GenPolynomial<C> c) {
388        GenPolynomial<C> x = val.multiply(c);
389        return new AlgebraicNumber<C>(ring, x);
390    }
391
392
393    /**
394     * AlgebraicNumber monic.
395     * @return this with monic value part.
396     */
397    public AlgebraicNumber<C> monic() {
398        return new AlgebraicNumber<C>(ring, val.monic());
399    }
400
401
402    /**
403     * AlgebraicNumber greatest common divisor.
404     * @param S AlgebraicNumber.
405     * @return gcd(this,S).
406     */
407    public AlgebraicNumber<C> gcd(AlgebraicNumber<C> S) {
408        if (S.isZERO()) {
409            return this;
410        }
411        if (isZERO()) {
412            return S;
413        }
414        if (isUnit() || S.isUnit()) {
415            return ring.getONE();
416        }
417        return new AlgebraicNumber<C>(ring, val.gcd(S.val));
418    }
419
420
421    /**
422     * AlgebraicNumber extended greatest common divisor.
423     * @param S AlgebraicNumber.
424     * @return [ gcd(this,S), a, b ] with a*this + b*S = gcd(this,S).
425     */
426    @SuppressWarnings("unchecked")
427    public AlgebraicNumber<C>[] egcd(AlgebraicNumber<C> S) {
428        AlgebraicNumber<C>[] ret = new AlgebraicNumber[3];
429        ret[0] = null;
430        ret[1] = null;
431        ret[2] = null;
432        if (S == null || S.isZERO()) {
433            ret[0] = this;
434            return ret;
435        }
436        if (isZERO()) {
437            ret[0] = S;
438            return ret;
439        }
440        if (this.isUnit() || S.isUnit()) {
441            ret[0] = ring.getONE();
442            if (this.isUnit() && S.isUnit()) {
443                AlgebraicNumber<C> half = ring.fromInteger(2).inverse();
444                ret[1] = this.inverse().multiply(half);
445                ret[2] = S.inverse().multiply(half);
446                return ret;
447            }
448            if (this.isUnit()) {
449                // oder inverse(S-1)?
450                ret[1] = this.inverse();
451                ret[2] = ring.getZERO();
452                return ret;
453            }
454            // if ( S.isUnit() ) {
455            // oder inverse(this-1)?
456            ret[1] = ring.getZERO();
457            ret[2] = S.inverse();
458            return ret;
459            //}
460        }
461        //System.out.println("this = " + this + ", S = " + S);
462        GenPolynomial<C>[] qr;
463        GenPolynomial<C> q = this.val;
464        GenPolynomial<C> r = S.val;
465        GenPolynomial<C> c1 = ring.ring.getONE();
466        GenPolynomial<C> d1 = ring.ring.getZERO();
467        GenPolynomial<C> c2 = ring.ring.getZERO();
468        GenPolynomial<C> d2 = ring.ring.getONE();
469        GenPolynomial<C> x1;
470        GenPolynomial<C> x2;
471        while (!r.isZERO()) {
472            qr = q.quotientRemainder(r);
473            q = qr[0];
474            x1 = c1.subtract(q.multiply(d1));
475            x2 = c2.subtract(q.multiply(d2));
476            c1 = d1;
477            c2 = d2;
478            d1 = x1;
479            d2 = x2;
480            q = r;
481            r = qr[1];
482        }
483        //System.out.println("q = " + q + "\n c1 = " + c1 + "\n c2 = " + c2);
484        ret[0] = new AlgebraicNumber<C>(ring, q);
485        ret[1] = new AlgebraicNumber<C>(ring, c1);
486        ret[2] = new AlgebraicNumber<C>(ring, c2);
487        return ret;
488    }
489
490}