001 /*
002 * $Id: Quotient.java 3356 2010-10-23 16:41:01Z kredel $
003 */
004
005 package edu.jas.ufd;
006
007
008 import org.apache.log4j.Logger;
009
010 import edu.jas.kern.PrettyPrint;
011 import edu.jas.poly.GenPolynomial;
012 import edu.jas.structure.GcdRingElem;
013
014
015 /**
016 * Quotient, i.e. rational function, based on GenPolynomial with RingElem
017 * interface. Objects of this class are immutable.
018 * @author Heinz Kredel
019 */
020 public class Quotient<C extends GcdRingElem<C>> implements GcdRingElem<Quotient<C>> {
021
022
023 private static final Logger logger = Logger.getLogger(Quotient.class);
024
025
026 private final boolean debug = logger.isDebugEnabled();
027
028
029 /**
030 * Quotient class factory data structure.
031 */
032 public final QuotientRing<C> ring;
033
034
035 /**
036 * Numerator part of the element data structure.
037 */
038 public final GenPolynomial<C> num;
039
040
041 /**
042 * Denominator part of the element data structure.
043 */
044 public final GenPolynomial<C> den;
045
046
047 /**
048 * The constructor creates a Quotient object from a ring factory.
049 * @param r ring factory.
050 */
051 public Quotient(QuotientRing<C> r) {
052 this(r, r.ring.getZERO());
053 }
054
055
056 /**
057 * The constructor creates a Quotient object from a ring factory and a
058 * numerator polynomial. The denominator is assumed to be 1.
059 * @param r ring factory.
060 * @param n numerator polynomial.
061 */
062 public Quotient(QuotientRing<C> r, GenPolynomial<C> n) {
063 this(r, n, r.ring.getONE(), true);
064 }
065
066
067 /**
068 * The constructor creates a Quotient object from a ring factory and a
069 * numerator and denominator polynomial.
070 * @param r ring factory.
071 * @param n numerator polynomial.
072 * @param d denominator polynomial.
073 */
074 public Quotient(QuotientRing<C> r, GenPolynomial<C> n, GenPolynomial<C> d) {
075 this(r, n, d, false);
076 }
077
078
079 /**
080 * The constructor creates a Quotient object from a ring factory and a
081 * numerator and denominator polynomial.
082 * @param r ring factory.
083 * @param n numerator polynomial.
084 * @param d denominator polynomial.
085 * @param isred true if gcd(n,d) == 1, else false.
086 */
087 protected Quotient(QuotientRing<C> r, GenPolynomial<C> n, GenPolynomial<C> d, boolean isred) {
088 if (d == null || d.isZERO()) {
089 throw new IllegalArgumentException("denominator may not be zero");
090 }
091 ring = r;
092 if (d.signum() < 0) {
093 n = n.negate();
094 d = d.negate();
095 }
096 if (!isred) {
097 // must reduce to lowest terms
098 GenPolynomial<C> gcd = ring.gcd(n, d);
099 if (false || debug) {
100 logger.info("gcd = " + gcd);
101 }
102 //GenPolynomial<C> gcd = ring.ring.getONE();
103 if (!gcd.isONE()) {
104 //logger.info("gcd = " + gcd);
105 n = ring.divide(n, gcd);
106 d = ring.divide(d, gcd);
107 }
108 }
109 C lc = d.leadingBaseCoefficient();
110 if (!lc.isONE() && lc.isUnit()) {
111 lc = lc.inverse();
112 n = n.multiply(lc);
113 d = d.multiply(lc);
114 }
115 num = n;
116 den = d;
117 }
118
119
120 /**
121 * Get the corresponding element factory.
122 * @return factory for this Element.
123 * @see edu.jas.structure.Element#factory()
124 */
125 public QuotientRing<C> factory() {
126 return ring;
127 }
128
129
130 /**
131 * Clone this.
132 * @see java.lang.Object#clone()
133 */
134 @Override
135 public Quotient<C> clone() {
136 return new Quotient<C>(ring, num, den, true);
137 }
138
139
140 /**
141 * Is Quotient zero.
142 * @return If this is 0 then true is returned, else false.
143 * @see edu.jas.structure.RingElem#isZERO()
144 */
145 public boolean isZERO() {
146 return num.isZERO();
147 }
148
149
150 /**
151 * Is Quotient one.
152 * @return If this is 1 then true is returned, else false.
153 * @see edu.jas.structure.RingElem#isONE()
154 */
155 public boolean isONE() {
156 return num.equals(den);
157 }
158
159
160 /**
161 * Is Quotient a unit.
162 * @return If this is a unit then true is returned, else false.
163 * @see edu.jas.structure.RingElem#isUnit()
164 */
165 public boolean isUnit() {
166 if (num.isZERO()) {
167 return false;
168 } else {
169 return true;
170 }
171 }
172
173
174 /**
175 * Is Qoutient a constant.
176 * @return true, if this has constant numerator and denominator, else false.
177 */
178 public boolean isConstant() {
179 return num.isConstant() && den.isConstant();
180 }
181
182
183 /**
184 * Get the String representation as RingElem.
185 * @see java.lang.Object#toString()
186 */
187 @Override
188 public String toString() {
189 if (PrettyPrint.isTrue()) {
190 String s = "{ " + num.toString(ring.ring.getVars());
191 if (!den.isONE()) {
192 s += " | " + den.toString(ring.ring.getVars());
193 }
194 return s + " }";
195 } else {
196 return "Quotient[ " + num.toString() + " | " + den.toString() + " ]";
197 }
198 }
199
200
201 /**
202 * Get a scripting compatible string representation.
203 * @return script compatible representation for this Element.
204 * @see edu.jas.structure.Element#toScript()
205 */
206 //JAVA6only: @Override
207 public String toScript() {
208 // Python case
209 if (den.isONE()) {
210 return num.toScript();
211 } else {
212 return num.toScript() + " / " + den.toScript();
213 }
214 }
215
216
217 /**
218 * Get a scripting compatible string representation of the factory.
219 * @return script compatible representation for this ElemFactory.
220 * @see edu.jas.structure.Element#toScriptFactory()
221 */
222 //JAVA6only: @Override
223 public String toScriptFactory() {
224 // Python case
225 return factory().toScript();
226 }
227
228
229 /**
230 * Quotient comparison.
231 * @param b Quotient.
232 * @return sign(this-b).
233 */
234 //JAVA6only: @Override
235 public int compareTo(Quotient<C> b) {
236 if (b == null || b.isZERO()) {
237 return this.signum();
238 }
239 if (this.isZERO()) {
240 return -b.signum();
241 }
242 int s1 = num.signum();
243 int s2 = b.num.signum();
244 int t = (s1 - s2) / 2;
245 if (t != 0) {
246 return t;
247 }
248 GenPolynomial<C> r = num.multiply(b.den);
249 GenPolynomial<C> s = den.multiply(b.num);
250 //GenPolynomial<C> x = r.subtract( s );
251 //return x.signum();
252 return r.compareTo(s);
253 }
254
255
256 /**
257 * Comparison with any other object.
258 * @see java.lang.Object#equals(java.lang.Object)
259 */
260 @SuppressWarnings("unchecked")
261 // not jet working
262 @Override
263 public boolean equals(Object b) {
264 if (!(b instanceof Quotient)) {
265 return false;
266 }
267 Quotient<C> a = null;
268 try {
269 a = (Quotient<C>) b;
270 } catch (ClassCastException e) {
271 }
272 if (a == null) {
273 return false;
274 }
275 //return ( 0 == compareTo( a ) );
276 return num.equals(a.num) && den.equals(a.den);
277 }
278
279
280 /**
281 * Hash code for this local.
282 * @see java.lang.Object#hashCode()
283 */
284 @Override
285 public int hashCode() {
286 int h;
287 h = ring.hashCode();
288 h = 37 * h + num.hashCode();
289 h = 37 * h + den.hashCode();
290 return h;
291 }
292
293
294 /**
295 * Quotient absolute value.
296 * @return the absolute value of this.
297 * @see edu.jas.structure.RingElem#abs()
298 */
299 public Quotient<C> abs() {
300 return new Quotient<C>(ring, num.abs(), den, true);
301 }
302
303
304 /**
305 * Quotient summation.
306 * @param S Quotient.
307 * @return this+S.
308 */
309 public Quotient<C> sum(Quotient<C> S) {
310 if (S == null || S.isZERO()) {
311 return this;
312 }
313 if (this.isZERO()) {
314 return S;
315 }
316 GenPolynomial<C> n;
317 if (den.isONE() && S.den.isONE()) {
318 n = num.sum(S.num);
319 return new Quotient<C>(ring, n);
320 }
321 if (den.isONE()) {
322 n = num.multiply(S.den);
323 n = n.sum(S.num);
324 return new Quotient<C>(ring, n, S.den, true);
325 }
326 if (S.den.isONE()) {
327 n = S.num.multiply(den);
328 n = n.sum(num);
329 return new Quotient<C>(ring, n, den, true);
330 }
331 GenPolynomial<C> d;
332 GenPolynomial<C> sd;
333 GenPolynomial<C> g;
334 g = ring.gcd(den, S.den);
335 if (g.isONE()) {
336 d = den;
337 sd = S.den;
338 } else {
339 d = ring.divide(den, g);
340 sd = ring.divide(S.den, g);
341 }
342 n = num.multiply(sd);
343 n = n.sum(d.multiply(S.num));
344 if (n.isZERO()) {
345 return ring.getZERO();
346 }
347 GenPolynomial<C> f;
348 GenPolynomial<C> dd;
349 dd = den;
350 if (!g.isONE()) {
351 f = ring.gcd(n, g);
352 if (!f.isONE()) {
353 n = ring.divide(n, f);
354 dd = ring.divide(den, f);
355 }
356 }
357 d = dd.multiply(sd);
358 return new Quotient<C>(ring, n, d, true);
359 }
360
361
362 /**
363 * Quotient negate.
364 * @return -this.
365 * @see edu.jas.structure.RingElem#negate()
366 */
367 public Quotient<C> negate() {
368 return new Quotient<C>(ring, num.negate(), den, true);
369 }
370
371
372 /**
373 * Quotient signum.
374 * @see edu.jas.structure.RingElem#signum()
375 * @return signum(this).
376 */
377 public int signum() {
378 return num.signum();
379 }
380
381
382 /**
383 * Quotient subtraction.
384 * @param S Quotient.
385 * @return this-S.
386 */
387 public Quotient<C> subtract(Quotient<C> S) {
388 return sum(S.negate());
389 }
390
391
392 /**
393 * Quotient division.
394 * @param S Quotient.
395 * @return this/S.
396 */
397 public Quotient<C> divide(Quotient<C> S) {
398 return multiply(S.inverse());
399 }
400
401
402 /**
403 * Quotient inverse.
404 * @see edu.jas.structure.RingElem#inverse()
405 * @return S with S = 1/this.
406 */
407 public Quotient<C> inverse() {
408 return new Quotient<C>(ring, den, num, true);
409 }
410
411
412 /**
413 * Quotient remainder.
414 * @param S Quotient.
415 * @return this - (this/S)*S.
416 */
417 public Quotient<C> remainder(Quotient<C> S) {
418 if (num.isZERO()) {
419 throw new ArithmeticException("element not invertible " + this);
420 }
421 return ring.getZERO();
422 }
423
424
425 /**
426 * Quotient multiplication.
427 * @param S Quotient.
428 * @return this*S.
429 */
430 public Quotient<C> multiply(Quotient<C> S) {
431 if (S == null || S.isZERO()) {
432 return S;
433 }
434 if (num.isZERO()) {
435 return this;
436 }
437 if (S.isONE()) {
438 return this;
439 }
440 if (this.isONE()) {
441 return S;
442 }
443 GenPolynomial<C> n;
444 if (den.isONE() && S.den.isONE()) {
445 n = num.multiply(S.num);
446 return new Quotient<C>(ring, n);
447 }
448 GenPolynomial<C> g;
449 GenPolynomial<C> d;
450 if (den.isONE()) {
451 g = ring.gcd(num, S.den);
452 n = ring.divide(num, g);
453 d = ring.divide(S.den, g);
454 n = n.multiply(S.num);
455 return new Quotient<C>(ring, n, d, true);
456 }
457 if (S.den.isONE()) {
458 g = ring.gcd(S.num, den);
459 n = ring.divide(S.num, g);
460 d = ring.divide(den, g);
461 n = n.multiply(num);
462 return new Quotient<C>(ring, n, d, true);
463 }
464 GenPolynomial<C> f;
465 GenPolynomial<C> sd;
466 GenPolynomial<C> sn;
467 g = ring.gcd(num, S.den);
468 n = ring.divide(num, g);
469 sd = ring.divide(S.den, g);
470 f = ring.gcd(den, S.num);
471 d = ring.divide(den, f);
472 sn = ring.divide(S.num, f);
473 n = n.multiply(sn);
474 d = d.multiply(sd);
475 return new Quotient<C>(ring, n, d, true);
476 }
477
478
479 /**
480 * Quotient multiplication by GenPolynomial.
481 * @param b GenPolynomial<C>.
482 * @return this*b.
483 */
484 public Quotient<C> multiply(GenPolynomial<C> b) {
485 if (b == null || b.isZERO()) {
486 return ring.getZERO();
487 }
488 if (num.isZERO()) {
489 return this;
490 }
491 if (b.isONE()) {
492 return this;
493 }
494 GenPolynomial<C> gcd = ring.gcd(b, den);
495 GenPolynomial<C> d = den;
496 if (!gcd.isONE()) {
497 b = ring.divide(b, gcd);
498 d = ring.divide(d, gcd);
499 }
500 if (this.isONE()) {
501 return new Quotient<C>(ring, b, d, true);
502 }
503 GenPolynomial<C> n = num.multiply(b);
504 return new Quotient<C>(ring, n, d, true);
505 }
506
507
508 /**
509 * Quotient multiplication by coefficient.
510 * @param b coefficient.
511 * @return this*b.
512 */
513 public Quotient<C> multiply(C b) {
514 if (b == null || b.isZERO()) {
515 return ring.getZERO();
516 }
517 if (num.isZERO()) {
518 return this;
519 }
520 if (b.isONE()) {
521 return this;
522 }
523 GenPolynomial<C> n = num.multiply(b);
524 return new Quotient<C>(ring, n, den, true);
525 }
526
527
528 /**
529 * Quotient monic.
530 * @return this with monic value part.
531 */
532 public Quotient<C> monic() {
533 if (num.isZERO()) {
534 return this;
535 }
536 C lbc = num.leadingBaseCoefficient();
537 if (!lbc.isUnit()) {
538 return this;
539 }
540 lbc = lbc.inverse();
541 lbc = lbc.abs();
542 GenPolynomial<C> n = num.multiply(lbc);
543 GenPolynomial<C> d = den.multiply(lbc);
544 return new Quotient<C>(ring, n, d, true);
545 }
546
547
548 /**
549 * Greatest common divisor.
550 * @param b other element.
551 * @return gcd(this,b).
552 */
553 public Quotient<C> gcd(Quotient<C> b) {
554 if (b == null || b.isZERO()) {
555 return this;
556 }
557 if (this.isZERO()) {
558 return b;
559 }
560 return ring.getONE();
561 }
562
563
564 /**
565 * Extended greatest common divisor.
566 * @param b other element.
567 * @return [ gcd(this,b), c1, c2 ] with c1*this + c2*b = gcd(this,b).
568 */
569 @SuppressWarnings("unchecked")
570 public Quotient<C>[] egcd(Quotient<C> b) {
571 Quotient<C>[] ret = (Quotient<C>[]) new Quotient[3];
572 ret[0] = null;
573 ret[1] = null;
574 ret[2] = null;
575 if (b == null || b.isZERO()) {
576 ret[0] = this;
577 return ret;
578 }
579 if (this.isZERO()) {
580 ret[0] = b;
581 return ret;
582 }
583 GenPolynomial<C> two = ring.ring.fromInteger(2);
584 ret[0] = ring.getONE();
585 ret[1] = (this.multiply(two)).inverse();
586 ret[2] = (b.multiply(two)).inverse();
587 return ret;
588 }
589 }