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