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