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