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