001/* 002 * $Id: SolvableQuotient.java 5267 2015-07-27 17:57:50Z kredel $ 003 */ 004 005package edu.jas.gbufd; 006 007 008import java.util.Arrays; 009 010import org.apache.log4j.Logger; 011 012import edu.jas.kern.PrettyPrint; 013import edu.jas.poly.ExpVector; 014import edu.jas.poly.GenPolynomial; 015import edu.jas.poly.GenSolvablePolynomial; 016import edu.jas.structure.GcdRingElem; 017import edu.jas.structure.QuotPair; 018 019 020/** 021 * SolvableQuotient, that is a (left) rational function, based on 022 * GenSolvablePolynomial with RingElem interface. Objects of this class are 023 * immutable. 024 * @author Heinz Kredel 025 */ 026public class SolvableQuotient<C extends GcdRingElem<C>> implements GcdRingElem<SolvableQuotient<C>>, 027 QuotPair<GenPolynomial<C>> { 028 029 030 private static final Logger logger = Logger.getLogger(SolvableQuotient.class); 031 032 033 private final boolean debug = logger.isDebugEnabled(); 034 035 036 /** 037 * SolvableQuotient class factory data structure. 038 */ 039 public final SolvableQuotientRing<C> ring; 040 041 042 /** 043 * Numerator part of the element data structure. 044 */ 045 public final GenSolvablePolynomial<C> num; 046 047 048 /** 049 * Denominator part of the element data structure. 050 */ 051 public final GenSolvablePolynomial<C> den; 052 053 054 /** 055 * The constructor creates a SolvableQuotient object from a ring factory. 056 * @param r ring factory. 057 */ 058 public SolvableQuotient(SolvableQuotientRing<C> r) { 059 this(r, r.ring.getZERO()); 060 } 061 062 063 /** 064 * The constructor creates a SolvableQuotient object from a ring factory and 065 * a numerator polynomial. The denominator is assumed to be 1. 066 * @param r ring factory. 067 * @param n numerator solvable polynomial. 068 */ 069 public SolvableQuotient(SolvableQuotientRing<C> r, GenSolvablePolynomial<C> n) { 070 this(r, n, r.ring.getONE(), true); 071 } 072 073 074 /** 075 * The constructor creates a SolvableQuotient object from a ring factory and 076 * a numerator and denominator solvable polynomial. 077 * @param r ring factory. 078 * @param n numerator polynomial. 079 * @param d denominator polynomial. 080 */ 081 public SolvableQuotient(SolvableQuotientRing<C> r, GenSolvablePolynomial<C> n, GenSolvablePolynomial<C> d) { 082 this(r, n, d, false); 083 } 084 085 086 /** 087 * The constructor creates a SolvableQuotient object from a ring factory and 088 * a numerator and denominator polynomial. 089 * @param r ring factory. 090 * @param n numerator polynomial. 091 * @param d denominator polynomial. 092 * @param isred <em>unused at the moment</em>. 093 */ 094 protected SolvableQuotient(SolvableQuotientRing<C> r, GenSolvablePolynomial<C> n, 095 GenSolvablePolynomial<C> d, boolean isred) { 096 if (d == null || d.isZERO()) { 097 throw new IllegalArgumentException("denominator may not be zero"); 098 } 099 ring = r; 100 if (d.signum() < 0) { 101 n = (GenSolvablePolynomial<C>) n.negate(); 102 d = (GenSolvablePolynomial<C>) d.negate(); 103 } 104 if (isred) { 105 num = n; 106 den = d; 107 return; 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 if (n.compareTo(d) == 0) { 116 num = ring.ring.getONE(); 117 den = ring.ring.getONE(); 118 return; 119 } 120 if (n.negate().compareTo(d) == 0) { 121 num = (GenSolvablePolynomial<C>) ring.ring.getONE().negate(); 122 den = ring.ring.getONE(); 123 return; 124 } 125 if (n.isZERO()) { 126 num = n; 127 den = ring.ring.getONE(); 128 return; 129 } 130 //if (n.isONE() || d.isONE()) { 131 if (n.isConstant() || d.isConstant()) { 132 num = n; 133 den = d; 134 return; 135 } 136 // must reduce to lowest terms 137 // not perfect, TODO 138 GenSolvablePolynomial<C>[] gcd = PolyModUtil.<C> syzGcdCofactors(r.ring, n, d); 139 if (!gcd[0].isONE()) { 140 logger.info("constructor: gcd = " + Arrays.toString(gcd)); // + ", " + n + ", " +d); 141 n = gcd[1]; 142 d = gcd[2]; 143 if (n.isConstant() || d.isConstant()) { 144 num = n; 145 den = d; 146 return; 147 } 148 } 149 // not perfect, TODO 150 GenSolvablePolynomial<C>[] simp = ring.engine.leftSimplifier(n, d); 151 logger.info("simp: " + Arrays.toString(simp) + ", " + n + ", " + d); 152 num = simp[0]; 153 den = simp[1]; 154 } 155 156 157 /** 158 * Get the corresponding element factory. 159 * @return factory for this Element. 160 * @see edu.jas.structure.Element#factory() 161 */ 162 public SolvableQuotientRing<C> factory() { 163 return ring; 164 } 165 166 167 /** 168 * Numerator. 169 * @see edu.jas.structure.QuotPair#numerator() 170 */ 171 public GenSolvablePolynomial<C> numerator() { 172 return num; 173 } 174 175 176 /** 177 * Denominator. 178 * @see edu.jas.structure.QuotPair#denominator() 179 */ 180 public GenSolvablePolynomial<C> denominator() { 181 return den; 182 } 183 184 185 /** 186 * Clone this. 187 * @see java.lang.Object#clone() 188 */ 189 @Override 190 public SolvableQuotient<C> copy() { 191 return new SolvableQuotient<C>(ring, num, den, true); 192 } 193 194 195 /** 196 * Is SolvableQuotient zero. 197 * @return If this is 0 then true is returned, else false. 198 * @see edu.jas.structure.RingElem#isZERO() 199 */ 200 public boolean isZERO() { 201 return num.isZERO(); 202 } 203 204 205 /** 206 * Is SolvableQuotient one. 207 * @return If this is 1 then true is returned, else false. 208 * @see edu.jas.structure.RingElem#isONE() 209 */ 210 public boolean isONE() { 211 return num.compareTo(den) == 0; 212 } 213 214 215 /** 216 * Is SolvableQuotient a unit. 217 * @return If this is a unit then true is returned, else false. 218 * @see edu.jas.structure.RingElem#isUnit() 219 */ 220 public boolean isUnit() { 221 if (num.isZERO()) { 222 return false; 223 } 224 return true; 225 } 226 227 228 /** 229 * Is Qoutient a constant. 230 * @return true, if this has constant numerator and denominator, else false. 231 */ 232 public boolean isConstant() { 233 return num.isConstant() && den.isConstant(); 234 } 235 236 237 /** 238 * Get the String representation as RingElem. 239 * @see java.lang.Object#toString() 240 */ 241 @Override 242 public String toString() { 243 if (PrettyPrint.isTrue()) { 244 String s = "{ " + num.toString(ring.ring.getVars()); 245 if (!den.isONE()) { 246 s += " | " + den.toString(ring.ring.getVars()); 247 } 248 return s + " }"; 249 } 250 return "SolvableQuotient[ " + num.toString() + " | " + den.toString() + " ]"; 251 } 252 253 254 /** 255 * Get a scripting compatible string representation. 256 * @return script compatible representation for this Element. 257 * @see edu.jas.structure.Element#toScript() 258 */ 259 @Override 260 public String toScript() { 261 // any scripting case 262 if (den.isONE()) { 263 return num.toScript(); 264 } 265 return num.toScript() + " / " + den.toScript(); 266 } 267 268 269 /** 270 * Get a scripting compatible string representation of the factory. 271 * @return script compatible representation for this ElemFactory. 272 * @see edu.jas.structure.Element#toScriptFactory() 273 */ 274 @Override 275 public String toScriptFactory() { 276 return factory().toScript(); 277 } 278 279 280 /** 281 * SolvableQuotient comparison. 282 * @param b SolvableQuotient. 283 * @return sign(this-b). 284 */ 285 @Override 286 public int compareTo(SolvableQuotient<C> b) { 287 if (b == null || b.isZERO()) { 288 return this.signum(); 289 } 290 if (this.isZERO()) { 291 return -b.signum(); 292 } 293 // assume sign(den,b.den) > 0 294 int s1 = num.signum(); 295 int s2 = b.num.signum(); 296 int t = (s1 - s2) / 2; 297 if (t != 0) { 298 return t; 299 } 300 if (den.compareTo(b.den) == 0) { 301 return num.compareTo(b.num); 302 } 303 GenSolvablePolynomial<C> r, s; 304 // if (den.isONE()) { 305 // r = b.den.multiply(num); 306 // s = b.num; 307 // return r.compareTo(s); 308 // } 309 // if (b.den.isONE()) { 310 // r = num; 311 // s = den.multiply(b.num); 312 // return r.compareTo(s); 313 // } 314 GenSolvablePolynomial<C>[] oc = ring.engine.leftOreCond(den, b.den); 315 if (debug) { 316 System.out.println("oc[0] den =<>= oc[1] b.den: (" + oc[0] + ") (" + den + ") = (" + oc[1] 317 + ") (" + b.den + ")"); 318 } 319 r = oc[0].multiply(num); 320 s = oc[1].multiply(b.num); 321 //System.out.println("r = " + r); 322 //System.out.println("s = " + s); 323 return r.compareTo(s); 324 } 325 326 327 /** 328 * Comparison with any other object. 329 * @see java.lang.Object#equals(java.lang.Object) 330 */ 331 @SuppressWarnings("unchecked") 332 @Override 333 public boolean equals(Object b) { 334 if (b == null) { 335 return false; 336 } 337 if (!(b instanceof SolvableQuotient)) { 338 return false; 339 } 340 SolvableQuotient<C> a = (SolvableQuotient<C>) b; 341 if (num.equals(a.num) && den.equals(a.den)) { // short cut 342 return true; 343 } 344 return compareTo(a) == 0; 345 } 346 347 348 /** 349 * Hash code for this element. 350 * @see java.lang.Object#hashCode() 351 */ 352 @Override 353 public int hashCode() { 354 int h; 355 h = ring.hashCode(); 356 h = 37 * h + num.hashCode(); 357 h = 37 * h + den.hashCode(); 358 return h; 359 } 360 361 362 /** 363 * SolvableQuotient right fraction. <b>Note:</b> It is not possible to 364 * distinguish right from left fractions in the current implementation. So 365 * it is not possible to compute with right fractions. 366 * @return SolvableQuotient(a,b), where den<sup>-1</sup> num = a 367 * b<sup>-1</sup> 368 */ 369 public SolvableQuotient<C> rightFraction() { 370 if (isZERO() || isONE()) { 371 return this; 372 } 373 GenSolvablePolynomial<C>[] oc = ring.engine.rightOreCond(num, den); 374 return new SolvableQuotient<C>(ring, oc[1], oc[0], true); // reversed, true is wrong but okay 375 } 376 377 378 /** 379 * Test if SolvableQuotient right fraction. <b>Note:</b> It is not possible 380 * to distinguish right from left fractions in the current implementation. 381 * So it is not possible to compute with right fractions. 382 * @param s = SolvableQuotient(a,b) 383 * @return true if s is a right fraction of this, i.e. den<sup>-1</sup> num 384 * = a b<sup>-1</sup> 385 */ 386 public boolean isRightFraction(SolvableQuotient<C> s) { 387 if (isZERO()) { 388 return s.isZERO(); 389 } 390 if (isONE()) { 391 return s.isONE(); 392 } 393 GenSolvablePolynomial<C> x = den.multiply(s.num); 394 GenSolvablePolynomial<C> y = num.multiply(s.den); 395 return x.compareTo(y) == 0; 396 } 397 398 399 /** 400 * SolvableQuotient absolute value. 401 * @return the absolute value of this. 402 * @see edu.jas.structure.RingElem#abs() 403 */ 404 public SolvableQuotient<C> abs() { 405 return new SolvableQuotient<C>(ring, (GenSolvablePolynomial<C>) num.abs(), den, true); 406 } 407 408 409 /** 410 * SolvableQuotient summation. 411 * @param S SolvableQuotient. 412 * @return this+S. 413 */ 414 public SolvableQuotient<C> sum(SolvableQuotient<C> S) { 415 if (S == null || S.isZERO()) { 416 return this; 417 } 418 if (this.isZERO()) { 419 return S; 420 } 421 GenSolvablePolynomial<C> n, d, n1, n2; 422 if (den.isONE() && S.den.isONE()) { 423 n = (GenSolvablePolynomial<C>) num.sum(S.num); 424 return new SolvableQuotient<C>(ring, n, den, true); 425 } 426 /* wrong: 427 if (den.isONE()) { 428 n = S.den.multiply(num); 429 n = (GenSolvablePolynomial<C>) n.sum(S.num); 430 return new SolvableQuotient<C>(ring, n, S.den, false); 431 } 432 if (S.den.isONE()) { 433 n = den.multiply(S.num); 434 n = (GenSolvablePolynomial<C>) n.sum(num); 435 return new SolvableQuotient<C>(ring, n, den, false); 436 } 437 */ 438 if (den.compareTo(S.den) == 0) { // correct ? 439 //d = den.multiply(den); 440 //n1 = den.multiply(S.num); 441 //n2 = S.den.multiply(num); 442 n = (GenSolvablePolynomial<C>) num.sum(S.num); 443 return new SolvableQuotient<C>(ring, n, den, false); 444 } 445 // general case 446 GenSolvablePolynomial<C>[] oc = ring.engine.leftOreCond(den, S.den); 447 if (debug) { 448 System.out.println("oc[0] den =sum= oc[1] S.den: (" + oc[0] + ") (" + den + ") = (" + oc[1] 449 + ") (" + S.den + ")"); 450 } 451 d = oc[0].multiply(den); 452 n1 = oc[0].multiply(num); 453 n2 = oc[1].multiply(S.num); 454 n = (GenSolvablePolynomial<C>) n1.sum(n2); 455 //System.out.println("n = " + n); 456 //System.out.println("d = " + d); 457 return new SolvableQuotient<C>(ring, n, d, false); 458 } 459 460 461 /** 462 * SolvableQuotient negate. 463 * @return -this. 464 * @see edu.jas.structure.RingElem#negate() 465 */ 466 public SolvableQuotient<C> negate() { 467 return new SolvableQuotient<C>(ring, (GenSolvablePolynomial<C>) num.negate(), den, true); 468 } 469 470 471 /** 472 * SolvableQuotient signum. 473 * @see edu.jas.structure.RingElem#signum() 474 * @return signum(this). 475 */ 476 public int signum() { 477 // assume sign(den) > 0 478 return num.signum(); 479 } 480 481 482 /** 483 * SolvableQuotient subtraction. 484 * @param S SolvableQuotient. 485 * @return this-S. 486 */ 487 public SolvableQuotient<C> subtract(SolvableQuotient<C> S) { 488 return sum(S.negate()); 489 } 490 491 492 /** 493 * SolvableQuotient division. 494 * @param S SolvableQuotient. 495 * @return this/S. 496 */ 497 public SolvableQuotient<C> divide(SolvableQuotient<C> S) { 498 return multiply(S.inverse()); 499 } 500 501 502 /** 503 * SolvableQuotient inverse. 504 * @see edu.jas.structure.RingElem#inverse() 505 * @return S with S = 1/this. 506 */ 507 public SolvableQuotient<C> inverse() { 508 if (num.isZERO()) { 509 throw new ArithmeticException("element not invertible " + this); 510 } 511 return new SolvableQuotient<C>(ring, den, num, true); 512 } 513 514 515 /** 516 * SolvableQuotient remainder. 517 * @param S SolvableQuotient. 518 * @return this - (this/S)*S. 519 */ 520 public SolvableQuotient<C> remainder(SolvableQuotient<C> S) { 521 if (S.isZERO()) { 522 throw new ArithmeticException("element not invertible " + S); 523 } 524 return ring.getZERO(); 525 } 526 527 528 /** 529 * Quotient and remainder by division of this by S. 530 * @param S a SolvableQuotient 531 * @return [this/S, this - (this/S)*S]. 532 */ 533 public SolvableQuotient<C>[] quotientRemainder(SolvableQuotient<C> S) { 534 return new SolvableQuotient[] { divide(S), remainder(S) }; 535 } 536 537 538 /** 539 * SolvableQuotient multiplication. 540 * @param S SolvableQuotient. 541 * @return this*S. 542 */ 543 public SolvableQuotient<C> multiply(SolvableQuotient<C> S) { 544 if (S == null || S.isZERO()) { 545 return S; 546 } 547 if (num.isZERO()) { 548 return this; 549 } 550 if (S.isONE()) { 551 return this; 552 } 553 if (this.isONE()) { 554 return S; 555 } 556 GenSolvablePolynomial<C> n, d; 557 if (den.isONE() && S.den.isONE()) { 558 n = num.multiply(S.num); 559 return new SolvableQuotient<C>(ring, n, den, true); 560 } 561 /* wrong: 562 if (den.isONE()) { 563 d = S.den; 564 n = num.multiply(S.num); 565 return new SolvableQuotient<C>(ring, n, d, false); 566 } 567 if (S.den.isONE()) { 568 d = den; 569 n = num.multiply(S.num); 570 return new SolvableQuotient<C>(ring, n, d, false); 571 } 572 */ 573 // if ( den.compareTo(S.den) == 0 ) { // not correct ? 574 // d = den.multiply(den); 575 // n = num.multiply(S.num); 576 // return new SolvableQuotient<C>(ring, n, d, false); 577 // } 578 GenSolvablePolynomial<C>[] oc = ring.engine.leftOreCond(num, S.den); 579 n = oc[1].multiply(S.num); 580 d = oc[0].multiply(den); 581 if (debug) { 582 System.out.println("oc[0] num =mult= oc[1] S.den: (" + oc[0] + ") (" + num + ") = (" + oc[1] 583 + ") (" + S.den + ")"); 584 } 585 return new SolvableQuotient<C>(ring, n, d, false); 586 } 587 588 589 /** 590 * SolvableQuotient multiplication by GenSolvablePolynomial. 591 * @param b GenSolvablePolynomial<C>. 592 * @return this*b. 593 */ 594 public SolvableQuotient<C> multiply(GenSolvablePolynomial<C> b) { 595 if (b == null || b.isZERO()) { 596 return ring.getZERO(); 597 } 598 if (num.isZERO()) { 599 return this; 600 } 601 if (b.isONE()) { 602 return this; 603 } 604 GenSolvablePolynomial<C> n = num.multiply(b); 605 return new SolvableQuotient<C>(ring, n, den, false); 606 } 607 608 609 /** 610 * SolvableQuotient multiplication by coefficient. 611 * @param b coefficient. 612 * @return this*b. 613 */ 614 public SolvableQuotient<C> multiply(C b) { 615 if (b == null || b.isZERO()) { 616 return ring.getZERO(); 617 } 618 if (num.isZERO()) { 619 return this; 620 } 621 if (b.isONE()) { 622 return this; 623 } 624 GenSolvablePolynomial<C> n = num.multiply(b); 625 return new SolvableQuotient<C>(ring, n, den, false); 626 } 627 628 629 /** 630 * SolvableQuotient multiplication by exponent. 631 * @param e exponent vector. 632 * @return this*b. 633 */ 634 public SolvableQuotient<C> multiply(ExpVector e) { 635 if (e == null || e.isZERO()) { 636 return this; 637 } 638 if (num.isZERO()) { 639 return this; 640 } 641 GenSolvablePolynomial<C> n = num.multiply(e); 642 return new SolvableQuotient<C>(ring, n, den, false); 643 } 644 645 646 /** 647 * SolvableQuotient monic. 648 * @return this with monic value part. 649 */ 650 public SolvableQuotient<C> monic() { 651 if (num.isZERO()) { 652 return this; 653 } 654 C lbc = num.leadingBaseCoefficient(); 655 if (!lbc.isUnit()) { 656 return this; 657 } 658 lbc = lbc.inverse(); 659 //lbc = lbc.abs(); 660 GenSolvablePolynomial<C> n = num.multiply(lbc); 661 //GenSolvablePolynomial<C> d = (GenSolvablePolynomial<C>) den.multiply(lbc); 662 return new SolvableQuotient<C>(ring, n, den, true); 663 } 664 665 666 /** 667 * Greatest common divisor. 668 * @param b other element. 669 * @return gcd(this,b). 670 */ 671 public SolvableQuotient<C> gcd(SolvableQuotient<C> b) { 672 if (b == null || b.isZERO()) { 673 return this; 674 } 675 if (this.isZERO()) { 676 return b; 677 } 678 if (this.equals(b)) { 679 return this; 680 } 681 return ring.getONE(); 682 } 683 684 685 /** 686 * Extended greatest common divisor. 687 * @param b other element. 688 * @return [ gcd(this,b), c1, c2 ] with c1*this + c2*b = gcd(this,b). 689 */ 690 @SuppressWarnings("cast") 691 public SolvableQuotient<C>[] egcd(SolvableQuotient<C> b) { 692 SolvableQuotient<C>[] ret = (SolvableQuotient<C>[]) new SolvableQuotient[3]; 693 ret[0] = null; 694 ret[1] = null; 695 ret[2] = null; 696 if (b == null || b.isZERO()) { 697 ret[0] = this; 698 return ret; 699 } 700 if (this.isZERO()) { 701 ret[0] = b; 702 return ret; 703 } 704 GenSolvablePolynomial<C> two = ring.ring.fromInteger(2); 705 ret[0] = ring.getONE(); 706 ret[1] = (this.multiply(two)).inverse(); 707 ret[2] = (b.multiply(two)).inverse(); 708 return ret; 709 } 710 711}