Source code

001/*
002 * $Id: AlgebraicNumber.java 5340 2015-12-06 15:00:18Z kredel $
003 */
004
005package edu.jas.poly;
006
007
008import edu.jas.kern.PrettyPrint;
009import edu.jas.structure.GcdRingElem;
010import edu.jas.structure.NotInvertibleException;
011import edu.jas.structure.RingElem;
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     * Copy this.
091     * @see edu.jas.structure.Element#copy()
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    @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    @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    @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    public boolean equals(Object b) {
212        if (b == null) {
213            return false;
214        }
215        if (!(b instanceof AlgebraicNumber)) {
216            return false;
217        }
218        AlgebraicNumber<C> a = (AlgebraicNumber<C>) b;
219        if (!ring.equals(a.ring)) {
220            return false;
221        }
222        return (0 == compareTo(a));
223    }
224
225
226    /**
227     * Hash code for this AlgebraicNumber.
228     * @see java.lang.Object#hashCode()
229     */
230    @Override
231    public int hashCode() {
232        return 37 * val.hashCode() + ring.hashCode();
233    }
234
235
236    /**
237     * AlgebraicNumber absolute value.
238     * @return the absolute value of this.
239     * @see edu.jas.structure.RingElem#abs()
240     */
241    public AlgebraicNumber<C> abs() {
242        return new AlgebraicNumber<C>(ring, val.abs());
243    }
244
245
246    /**
247     * AlgebraicNumber summation.
248     * @param S AlgebraicNumber.
249     * @return this+S.
250     */
251    public AlgebraicNumber<C> sum(AlgebraicNumber<C> S) {
252        return new AlgebraicNumber<C>(ring, val.sum(S.val));
253    }
254
255
256    /**
257     * AlgebraicNumber summation.
258     * @param c coefficient.
259     * @return this+c.
260     */
261    public AlgebraicNumber<C> sum(GenPolynomial<C> c) {
262        return new AlgebraicNumber<C>(ring, val.sum(c));
263    }
264
265
266    /**
267     * AlgebraicNumber summation.
268     * @param c polynomial.
269     * @return this+c.
270     */
271    public AlgebraicNumber<C> sum(C c) {
272        return new AlgebraicNumber<C>(ring, val.sum(c));
273    }
274
275
276    /**
277     * AlgebraicNumber negate.
278     * @return -this.
279     * @see edu.jas.structure.RingElem#negate()
280     */
281    public AlgebraicNumber<C> negate() {
282        return new AlgebraicNumber<C>(ring, val.negate());
283    }
284
285
286    /**
287     * AlgebraicNumber signum.
288     * @see edu.jas.structure.RingElem#signum()
289     * @return signum(this).
290     */
291    public int signum() {
292        return val.signum();
293    }
294
295
296    /**
297     * AlgebraicNumber subtraction.
298     * @param S AlgebraicNumber.
299     * @return this-S.
300     */
301    public AlgebraicNumber<C> subtract(AlgebraicNumber<C> S) {
302        return new AlgebraicNumber<C>(ring, val.subtract(S.val));
303    }
304
305
306    /**
307     * AlgebraicNumber division.
308     * @param S AlgebraicNumber.
309     * @return this/S.
310     */
311    public AlgebraicNumber<C> divide(AlgebraicNumber<C> S) {
312        return multiply(S.inverse());
313    }
314
315
316    /**
317     * AlgebraicNumber inverse.
318     * @see edu.jas.structure.RingElem#inverse()
319     * @throws NotInvertibleException if the element is not invertible.
320     * @return S with S = 1/this if defined.
321     */
322    public AlgebraicNumber<C> inverse() {
323        try {
324            return new AlgebraicNumber<C>(ring, val.modInverse(ring.modul));
325        } catch (AlgebraicNotInvertibleException e) {
326            //System.out.println(e);
327            throw e;
328        } catch (NotInvertibleException e) {
329            throw new AlgebraicNotInvertibleException(e + ", val = " + val + ", modul = " + ring.modul
330                            + ", gcd = " + val.gcd(ring.modul), e);
331        }
332    }
333
334
335    /**
336     * AlgebraicNumber remainder.
337     * @param S AlgebraicNumber.
338     * @return this - (this/S)*S.
339     */
340    public AlgebraicNumber<C> remainder(AlgebraicNumber<C> S) {
341        if (S == null || S.isZERO()) {
342            throw new ArithmeticException("division by zero");
343        }
344        if (S.isONE()) {
345            return ring.getZERO();
346        }
347        if (S.isUnit()) {
348            return ring.getZERO();
349        }
350        GenPolynomial<C> x = val.remainder(S.val);
351        return new AlgebraicNumber<C>(ring, x);
352    }
353
354
355    /**
356     * Quotient and remainder by division of this by S.
357     * @param S a AlgebraicNumber
358     * @return [this/S, this - (this/S)*S].
359     */
360    public AlgebraicNumber<C>[] quotientRemainder(AlgebraicNumber<C> S) {
361        return new AlgebraicNumber[] { divide(S), remainder(S) };
362    }
363
364
365    /**
366     * AlgebraicNumber multiplication.
367     * @param S AlgebraicNumber.
368     * @return this*S.
369     */
370    public AlgebraicNumber<C> multiply(AlgebraicNumber<C> S) {
371        GenPolynomial<C> x = val.multiply(S.val);
372        return new AlgebraicNumber<C>(ring, x);
373    }
374
375
376    /**
377     * AlgebraicNumber multiplication.
378     * @param c coefficient.
379     * @return this*c.
380     */
381    public AlgebraicNumber<C> multiply(C c) {
382        GenPolynomial<C> x = val.multiply(c);
383        return new AlgebraicNumber<C>(ring, x);
384    }
385
386
387    /**
388     * AlgebraicNumber multiplication.
389     * @param c polynomial.
390     * @return this*c.
391     */
392    public AlgebraicNumber<C> multiply(GenPolynomial<C> c) {
393        GenPolynomial<C> x = val.multiply(c);
394        return new AlgebraicNumber<C>(ring, x);
395    }
396
397
398    /**
399     * AlgebraicNumber monic.
400     * @return this with monic value part.
401     */
402    public AlgebraicNumber<C> monic() {
403        return new AlgebraicNumber<C>(ring, val.monic());
404    }
405
406
407    /**
408     * AlgebraicNumber greatest common divisor.
409     * @param S AlgebraicNumber.
410     * @return gcd(this,S).
411     */
412    public AlgebraicNumber<C> gcd(AlgebraicNumber<C> S) {
413        if (S.isZERO()) {
414            return this;
415        }
416        if (isZERO()) {
417            return S;
418        }
419        if (isUnit() || S.isUnit()) {
420            return ring.getONE();
421        }
422        return new AlgebraicNumber<C>(ring, val.gcd(S.val));
423    }
424
425
426    /**
427     * AlgebraicNumber extended greatest common divisor.
428     * @param S AlgebraicNumber.
429     * @return [ gcd(this,S), a, b ] with a*this + b*S = gcd(this,S).
430     */
431    @SuppressWarnings("unchecked")
432    public AlgebraicNumber<C>[] egcd(AlgebraicNumber<C> S) {
433        AlgebraicNumber<C>[] ret = new AlgebraicNumber[3];
434        ret[0] = null;
435        ret[1] = null;
436        ret[2] = null;
437        if (S == null || S.isZERO()) {
438            ret[0] = this;
439            return ret;
440        }
441        if (isZERO()) {
442            ret[0] = S;
443            return ret;
444        }
445        if (this.isUnit() || S.isUnit()) {
446            ret[0] = ring.getONE();
447            if (this.isUnit() && S.isUnit()) {
448                AlgebraicNumber<C> half = ring.fromInteger(2).inverse();
449                ret[1] = this.inverse().multiply(half);
450                ret[2] = S.inverse().multiply(half);
451                return ret;
452            }
453            if (this.isUnit()) {
454                // oder inverse(S-1)?
455                ret[1] = this.inverse();
456                ret[2] = ring.getZERO();
457                return ret;
458            }
459            // if ( S.isUnit() ) {
460            // oder inverse(this-1)?
461            ret[1] = ring.getZERO();
462            ret[2] = S.inverse();
463            return ret;
464            //}
465        }
466        //System.out.println("this = " + this + ", S = " + S);
467        GenPolynomial<C>[] qr;
468        GenPolynomial<C> q = this.val;
469        GenPolynomial<C> r = S.val;
470        GenPolynomial<C> c1 = ring.ring.getONE();
471        GenPolynomial<C> d1 = ring.ring.getZERO();
472        GenPolynomial<C> c2 = ring.ring.getZERO();
473        GenPolynomial<C> d2 = ring.ring.getONE();
474        GenPolynomial<C> x1;
475        GenPolynomial<C> x2;
476        while (!r.isZERO()) {
477            qr = q.quotientRemainder(r);
478            q = qr[0];
479            x1 = c1.subtract(q.multiply(d1));
480            x2 = c2.subtract(q.multiply(d2));
481            c1 = d1;
482            c2 = d2;
483            d1 = x1;
484            d2 = x2;
485            q = r;
486            r = qr[1];
487        }
488        //System.out.println("q = " + q + "\n c1 = " + c1 + "\n c2 = " + c2);
489        ret[0] = new AlgebraicNumber<C>(ring, q);
490        ret[1] = new AlgebraicNumber<C>(ring, c1);
491        ret[2] = new AlgebraicNumber<C>(ring, c2);
492        return ret;
493    }
494
495}