001/* 002 * $Id: Residue.java 4125 2012-08-19 19:05:22Z 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 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 ring factory. 054 * @param a polynomial list. 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 ring factory. 065 * @param a polynomial list. 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 ( val.isUnit() ) { 080 isunit = 1; 081 //} else { // not possible 082 //isunit = 0; 083 } 084 isunit = -1; 085 } 086 087 088 /** 089 * Get the corresponding element factory. 090 * @return factory for this Element. 091 * @see edu.jas.structure.Element#factory() 092 */ 093 public ResidueRing<C> factory() { 094 return ring; 095 } 096 097 098 /** 099 * Clone this. 100 * @see java.lang.Object#clone() 101 */ 102 @Override 103 public Residue<C> copy() { 104 return new Residue<C>(ring, val, isunit); 105 } 106 107 108 /** 109 * Is Residue zero. 110 * @return If this is 0 then true is returned, else false. 111 * @see edu.jas.structure.RingElem#isZERO() 112 */ 113 public boolean isZERO() { 114 // ??return val.equals( ring.ring.getZERO() ); 115 return val.isZERO(); 116 } 117 118 119 /** 120 * Is Residue one. 121 * @return If this is 1 then true is returned, else false. 122 * @see edu.jas.structure.RingElem#isONE() 123 */ 124 public boolean isONE() { 125 // ?? return val.equals( ring.ring.getONE() ); 126 return val.isONE(); 127 } 128 129 130 /** 131 * Is Residue unit. 132 * @return If this is a unit then true is returned, else false. 133 * @see edu.jas.structure.RingElem#isUnit() 134 */ 135 public boolean isUnit() { 136 if (isunit > 0) { 137 return true; 138 } 139 if (isunit == 0) { 140 return false; 141 } 142 // not jet known 143 boolean u = ring.ideal.isUnit(val); 144 if (u) { 145 isunit = 1; 146 } else { 147 isunit = 0; 148 } 149 return (u); 150 } 151 152 153 /** 154 * Is Residue a constant. 155 * @return true if this.val is a constant polynomial, else false. 156 */ 157 public boolean isConstant() { 158 return val.isConstant(); 159 } 160 161 162 /** 163 * Get the String representation as RingElem. 164 * @see java.lang.Object#toString() 165 */ 166 @Override 167 public String toString() { 168 if (PrettyPrint.isTrue()) { 169 return val.toString(ring.ring.getVars()); 170 } 171 return "Residue[ " + val.toString() + " mod " + ring.toString() + " ]"; 172 } 173 174 175 /** 176 * Get a scripting compatible string representation. 177 * @return script compatible representation for this Element. 178 * @see edu.jas.structure.Element#toScript() 179 */ 180 //JAVA6only: @Override 181 public String toScript() { 182 // Python case 183 return val.toScript(); 184 // return "PolyResidue( " + val.toScript() 185 // + ", " + ring.toScript() + " )"; 186 } 187 188 189 /** 190 * Get a scripting compatible string representation of the factory. 191 * @return script compatible representation for this ElemFactory. 192 * @see edu.jas.structure.Element#toScriptFactory() 193 */ 194 //JAVA6only: @Override 195 public String toScriptFactory() { 196 // Python case 197 return factory().toScript(); 198 } 199 200 201 /** 202 * Residue comparison. 203 * @param b Residue. 204 * @return sign(this-b), 0 means that this and b are equivalent in this 205 * residue class ring. 206 */ 207 //JAVA6only: @Override 208 public int compareTo(Residue<C> b) { 209 GenPolynomial<C> v = b.val; 210 if (!ring.equals(b.ring)) { 211 v = ring.ideal.normalform(v); 212 } 213 return val.compareTo(v); 214 } 215 216 217 /** 218 * Comparison with any other object. 219 * @see java.lang.Object#equals(java.lang.Object) 220 * @return true means that this and b are equivalent in this residue class 221 * ring. 222 */ 223 @Override 224 @SuppressWarnings("unchecked") 225 public boolean equals(Object b) { 226 if (!(b instanceof Residue)) { 227 return false; 228 } 229 Residue<C> a = null; 230 try { 231 a = (Residue<C>) b; 232 } catch (ClassCastException e) { 233 } 234 if (a == null) { 235 return false; 236 } 237 return (0 == compareTo(a)); 238 } 239 240 241 /** 242 * Hash code for this local. 243 * @see java.lang.Object#hashCode() 244 */ 245 @Override 246 public int hashCode() { 247 int h; 248 h = ring.hashCode(); 249 h = 37 * h + val.hashCode(); 250 return h; 251 } 252 253 254 /** 255 * Residue absolute value. 256 * @return the absolute value of this. 257 * @see edu.jas.structure.RingElem#abs() 258 */ 259 public Residue<C> abs() { 260 return new Residue<C>(ring, val.abs(), isunit); 261 } 262 263 264 /** 265 * Residue summation. 266 * @param S Residue. 267 * @return this+S. 268 */ 269 public Residue<C> sum(Residue<C> S) { 270 return new Residue<C>(ring, val.sum(S.val)); 271 } 272 273 274 /** 275 * Residue negate. 276 * @return -this. 277 * @see edu.jas.structure.RingElem#negate() 278 */ 279 public Residue<C> negate() { 280 return new Residue<C>(ring, val.negate(), isunit); 281 } 282 283 284 /** 285 * Residue signum. 286 * @see edu.jas.structure.RingElem#signum() 287 * @return signum(this). 288 */ 289 public int signum() { 290 return val.signum(); 291 } 292 293 294 /** 295 * Residue subtraction. 296 * @param S Residue. 297 * @return this-S. 298 */ 299 public Residue<C> subtract(Residue<C> S) { 300 return new Residue<C>(ring, val.subtract(S.val)); 301 } 302 303 304 /** 305 * Residue division. 306 * @param S Residue. 307 * @return this/S. 308 */ 309 public Residue<C> divide(Residue<C> S) { 310 if (ring.isField()) { 311 return multiply(S.inverse()); 312 } 313 GenPolynomial<C> x = PolyUtil.<C> basePseudoDivide(val, S.val); 314 return new Residue<C>(ring, x); 315 } 316 317 318 /** 319 * Residue inverse. 320 * @see edu.jas.structure.RingElem#inverse() 321 * @return S with S = 1/this if defined. 322 */ 323 public Residue<C> inverse() { 324 GenPolynomial<C> x = ring.ideal.inverse(val); 325 return new Residue<C>(ring, x, 1); 326 } 327 328 329 /** 330 * Residue remainder. 331 * @param S Residue. 332 * @return this - (this/S)*S. 333 */ 334 public Residue<C> remainder(Residue<C> S) { 335 //GenPolynomial<C> x = val.remainder( S.val ); 336 GenPolynomial<C> x = PolyUtil.<C> baseSparsePseudoRemainder(val, S.val); 337 return new Residue<C>(ring, x); 338 } 339 340 341 /** 342 * Residue multiplication. 343 * @param S Residue. 344 * @return this*S. 345 */ 346 public Residue<C> multiply(Residue<C> S) { 347 GenPolynomial<C> x = val.multiply(S.val); 348 int i = -1; 349 if (isunit == 1 && S.isunit == 1) { 350 i = 1; 351 } else if (isunit == 0 || S.isunit == 0) { 352 i = 0; 353 } 354 return new Residue<C>(ring, x, i); 355 } 356 357 358 /** 359 * Residue monic. 360 * @return this with monic value part. 361 */ 362 public Residue<C> monic() { 363 return new Residue<C>(ring, val.monic(), isunit); 364 } 365 366 367 /** 368 * Greatest common divisor. 369 * @param b other element. 370 * @return gcd(this,b). 371 */ 372 public Residue<C> gcd(Residue<C> b) { 373 GenPolynomial<C> x = ring.engine.gcd(val, b.val); 374 int i = -1; // gcd might become a unit 375 if (x.isONE()) { 376 i = 1; 377 } else { 378 System.out.println("Residue gcd = " + x); 379 } 380 if (isunit == 1 && b.isunit == 1) { 381 i = 1; 382 } 383 return new Residue<C>(ring, x, i); 384 } 385 386 387 /** 388 * Extended greatest common divisor. <b>Note: </b>Not implemented, throws 389 * UnsupportedOperationException. 390 * @param b other element. 391 * @return [ gcd(this,b), c1, c2 ] with c1*this + c2*b = gcd(this,b). 392 */ 393 public Residue<C>[] egcd(Residue<C> b) { 394 throw new UnsupportedOperationException("egcd not implemented " + this.getClass().getName()); 395 } 396}