001/* 002 * $Id: Residue.java 4655 2013-10-05 10:12:32Z kredel $ 003 */ 004 005package edu.jas.application; 006 007 008import edu.jas.kern.PrettyPrint; 009import edu.jas.poly.GenPolynomial; 010import edu.jas.poly.PolyUtil; 011import edu.jas.structure.GcdRingElem; 012 013 014/** 015 * Residue ring element based on GenPolynomial with RingElem interface. Objects 016 * of this class are (nearly) immutable. 017 * @author Heinz Kredel 018 */ 019public class Residue<C extends GcdRingElem<C>> implements GcdRingElem<Residue<C>> { 020 021 022 /** 023 * Residue class factory data structure. 024 */ 025 public final ResidueRing<C> ring; 026 027 028 /** 029 * Value part of the element data structure. 030 */ 031 public final GenPolynomial<C> val; 032 033 034 /** 035 * Flag to remember if this residue element is a unit. -1 is unknown, 1 is 036 * unit, 0 not a unit. 037 */ 038 protected int isunit = -1; // initially unknown 039 040 041 /** 042 * The constructor creates a Residue object from a ring factory. 043 * @param r residue ring factory. 044 */ 045 public Residue(ResidueRing<C> r) { 046 this(r, r.ring.getZERO(), 0); 047 } 048 049 050 /** 051 * The constructor creates a Residue object from a ring factory and a 052 * polynomial. 053 * @param r residue ring factory. 054 * @param a polynomial. 055 */ 056 public Residue(ResidueRing<C> r, GenPolynomial<C> a) { 057 this(r, a, -1); 058 } 059 060 061 /** 062 * The constructor creates a Residue object from a ring factory, a 063 * polynomial and an indicator if a is a unit. 064 * @param r residue ring factory. 065 * @param a polynomial. 066 * @param u isunit indicator, -1, 0, 1. 067 */ 068 public Residue(ResidueRing<C> r, GenPolynomial<C> a, int u) { 069 ring = r; 070 val = ring.ideal.normalform(a); //.monic() no go 071 if ( u == 0 || u == 1 ) { 072 isunit = u; 073 return; 074 } 075 if (val.isZERO()) { 076 isunit = 0; 077 return; 078 } 079 if (ring.isField()) { 080 isunit = 1; 081 return; 082 } 083 if ( val.isUnit() ) { 084 isunit = 1; 085 //} else { // not possible 086 //isunit = 0; 087 } 088 isunit = -1; 089 } 090 091 092 /** 093 * Get the corresponding element factory. 094 * @return factory for this Element. 095 * @see edu.jas.structure.Element#factory() 096 */ 097 public ResidueRing<C> factory() { 098 return ring; 099 } 100 101 102 /** 103 * Clone this. 104 * @see java.lang.Object#clone() 105 */ 106 @Override 107 public Residue<C> copy() { 108 return new Residue<C>(ring, val, isunit); 109 } 110 111 112 /** 113 * Is Residue zero. 114 * @return If this is 0 then true is returned, else false. 115 * @see edu.jas.structure.RingElem#isZERO() 116 */ 117 public boolean isZERO() { 118 return val.isZERO(); 119 } 120 121 122 /** 123 * Is Residue one. 124 * @return If this is 1 then true is returned, else false. 125 * @see edu.jas.structure.RingElem#isONE() 126 */ 127 public boolean isONE() { 128 return val.isONE(); 129 } 130 131 132 /** 133 * Is Residue unit. 134 * @return If this is a unit then true is returned, else false. 135 * @see edu.jas.structure.RingElem#isUnit() 136 */ 137 public boolean isUnit() { 138 if (isunit > 0) { 139 return true; 140 } 141 if (isunit == 0) { 142 return false; 143 } 144 // not jet known 145 boolean u = ring.ideal.isUnit(val); 146 if (u) { 147 isunit = 1; 148 } else { 149 isunit = 0; 150 } 151 return (u); 152 } 153 154 155 /** 156 * Is Residue a constant. 157 * @return true if this.val is a constant polynomial, else false. 158 */ 159 public boolean isConstant() { 160 return val.isConstant(); 161 } 162 163 164 /** 165 * Get the String representation as RingElem. 166 * @see java.lang.Object#toString() 167 */ 168 @Override 169 public String toString() { 170 if (PrettyPrint.isTrue()) { 171 return val.toString(ring.ring.getVars()); 172 } 173 return "Residue[ " + val.toString() + " mod " + ring.toString() + " ]"; 174 } 175 176 177 /** 178 * Get a scripting compatible string representation. 179 * @return script compatible representation for this Element. 180 * @see edu.jas.structure.Element#toScript() 181 */ 182 @Override 183 public String toScript() { 184 // Python case 185 return val.toScript(); 186 // return "PolyResidue( " + val.toScript() 187 // + ", " + ring.toScript() + " )"; 188 } 189 190 191 /** 192 * Get a scripting compatible string representation of the factory. 193 * @return script compatible representation for this ElemFactory. 194 * @see edu.jas.structure.Element#toScriptFactory() 195 */ 196 @Override 197 public String toScriptFactory() { 198 // Python case 199 return factory().toScript(); 200 } 201 202 203 /** 204 * Residue comparison. 205 * @param b Residue. 206 * @return sign(this-b), 0 means that this and b are equivalent in this 207 * residue class ring. 208 */ 209 @Override 210 public int compareTo(Residue<C> b) { 211 GenPolynomial<C> v = b.val; 212 if (!ring.equals(b.ring)) { 213 v = ring.ideal.normalform(v); 214 } 215 return val.compareTo(v); 216 } 217 218 219 /** 220 * Comparison with any other object. 221 * @see java.lang.Object#equals(java.lang.Object) 222 * @return true means that this and b are equivalent in this residue class 223 * ring. 224 */ 225 @Override 226 @SuppressWarnings("unchecked") 227 public boolean equals(Object b) { 228 if (!(b instanceof Residue)) { 229 return false; 230 } 231 Residue<C> a = null; 232 try { 233 a = (Residue<C>) b; 234 } catch (ClassCastException e) { 235 } 236 if (a == null) { 237 return false; 238 } 239 return compareTo(a) == 0; 240 } 241 242 243 /** 244 * Hash code for this residue. 245 * @see java.lang.Object#hashCode() 246 */ 247 @Override 248 public int hashCode() { 249 int h; 250 h = ring.hashCode(); 251 h = 37 * h + val.hashCode(); 252 return h; 253 } 254 255 256 /** 257 * Residue absolute value. 258 * @return the absolute value of this. 259 * @see edu.jas.structure.RingElem#abs() 260 */ 261 public Residue<C> abs() { 262 return new Residue<C>(ring, val.abs(), isunit); 263 } 264 265 266 /** 267 * Residue summation. 268 * @param S Residue. 269 * @return this+S. 270 */ 271 public Residue<C> sum(Residue<C> S) { 272 return new Residue<C>(ring, val.sum(S.val)); 273 } 274 275 276 /** 277 * Residue negate. 278 * @return -this. 279 * @see edu.jas.structure.RingElem#negate() 280 */ 281 public Residue<C> negate() { 282 return new Residue<C>(ring, val.negate(), isunit); 283 } 284 285 286 /** 287 * Residue signum. 288 * @see edu.jas.structure.RingElem#signum() 289 * @return signum(this). 290 */ 291 public int signum() { 292 return val.signum(); 293 } 294 295 296 /** 297 * Residue subtraction. 298 * @param S Residue. 299 * @return this-S. 300 */ 301 public Residue<C> subtract(Residue<C> S) { 302 return new Residue<C>(ring, val.subtract(S.val)); 303 } 304 305 306 /** 307 * Residue division. 308 * @param S Residue. 309 * @return this/S. 310 */ 311 public Residue<C> divide(Residue<C> S) { 312 if (ring.isField()) { 313 return multiply(S.inverse()); 314 } 315 GenPolynomial<C> x = PolyUtil.<C> basePseudoDivide(val, S.val); 316 return new Residue<C>(ring, x); 317 } 318 319 320 /** 321 * Residue inverse. 322 * @see edu.jas.structure.RingElem#inverse() 323 * @return S with S = 1/this if defined. 324 */ 325 public Residue<C> inverse() { 326 GenPolynomial<C> x = ring.ideal.inverse(val); 327 return new Residue<C>(ring, x, 1); 328 } 329 330 331 /** 332 * Residue remainder. 333 * @param S Residue. 334 * @return this - (this/S)*S. 335 */ 336 public Residue<C> remainder(Residue<C> S) { 337 //GenPolynomial<C> x = val.remainder( S.val ); 338 GenPolynomial<C> x = PolyUtil.<C> baseSparsePseudoRemainder(val, S.val); 339 return new Residue<C>(ring, x); 340 } 341 342 343 /** 344 * Residue multiplication. 345 * @param S Residue. 346 * @return this*S. 347 */ 348 public Residue<C> multiply(Residue<C> S) { 349 GenPolynomial<C> x = val.multiply(S.val); 350 int i = -1; 351 if (isunit == 1 && S.isunit == 1) { 352 i = 1; 353 } else if (isunit == 0 || S.isunit == 0) { 354 i = 0; 355 } 356 return new Residue<C>(ring, x, i); 357 } 358 359 360 /** 361 * Residue monic. 362 * @return this with monic value part. 363 */ 364 public Residue<C> monic() { 365 return new Residue<C>(ring, val.monic(), isunit); 366 } 367 368 369 /** 370 * Greatest common divisor. 371 * @param b other element. 372 * @return gcd(this,b). 373 */ 374 public Residue<C> gcd(Residue<C> b) { 375 GenPolynomial<C> x = ring.engine.gcd(val, b.val); 376 int i = -1; // gcd might become a unit 377 if (x.isONE()) { 378 i = 1; 379 } else { 380 System.out.println("Residue gcd = " + x); 381 } 382 if (isunit == 1 && b.isunit == 1) { 383 i = 1; 384 } 385 return new Residue<C>(ring, x, i); 386 } 387 388 389 /** 390 * Extended greatest common divisor. <b>Note: </b>Not implemented, throws 391 * UnsupportedOperationException. 392 * @param b other element. 393 * @return [ gcd(this,b), c1, c2 ] with c1*this + c2*b = gcd(this,b). 394 */ 395 public Residue<C>[] egcd(Residue<C> b) { 396 throw new UnsupportedOperationException("egcd not implemented"); 397 } 398}