Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.poly;
006
007
008import java.io.Reader;
009import java.util.ArrayList;
010import java.util.Iterator;
011import java.util.List;
012import java.util.Random;
013
014import org.apache.logging.log4j.LogManager;
015import org.apache.logging.log4j.Logger;
016
017import edu.jas.kern.Scripting;
018import edu.jas.structure.RingElem;
019import edu.jas.structure.RingFactory;
020import edu.jas.util.CartesianProduct;
021import edu.jas.util.CartesianProductInfinite;
022
023
024/**
025 * Algebraic number factory. Based on GenPolynomial factory with RingElem
026 * interface. Objects of this class are immutable.
027 * @author Heinz Kredel
028 */
029
030public class AlgebraicNumberRing<C extends RingElem<C>>
031                implements RingFactory<AlgebraicNumber<C>>, Iterable<AlgebraicNumber<C>> {
032
033
034    /**
035     * Ring part of the factory data structure.
036     */
037    public final GenPolynomialRing<C> ring;
038
039
040    /**
041     * Module part of the factory data structure.
042     */
043    public final GenPolynomial<C> modul;
044
045
046    /**
047     * Indicator if this ring is a field
048     */
049    protected int isField = -1; // initially unknown
050
051
052    private static final Logger logger = LogManager.getLogger(AlgebraicNumberRing.class);
053
054
055    //  private static final boolean debug = logger.isDebugEnabled();
056
057
058    /**
059     * The constructor creates a AlgebraicNumber factory object from a
060     * GenPolynomial objects module.
061     * @param m module GenPolynomial<C>.
062     */
063    public AlgebraicNumberRing(GenPolynomial<C> m) {
064        ring = m.ring;
065        modul = m; // assert m != 0
066        if (ring.nvar > 1) {
067            throw new IllegalArgumentException("only univariate polynomials allowed");
068        }
069    }
070
071
072    /**
073     * The constructor creates a AlgebraicNumber factory object from a
074     * GenPolynomial objects module.
075     * @param m module GenPolynomial<C>.
076     * @param isField indicator if m is prime.
077     */
078    public AlgebraicNumberRing(GenPolynomial<C> m, boolean isField) {
079        ring = m.ring;
080        modul = m; // assert m != 0
081        this.isField = (isField ? 1 : 0);
082        if (ring.nvar > 1) {
083            throw new IllegalArgumentException("only univariate polynomials allowed");
084        }
085    }
086
087
088    /**
089     * Get the module part.
090     * @return modul.
091     */
092    public GenPolynomial<C> getModul() {
093        return modul;
094    }
095
096
097    /**
098     * Copy AlgebraicNumber element c.
099     * @param c algebraic number to copy.
100     * @return a copy of c.
101     */
102    public AlgebraicNumber<C> copy(AlgebraicNumber<C> c) {
103        return new AlgebraicNumber<C>(this, c.val);
104    }
105
106
107    /**
108     * Get the zero element.
109     * @return 0 as AlgebraicNumber.
110     */
111    public AlgebraicNumber<C> getZERO() {
112        return new AlgebraicNumber<C>(this, ring.getZERO());
113    }
114
115
116    /**
117     * Get the one element.
118     * @return 1 as AlgebraicNumber.
119     */
120    public AlgebraicNumber<C> getONE() {
121        return new AlgebraicNumber<C>(this, ring.getONE());
122    }
123
124
125    /**
126     * Get the generating element.
127     * @return alpha as AlgebraicNumber.
128     */
129    public AlgebraicNumber<C> getGenerator() {
130        return new AlgebraicNumber<C>(this, ring.univariate(0));
131    }
132
133
134    /**
135     * Get a list of the generating elements.
136     * @return list of generators for the algebraic structure.
137     * @see edu.jas.structure.ElemFactory#generators()
138     */
139    public List<AlgebraicNumber<C>> generators() {
140        List<GenPolynomial<C>> gc = ring.generators();
141        List<AlgebraicNumber<C>> gens = new ArrayList<AlgebraicNumber<C>>(gc.size());
142        for (GenPolynomial<C> g : gc) {
143            gens.add(new AlgebraicNumber<C>(this, g));
144        }
145        return gens;
146    }
147
148
149    /**
150     * Is this structure finite or infinite.
151     * @return true if this structure is finite, else false.
152     * @see edu.jas.structure.ElemFactory#isFinite()
153     */
154    public boolean isFinite() {
155        return ring.coFac.isFinite();
156    }
157
158
159    /**
160     * Query if this ring is commutative.
161     * @return true if this ring is commutative, else false.
162     */
163    public boolean isCommutative() {
164        return ring.isCommutative();
165    }
166
167
168    /**
169     * Query if this ring is associative.
170     * @return true if this ring is associative, else false.
171     */
172    public boolean isAssociative() {
173        return ring.isAssociative();
174    }
175
176
177    /**
178     * Query if this ring is a field.
179     * @return true if modul is prime, else false.
180     */
181    public boolean isField() {
182        if (isField > 0) {
183            return true;
184        }
185        if (isField == 0) {
186            return false;
187        }
188        if (!ring.coFac.isField()) {
189            isField = 0;
190            return false;
191        }
192        return false;
193    }
194
195
196    /**
197     * Set field property of this ring.
198     * @param field true, if this ring is determined to be a field, false, if it
199     *            is determined that it is not a field.
200     */
201    public void setField(boolean field) {
202        if (isField > 0 && field) {
203            return;
204        }
205        if (isField == 0 && !field) {
206            return;
207        }
208        if (field) {
209            isField = 1;
210        } else {
211            isField = 0;
212        }
213        return;
214    }
215
216
217    /**
218     * Get the internal field indicator.
219     * @return internal field indicator.
220     */
221    public int getField() {
222        return isField;
223    }
224
225
226    /**
227     * Characteristic of this ring.
228     * @return characteristic of this ring.
229     */
230    public java.math.BigInteger characteristic() {
231        return ring.characteristic();
232    }
233
234
235    /**
236     * Get an AlgebraicNumber element from a BigInteger value.
237     * If a = a_k p^k + ... + a_0 p^0 then b = a_k x^k + ... + a_0 x^0,
238     * where p = characteristic( this ).
239     * @param a BigInteger.
240     * @return b an AlgebraicNumber.
241     */
242    public AlgebraicNumber<C> fillFromInteger(java.math.BigInteger a) {
243        if (characteristic().signum() == 0) {
244            return new AlgebraicNumber<C>(this, ring.fromInteger(a));
245        }
246        java.math.BigInteger p = characteristic();
247        java.math.BigInteger b = a;
248        GenPolynomial<C> v = ring.getZERO();
249        GenPolynomial<C> x = ring.univariate(0, 1L);
250        GenPolynomial<C> t = ring.getONE();
251        do {
252            java.math.BigInteger[] qr = b.divideAndRemainder(p);
253            java.math.BigInteger q = qr[0];
254            java.math.BigInteger r = qr[1];
255            //System.out.println("q = " + q + ", r = " +r);
256            GenPolynomial<C> rp = ring.fromInteger(r);
257            v = v.sum(t.multiply(rp));
258            t = t.multiply(x);
259            b = q;
260        } while (!b.equals(java.math.BigInteger.ZERO));
261        AlgebraicNumber<C> an = new AlgebraicNumber<C>(this, v);
262        logger.info("fill({}) = {}, mod: {}", a, v, an);
263        //RuntimeException e = new RuntimeException("hihihi");
264        //e.printStackTrace();
265        return an;
266    }
267
268
269    /**
270     * Get a AlgebraicNumber element from a long value.
271     * @param a long.
272     * @return a AlgebraicNumber.
273     */
274    public AlgebraicNumber<C> fillFromInteger(long a) {
275        return fillFromInteger(new java.math.BigInteger("" + a));
276    }
277
278
279    /**
280     * Get a AlgebraicNumber element from a BigInteger value.
281     * @param a BigInteger.
282     * @return a AlgebraicNumber.
283     */
284    public AlgebraicNumber<C> fromInteger(java.math.BigInteger a) {
285        return new AlgebraicNumber<C>(this, ring.fromInteger(a));
286    }
287
288
289    /**
290     * Get a AlgebraicNumber element from a long value.
291     * @param a long.
292     * @return a AlgebraicNumber.
293     */
294    public AlgebraicNumber<C> fromInteger(long a) {
295        return new AlgebraicNumber<C>(this, ring.fromInteger(a));
296        //         if ( characteristic().signum() == 0 ) {
297        //         }
298        //         return fromInteger( new java.math.BigInteger(""+a) );
299    }
300
301
302    /**
303     * Get the String representation as RingFactory.
304     * @see java.lang.Object#toString()
305     */
306    @Override
307    public String toString() {
308        return "AlgebraicNumberRing[ " + modul.toString() + " | isField=" + isField + " :: " + ring.toString()
309                        + " ]";
310    }
311
312
313    /**
314     * Get a scripting compatible string representation.
315     * @return script compatible representation for this ElemFactory.
316     * @see edu.jas.structure.ElemFactory#toScript()
317     */
318    @Override
319    public String toScript() {
320        StringBuffer s = new StringBuffer();
321        s.append("AN(");
322        s.append(modul.toScript());
323        switch (Scripting.getLang()) {
324        case Ruby:
325            s.append((isField() ? ",true" : ",false"));
326            break;
327        case Python:
328        default:
329            s.append((isField() ? ",True" : ",False"));
330        }
331        s.append(",");
332        s.append(ring.toScript());
333        s.append(")");
334        return s.toString();
335    }
336
337
338    /**
339     * Comparison with any other object.
340     * @see java.lang.Object#equals(java.lang.Object)
341     */
342    @Override
343    @SuppressWarnings("unchecked")
344    // not jet working
345    public boolean equals(Object b) {
346        if (b == null) {
347            return false;
348        }
349        if (!(b instanceof AlgebraicNumberRing)) {
350            return false;
351        }
352        AlgebraicNumberRing<C> a = (AlgebraicNumberRing<C>) b;
353        return modul.equals(a.modul);
354    }
355
356
357    /**
358     * Hash code for this AlgebraicNumber.
359     * @see java.lang.Object#hashCode()
360     */
361    @Override
362    public int hashCode() {
363        return 37 * modul.hashCode() + ring.hashCode();
364    }
365
366
367    /**
368     * AlgebraicNumber random.
369     * @param n such that 0 &le; v &le; (2<sup>n</sup>-1).
370     * @return a random integer mod modul.
371     */
372    public AlgebraicNumber<C> random(int n) {
373        GenPolynomial<C> x = ring.random(n).monic();
374        return new AlgebraicNumber<C>(this, x);
375    }
376
377
378    /**
379     * AlgebraicNumber random.
380     * @param n such that 0 &le; v &le; (2<sup>n</sup>-1).
381     * @param rnd is a source for random bits.
382     * @return a random integer mod modul.
383     */
384    public AlgebraicNumber<C> random(int n, Random rnd) {
385        GenPolynomial<C> x = ring.random(n, rnd).monic();
386        return new AlgebraicNumber<C>(this, x);
387    }
388
389
390    /**
391     * Parse AlgebraicNumber from String.
392     * @param s String.
393     * @return AlgebraicNumber from s.
394     */
395    public AlgebraicNumber<C> parse(String s) {
396        GenPolynomial<C> x = ring.parse(s);
397        return new AlgebraicNumber<C>(this, x);
398    }
399
400
401    /**
402     * Parse AlgebraicNumber from Reader.
403     * @param r Reader.
404     * @return next AlgebraicNumber from r.
405     */
406    public AlgebraicNumber<C> parse(Reader r) {
407        GenPolynomial<C> x = ring.parse(r);
408        return new AlgebraicNumber<C>(this, x);
409    }
410
411
412    /**
413     * AlgebraicNumber chinese remainder algorithm. Assert deg(c.modul) &ge;
414     * deg(a.modul) and c.modul * a.modul = this.modul.
415     * @param c AlgebraicNumber.
416     * @param ci inverse of c.modul in ring of a.
417     * @param a other AlgebraicNumber.
418     * @return S, with S mod c.modul == c and S mod a.modul == a.
419     */
420    public AlgebraicNumber<C> chineseRemainder(AlgebraicNumber<C> c, AlgebraicNumber<C> ci,
421                    AlgebraicNumber<C> a) {
422        if (true) { // debug
423            if (c.ring.modul.compareTo(a.ring.modul) < 1) {
424                System.out.println("AlgebraicNumber error " + c + ", " + a);
425            }
426        }
427        AlgebraicNumber<C> b = new AlgebraicNumber<C>(a.ring, c.val);
428        // c mod a.modul
429        // c( tbcf(a.modul) ) if deg(a.modul)==1
430        AlgebraicNumber<C> d = a.subtract(b); // a-c mod a.modul
431        if (d.isZERO()) {
432            return new AlgebraicNumber<C>(this, c.val);
433        }
434        b = d.multiply(ci); // b = (a-c)*ci mod a.modul
435        // (c.modul*b)+c mod this.modul = c mod c.modul = 
436        // (c.modul*ci*(a-c)+c) mod a.modul = a mod a.modul
437        GenPolynomial<C> s = c.ring.modul.multiply(b.val);
438        s = s.sum(c.val);
439        return new AlgebraicNumber<C>(this, s);
440    }
441
442
443    /**
444     * AlgebraicNumber interpolation algorithm. Assert deg(c.modul) &ge;
445     * deg(A.modul) and c.modul * A.modul = this.modul. Special case with
446     * deg(A.modul) == 1. Similar algorithm as chinese remainder algorithm.
447     * @param c AlgebraicNumber.
448     * @param ci inverse of (c.modul)(a) in ring of A.
449     * @param am trailing base coefficient of modul of other AlgebraicNumber A.
450     * @param a value of other AlgebraicNumber A.
451     * @return S, with S(c) == c and S(A) == a.
452     */
453    public AlgebraicNumber<C> interpolate(AlgebraicNumber<C> c, C ci, C am, C a) {
454        C b = PolyUtil.<C> evaluateMain(ring.coFac /*a*/, c.val, am);
455        // c mod a.modul
456        // c( tbcf(a.modul) ) if deg(a.modul)==1
457        C d = a.subtract(b); // a-c mod a.modul
458        if (d.isZERO()) {
459            return new AlgebraicNumber<C>(this, c.val);
460        }
461        b = d.multiply(ci); // b = (a-c)*ci mod a.modul
462        // (c.modul*b)+c mod this.modul = c mod c.modul = 
463        // (c.modul*ci*(a-c)+c) mod a.modul = a mod a.modul
464        GenPolynomial<C> s = c.ring.modul.multiply(b);
465        s = s.sum(c.val);
466        return new AlgebraicNumber<C>(this, s);
467    }
468
469
470    /**
471     * Depth of extension field tower.
472     * @return number of nested algebraic extension fields
473     */
474    @SuppressWarnings({ "unchecked", "cast" })
475    public int depth() {
476        AlgebraicNumberRing<C> arr = this;
477        int depth = 1;
478        RingFactory<C> cf = arr.ring.coFac;
479        if (cf instanceof AlgebraicNumberRing) {
480            arr = (AlgebraicNumberRing<C>) (Object) cf;
481            depth += arr.depth();
482        }
483        return depth;
484    }
485
486
487    /**
488     * Degree of extension field.
489     * @return degree of this algebraic extension field
490     */
491    public long extensionDegree() {
492        long degree = modul.degree(0);
493        return degree;
494    }
495
496
497    /**
498     * Total degree of nested extension fields.
499     * @return degree of tower of algebraic extension fields
500     */
501    @SuppressWarnings({ "unchecked", "cast" })
502    public long totalExtensionDegree() {
503        long degree = modul.degree(0);
504        AlgebraicNumberRing<C> arr = this;
505        RingFactory<C> cf = arr.ring.coFac;
506        if (cf instanceof AlgebraicNumberRing) {
507            arr = (AlgebraicNumberRing<C>) (Object) cf;
508            if (degree == 0L) {
509                degree = arr.totalExtensionDegree();
510            } else {
511                degree *= arr.totalExtensionDegree();
512            }
513        }
514        return degree;
515    }
516
517
518    /**
519     * Get a AlgebraicNumber iterator. <b>Note: </b> Only for finite field
520     * coefficients or fields which are iterable.
521     * @return a iterator over all algebraic numbers in this ring.
522     */
523    public Iterator<AlgebraicNumber<C>> iterator() {
524        return new AlgebraicNumberIterator<C>(this);
525    }
526
527}
528
529
530/**
531 * Algebraic number iterator.
532 * @author Heinz Kredel
533 */
534class AlgebraicNumberIterator<C extends RingElem<C>> implements Iterator<AlgebraicNumber<C>> {
535
536
537    /**
538     * data structure.
539     */
540    final Iterator<List<C>> iter;
541
542
543    final List<GenPolynomial<C>> powers;
544
545
546    final AlgebraicNumberRing<C> aring;
547
548
549    private static final Logger logger = LogManager.getLogger(AlgebraicNumberIterator.class);
550
551
552    //  private static final boolean debug = logger.isDebugEnabled();
553
554
555    /**
556     * CartesianProduct iterator constructor.
557     * @param aring AlgebraicNumberRing components of the Cartesian product.
558     */
559    @SuppressWarnings("unchecked")
560    public AlgebraicNumberIterator(AlgebraicNumberRing<C> aring) {
561        RingFactory<C> cf = aring.ring.coFac;
562        this.aring = aring;
563        long d = aring.modul.degree(0);
564        //System.out.println("d = " + d);
565        powers = new ArrayList<GenPolynomial<C>>((int) d);
566        for (long j = d - 1; j >= 0L; j--) {
567            powers.add(aring.ring.univariate(0, j));
568        }
569        //System.out.println("powers = " + powers);
570        if (!(cf instanceof Iterable)) {
571            throw new IllegalArgumentException("only for iterable coefficients implemented");
572        }
573        List<Iterable<C>> comps = new ArrayList<Iterable<C>>((int) d);
574        Iterable<C> cfi = (Iterable<C>) cf;
575        for (long j = 0L; j < d; j++) {
576            comps.add(cfi);
577        }
578        if (cf.isFinite()) {
579            CartesianProduct<C> tuples = new CartesianProduct<C>(comps);
580            iter = tuples.iterator();
581        } else {
582            CartesianProductInfinite<C> tuples = new CartesianProductInfinite<C>(comps);
583            iter = tuples.iterator();
584        }
585        logger.info("iterator for degree {}, finite = {}", d, cf.isFinite());
586    }
587
588
589    /**
590     * Test for availability of a next tuple.
591     * @return true if the iteration has more tuples, else false.
592     */
593    public boolean hasNext() {
594        return iter.hasNext();
595    }
596
597
598    /**
599     * Get next tuple.
600     * @return next tuple.
601     */
602    public AlgebraicNumber<C> next() {
603        List<C> coeffs = iter.next();
604        //System.out.println("coeffs = " + coeffs);
605        GenPolynomial<C> pol = aring.ring.getZERO();
606        int i = 0;
607        for (GenPolynomial<C> f : powers) {
608            C c = coeffs.get(i++);
609            if (c.isZERO()) {
610                continue;
611            }
612            pol = pol.sum(f.multiply(c));
613        }
614        return new AlgebraicNumber<C>(aring, pol);
615    }
616
617
618    /**
619     * Remove a tuple if allowed.
620     */
621    public void remove() {
622        throw new UnsupportedOperationException("cannot remove tuples");
623    }
624
625}