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