Source code

001/*
002 * $Id: AlgebraicNumber.java 5997 2020-03-17 15:34:31Z 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     * Is AlgebraicNumber a root of unity.
152     * @return true if |this**i| == 1, for some 0 &lt; i &le; deg(modul), else
153     *         false.
154     */
155    public boolean isRootOfUnity() {
156        long d = ring.modul.degree();
157        AlgebraicNumber<C> t = ring.getONE();
158        for (long i = 1; i <= d; i++) {
159            t = t.multiply(this);
160            if (t.abs().isONE()) {
161                //System.out.println("isRootOfUnity for i = " + i);
162                return true;
163            }
164        }
165        return false;
166    }
167
168
169    /**
170     * Get the String representation as RingElem.
171     * @see java.lang.Object#toString()
172     */
173    @Override
174    public String toString() {
175        if (PrettyPrint.isTrue()) {
176            return val.toString(ring.ring.vars);
177        }
178        return "AlgebraicNumber[ " + val.toString() + " ]";
179    }
180
181
182    /**
183     * Get a scripting compatible string representation.
184     * @return script compatible representation for this Element.
185     * @see edu.jas.structure.Element#toScript()
186     */
187    @Override
188    public String toScript() {
189        // Python case
190        return val.toScript();
191    }
192
193
194    /**
195     * Get a scripting compatible string representation of the factory.
196     * @return script compatible representation for this ElemFactory.
197     * @see edu.jas.structure.Element#toScriptFactory()
198     */
199    @Override
200    public String toScriptFactory() {
201        // Python case
202        return factory().toScript();
203    }
204
205
206    /**
207     * AlgebraicNumber comparison.
208     * @param b AlgebraicNumber.
209     * @return sign(this-b).
210     */
211    @Override
212    public int compareTo(AlgebraicNumber<C> b) {
213        int s = 0;
214        if (ring.modul != b.ring.modul) { // avoid compareTo if possible
215            s = ring.modul.compareTo(b.ring.modul);
216        }
217        if (s != 0) {
218            return s;
219        }
220        return val.compareTo(b.val);
221    }
222
223
224    /**
225     * Comparison with any other object.
226     * @see java.lang.Object#equals(java.lang.Object)
227     */
228    @Override
229    @SuppressWarnings("unchecked")
230    public boolean equals(Object b) {
231        if (b == null) {
232            return false;
233        }
234        if (!(b instanceof AlgebraicNumber)) {
235            return false;
236        }
237        AlgebraicNumber<C> a = (AlgebraicNumber<C>) b;
238        if (!ring.equals(a.ring)) {
239            return false;
240        }
241        return (0 == compareTo(a));
242    }
243
244
245    /**
246     * Hash code for this AlgebraicNumber.
247     * @see java.lang.Object#hashCode()
248     */
249    @Override
250    public int hashCode() {
251        return 37 * val.hashCode() + ring.hashCode();
252    }
253
254
255    /**
256     * AlgebraicNumber absolute value.
257     * @return the absolute value of this.
258     * @see edu.jas.structure.RingElem#abs()
259     */
260    public AlgebraicNumber<C> abs() {
261        return new AlgebraicNumber<C>(ring, val.abs());
262    }
263
264
265    /**
266     * AlgebraicNumber summation.
267     * @param S AlgebraicNumber.
268     * @return this+S.
269     */
270    public AlgebraicNumber<C> sum(AlgebraicNumber<C> S) {
271        return new AlgebraicNumber<C>(ring, val.sum(S.val));
272    }
273
274
275    /**
276     * AlgebraicNumber summation.
277     * @param c coefficient.
278     * @return this+c.
279     */
280    public AlgebraicNumber<C> sum(GenPolynomial<C> c) {
281        return new AlgebraicNumber<C>(ring, val.sum(c));
282    }
283
284
285    /**
286     * AlgebraicNumber summation.
287     * @param c polynomial.
288     * @return this+c.
289     */
290    public AlgebraicNumber<C> sum(C c) {
291        return new AlgebraicNumber<C>(ring, val.sum(c));
292    }
293
294
295    /**
296     * AlgebraicNumber negate.
297     * @return -this.
298     * @see edu.jas.structure.RingElem#negate()
299     */
300    public AlgebraicNumber<C> negate() {
301        return new AlgebraicNumber<C>(ring, val.negate());
302    }
303
304
305    /**
306     * AlgebraicNumber signum.
307     * @see edu.jas.structure.RingElem#signum()
308     * @return signum(this).
309     */
310    public int signum() {
311        return val.signum();
312    }
313
314
315    /**
316     * AlgebraicNumber subtraction.
317     * @param S AlgebraicNumber.
318     * @return this-S.
319     */
320    public AlgebraicNumber<C> subtract(AlgebraicNumber<C> S) {
321        return new AlgebraicNumber<C>(ring, val.subtract(S.val));
322    }
323
324
325    /**
326     * AlgebraicNumber division.
327     * @param S AlgebraicNumber.
328     * @return this/S.
329     */
330    public AlgebraicNumber<C> divide(AlgebraicNumber<C> S) {
331        return multiply(S.inverse());
332    }
333
334
335    /**
336     * AlgebraicNumber inverse.
337     * @see edu.jas.structure.RingElem#inverse()
338     * @throws NotInvertibleException if the element is not invertible.
339     * @return S with S = 1/this if defined.
340     */
341    public AlgebraicNumber<C> inverse() {
342        try {
343            return new AlgebraicNumber<C>(ring, val.modInverse(ring.modul));
344        } catch (AlgebraicNotInvertibleException e) {
345            //System.out.println(e);
346            throw e;
347        } catch (NotInvertibleException e) {
348            throw new AlgebraicNotInvertibleException(e + ", val = " + val + ", modul = " + ring.modul
349                            + ", gcd = " + val.gcd(ring.modul), e);
350        }
351    }
352
353
354    /**
355     * AlgebraicNumber remainder.
356     * @param S AlgebraicNumber.
357     * @return this - (this/S)*S.
358     */
359    public AlgebraicNumber<C> remainder(AlgebraicNumber<C> S) {
360        if (S == null || S.isZERO()) {
361            throw new ArithmeticException("division by zero");
362        }
363        if (S.isONE()) {
364            return ring.getZERO();
365        }
366        if (S.isUnit()) {
367            return ring.getZERO();
368        }
369        GenPolynomial<C> x = val.remainder(S.val);
370        return new AlgebraicNumber<C>(ring, x);
371    }
372
373
374    /**
375     * Quotient and remainder by division of this by S.
376     * @param S a AlgebraicNumber
377     * @return [this/S, this - (this/S)*S].
378     */
379    @SuppressWarnings("unchecked")
380    public AlgebraicNumber<C>[] quotientRemainder(AlgebraicNumber<C> S) {
381        return new AlgebraicNumber[] { divide(S), remainder(S) };
382    }
383
384
385    /**
386     * AlgebraicNumber multiplication.
387     * @param S AlgebraicNumber.
388     * @return this*S.
389     */
390    public AlgebraicNumber<C> multiply(AlgebraicNumber<C> S) {
391        GenPolynomial<C> x = val.multiply(S.val);
392        return new AlgebraicNumber<C>(ring, x);
393    }
394
395
396    /**
397     * AlgebraicNumber multiplication.
398     * @param c coefficient.
399     * @return this*c.
400     */
401    public AlgebraicNumber<C> multiply(C c) {
402        GenPolynomial<C> x = val.multiply(c);
403        return new AlgebraicNumber<C>(ring, x);
404    }
405
406
407    /**
408     * AlgebraicNumber multiplication.
409     * @param c polynomial.
410     * @return this*c.
411     */
412    public AlgebraicNumber<C> multiply(GenPolynomial<C> c) {
413        GenPolynomial<C> x = val.multiply(c);
414        return new AlgebraicNumber<C>(ring, x);
415    }
416
417
418    /**
419     * AlgebraicNumber monic.
420     * @return this with monic value part.
421     */
422    public AlgebraicNumber<C> monic() {
423        return new AlgebraicNumber<C>(ring, val.monic());
424    }
425
426
427    /**
428     * AlgebraicNumber greatest common divisor.
429     * @param S AlgebraicNumber.
430     * @return gcd(this,S).
431     */
432    public AlgebraicNumber<C> gcd(AlgebraicNumber<C> S) {
433        if (S.isZERO()) {
434            return this;
435        }
436        if (isZERO()) {
437            return S;
438        }
439        if (isUnit() || S.isUnit()) {
440            return ring.getONE();
441        }
442        return new AlgebraicNumber<C>(ring, val.gcd(S.val));
443    }
444
445
446    /**
447     * AlgebraicNumber extended greatest common divisor.
448     * @param S AlgebraicNumber.
449     * @return [ gcd(this,S), a, b ] with a*this + b*S = gcd(this,S).
450     */
451    @SuppressWarnings("unchecked")
452    public AlgebraicNumber<C>[] egcd(AlgebraicNumber<C> S) {
453        AlgebraicNumber<C>[] ret = new AlgebraicNumber[3];
454        ret[0] = null;
455        ret[1] = null;
456        ret[2] = null;
457        if (S == null || S.isZERO()) {
458            ret[0] = this;
459            return ret;
460        }
461        if (isZERO()) {
462            ret[0] = S;
463            return ret;
464        }
465        if (this.isUnit() || S.isUnit()) {
466            ret[0] = ring.getONE();
467            if (this.isUnit() && S.isUnit()) {
468                AlgebraicNumber<C> half = ring.fromInteger(2).inverse();
469                ret[1] = this.inverse().multiply(half);
470                ret[2] = S.inverse().multiply(half);
471                return ret;
472            }
473            if (this.isUnit()) {
474                // oder inverse(S-1)?
475                ret[1] = this.inverse();
476                ret[2] = ring.getZERO();
477                return ret;
478            }
479            // if ( S.isUnit() ) {
480            // oder inverse(this-1)?
481            ret[1] = ring.getZERO();
482            ret[2] = S.inverse();
483            return ret;
484            //}
485        }
486        //System.out.println("this = " + this + ", S = " + S);
487        GenPolynomial<C>[] qr;
488        GenPolynomial<C> q = this.val;
489        GenPolynomial<C> r = S.val;
490        GenPolynomial<C> c1 = ring.ring.getONE();
491        GenPolynomial<C> d1 = ring.ring.getZERO();
492        GenPolynomial<C> c2 = ring.ring.getZERO();
493        GenPolynomial<C> d2 = ring.ring.getONE();
494        GenPolynomial<C> x1;
495        GenPolynomial<C> x2;
496        while (!r.isZERO()) {
497            qr = q.quotientRemainder(r);
498            q = qr[0];
499            x1 = c1.subtract(q.multiply(d1));
500            x2 = c2.subtract(q.multiply(d2));
501            c1 = d1;
502            c2 = d2;
503            d1 = x1;
504            d2 = x2;
505            q = r;
506            r = qr[1];
507        }
508        //System.out.println("q = " + q + "\n c1 = " + c1 + "\n c2 = " + c2);
509        ret[0] = new AlgebraicNumber<C>(ring, q);
510        ret[1] = new AlgebraicNumber<C>(ring, c1);
511        ret[2] = new AlgebraicNumber<C>(ring, c2);
512        return ret;
513    }
514
515}