001/* 002 * $Id$ 003 */ 004 005package edu.jas.poly; 006 007 008import edu.jas.kern.PrettyPrint; 009import edu.jas.structure.GcdRingElem; 010import edu.jas.structure.NotInvertibleException; 011import edu.jas.structure.RingElem; 012 013 014/** 015 * Algebraic number class. Based on GenPolynomial with RingElem interface. 016 * Objects of this class are immutable. 017 * @author Heinz Kredel 018 */ 019 020public class AlgebraicNumber<C extends RingElem<C>> implements GcdRingElem<AlgebraicNumber<C>> { 021 022 023 /** 024 * Ring part of the data structure. 025 */ 026 public final AlgebraicNumberRing<C> ring; 027 028 029 /** 030 * Value part of the element data structure. 031 */ 032 public final GenPolynomial<C> val; 033 034 035 /** 036 * Flag to remember if this algebraic number is a unit. -1 is unknown, 1 is 037 * unit, 0 not a unit. 038 */ 039 protected int isunit = -1; // initially unknown 040 041 042 /** 043 * The constructor creates a AlgebraicNumber object from AlgebraicNumberRing 044 * modul and a GenPolynomial value. 045 * @param r ring AlgebraicNumberRing<C>. 046 * @param a value GenPolynomial<C>. 047 */ 048 public AlgebraicNumber(AlgebraicNumberRing<C> r, GenPolynomial<C> a) { 049 ring = r; // assert r != 0 050 val = a.remainder(ring.modul); //.monic() no go 051 if (val.isZERO()) { 052 isunit = 0; 053 } 054 if (ring.isField()) { 055 isunit = 1; 056 } 057 } 058 059 060 /** 061 * The constructor creates a AlgebraicNumber object from a GenPolynomial 062 * object module. 063 * @param r ring AlgebraicNumberRing<C>. 064 */ 065 public AlgebraicNumber(AlgebraicNumberRing<C> r) { 066 this(r, r.ring.getZERO()); 067 } 068 069 070 /** 071 * Get the value part. 072 * @return val. 073 */ 074 public GenPolynomial<C> getVal() { 075 return val; 076 } 077 078 079 /** 080 * Get the corresponding element factory. 081 * @return factory for this Element. 082 * @see edu.jas.structure.Element#factory() 083 */ 084 public AlgebraicNumberRing<C> factory() { 085 return ring; 086 } 087 088 089 /** 090 * Copy this. 091 * @see edu.jas.structure.Element#copy() 092 */ 093 @Override 094 public AlgebraicNumber<C> copy() { 095 return new AlgebraicNumber<C>(ring, val); 096 } 097 098 099 /** 100 * Is AlgebraicNumber zero. 101 * @return If this is 0 then true is returned, else false. 102 * @see edu.jas.structure.RingElem#isZERO() 103 */ 104 public boolean isZERO() { 105 return val.equals(ring.ring.getZERO()); 106 } 107 108 109 /** 110 * Is AlgebraicNumber one. 111 * @return If this is 1 then true is returned, else false. 112 * @see edu.jas.structure.RingElem#isONE() 113 */ 114 public boolean isONE() { 115 return val.equals(ring.ring.getONE()); 116 } 117 118 119 /** 120 * Is AlgebraicNumber unit. 121 * @return If this is a unit then true is returned, else false. 122 * @see edu.jas.structure.RingElem#isUnit() 123 */ 124 public boolean isUnit() { 125 if (isunit > 0) { 126 return true; 127 } 128 if (isunit == 0) { 129 return false; 130 } 131 // not jet known 132 if (val.isZERO()) { 133 isunit = 0; 134 return false; 135 } 136 if (ring.isField()) { 137 isunit = 1; 138 return true; 139 } 140 boolean u = val.gcd(ring.modul).isUnit(); 141 if (u) { 142 isunit = 1; 143 } else { 144 isunit = 0; 145 } 146 return u; 147 } 148 149 150 /** 151 * Is AlgebraicNumber a root of unity. 152 * @return true if |this**i| == 1, for some 0 < i ≤ deg(modul), else 153 * false. 154 */ 155 public boolean isRootOfUnity() { 156 long d = ring.modul.degree(); 157 AlgebraicNumber<C> t = ring.getONE(); 158 for (long i = 1; i <= d; i++) { 159 t = t.multiply(this); 160 if (t.abs().isONE()) { 161 //System.out.println("isRootOfUnity for i = " + i); 162 return true; 163 } 164 } 165 return false; 166 } 167 168 169 /** 170 * Get the String representation as RingElem. 171 * @see java.lang.Object#toString() 172 */ 173 @Override 174 public String toString() { 175 if (PrettyPrint.isTrue()) { 176 return val.toString(ring.ring.vars); 177 } 178 return "AlgebraicNumber[ " + val.toString() + " ]"; 179 } 180 181 182 /** 183 * Get a scripting compatible string representation. 184 * @return script compatible representation for this Element. 185 * @see edu.jas.structure.Element#toScript() 186 */ 187 @Override 188 public String toScript() { 189 // Python case 190 return val.toScript(); 191 } 192 193 194 /** 195 * Get a scripting compatible string representation of the factory. 196 * @return script compatible representation for this ElemFactory. 197 * @see edu.jas.structure.Element#toScriptFactory() 198 */ 199 @Override 200 public String toScriptFactory() { 201 // Python case 202 return factory().toScript(); 203 } 204 205 206 /** 207 * AlgebraicNumber comparison. 208 * @param b AlgebraicNumber. 209 * @return sign(this-b). 210 */ 211 @Override 212 public int compareTo(AlgebraicNumber<C> b) { 213 int s = 0; 214 if (ring.modul != b.ring.modul) { // avoid compareTo if possible 215 s = ring.modul.compareTo(b.ring.modul); 216 } 217 if (s != 0) { 218 return s; 219 } 220 return val.compareTo(b.val); 221 } 222 223 224 /** 225 * Comparison with any other object. 226 * @see java.lang.Object#equals(java.lang.Object) 227 */ 228 @Override 229 @SuppressWarnings("unchecked") 230 public boolean equals(Object b) { 231 if (b == null) { 232 return false; 233 } 234 if (!(b instanceof AlgebraicNumber)) { 235 return false; 236 } 237 AlgebraicNumber<C> a = (AlgebraicNumber<C>) b; 238 if (!ring.equals(a.ring)) { 239 return false; 240 } 241 return (0 == compareTo(a)); 242 } 243 244 245 /** 246 * Hash code for this AlgebraicNumber. 247 * @see java.lang.Object#hashCode() 248 */ 249 @Override 250 public int hashCode() { 251 return 37 * val.hashCode() + ring.hashCode(); 252 } 253 254 255 /** 256 * AlgebraicNumber absolute value. 257 * @return the absolute value of this. 258 * @see edu.jas.structure.RingElem#abs() 259 */ 260 public AlgebraicNumber<C> abs() { 261 return new AlgebraicNumber<C>(ring, val.abs()); 262 } 263 264 265 /** 266 * AlgebraicNumber summation. 267 * @param S AlgebraicNumber. 268 * @return this+S. 269 */ 270 public AlgebraicNumber<C> sum(AlgebraicNumber<C> S) { 271 return new AlgebraicNumber<C>(ring, val.sum(S.val)); 272 } 273 274 275 /** 276 * AlgebraicNumber summation. 277 * @param c coefficient. 278 * @return this+c. 279 */ 280 public AlgebraicNumber<C> sum(GenPolynomial<C> c) { 281 return new AlgebraicNumber<C>(ring, val.sum(c)); 282 } 283 284 285 /** 286 * AlgebraicNumber summation. 287 * @param c polynomial. 288 * @return this+c. 289 */ 290 public AlgebraicNumber<C> sum(C c) { 291 return new AlgebraicNumber<C>(ring, val.sum(c)); 292 } 293 294 295 /** 296 * AlgebraicNumber negate. 297 * @return -this. 298 * @see edu.jas.structure.RingElem#negate() 299 */ 300 public AlgebraicNumber<C> negate() { 301 return new AlgebraicNumber<C>(ring, val.negate()); 302 } 303 304 305 /** 306 * AlgebraicNumber signum. 307 * @see edu.jas.structure.RingElem#signum() 308 * @return signum(this). 309 */ 310 public int signum() { 311 return val.signum(); 312 } 313 314 315 /** 316 * AlgebraicNumber subtraction. 317 * @param S AlgebraicNumber. 318 * @return this-S. 319 */ 320 public AlgebraicNumber<C> subtract(AlgebraicNumber<C> S) { 321 return new AlgebraicNumber<C>(ring, val.subtract(S.val)); 322 } 323 324 325 /** 326 * AlgebraicNumber division. 327 * @param S AlgebraicNumber. 328 * @return this/S. 329 */ 330 public AlgebraicNumber<C> divide(AlgebraicNumber<C> S) { 331 return multiply(S.inverse()); 332 } 333 334 335 /** 336 * AlgebraicNumber inverse. 337 * @see edu.jas.structure.RingElem#inverse() 338 * @throws NotInvertibleException if the element is not invertible. 339 * @return S with S = 1/this if defined. 340 */ 341 public AlgebraicNumber<C> inverse() { 342 try { 343 return new AlgebraicNumber<C>(ring, val.modInverse(ring.modul)); 344 } catch (AlgebraicNotInvertibleException e) { 345 //System.out.println(e); 346 throw e; 347 } catch (NotInvertibleException e) { 348 throw new AlgebraicNotInvertibleException(e + ", val = " + val + ", modul = " + ring.modul 349 + ", gcd = " + val.gcd(ring.modul), e); 350 } 351 } 352 353 354 /** 355 * AlgebraicNumber remainder. 356 * @param S AlgebraicNumber. 357 * @return this - (this/S)*S. 358 */ 359 public AlgebraicNumber<C> remainder(AlgebraicNumber<C> S) { 360 if (S == null || S.isZERO()) { 361 throw new ArithmeticException("division by zero"); 362 } 363 if (S.isONE()) { 364 return ring.getZERO(); 365 } 366 if (S.isUnit()) { 367 return ring.getZERO(); 368 } 369 GenPolynomial<C> x = val.remainder(S.val); 370 return new AlgebraicNumber<C>(ring, x); 371 } 372 373 374 /** 375 * Quotient and remainder by division of this by S. 376 * @param S a AlgebraicNumber 377 * @return [this/S, this - (this/S)*S]. 378 */ 379 @SuppressWarnings("unchecked") 380 public AlgebraicNumber<C>[] quotientRemainder(AlgebraicNumber<C> S) { 381 return new AlgebraicNumber[] { divide(S), remainder(S) }; 382 } 383 384 385 /** 386 * AlgebraicNumber multiplication. 387 * @param S AlgebraicNumber. 388 * @return this*S. 389 */ 390 public AlgebraicNumber<C> multiply(AlgebraicNumber<C> S) { 391 GenPolynomial<C> x = val.multiply(S.val); 392 return new AlgebraicNumber<C>(ring, x); 393 } 394 395 396 /** 397 * AlgebraicNumber multiplication. 398 * @param c coefficient. 399 * @return this*c. 400 */ 401 public AlgebraicNumber<C> multiply(C c) { 402 GenPolynomial<C> x = val.multiply(c); 403 return new AlgebraicNumber<C>(ring, x); 404 } 405 406 407 /** 408 * AlgebraicNumber multiplication. 409 * @param c polynomial. 410 * @return this*c. 411 */ 412 public AlgebraicNumber<C> multiply(GenPolynomial<C> c) { 413 GenPolynomial<C> x = val.multiply(c); 414 return new AlgebraicNumber<C>(ring, x); 415 } 416 417 418 /** 419 * AlgebraicNumber monic. 420 * @return this with monic value part. 421 */ 422 public AlgebraicNumber<C> monic() { 423 return new AlgebraicNumber<C>(ring, val.monic()); 424 } 425 426 427 /** 428 * AlgebraicNumber greatest common divisor. 429 * @param S AlgebraicNumber. 430 * @return gcd(this,S). 431 */ 432 public AlgebraicNumber<C> gcd(AlgebraicNumber<C> S) { 433 if (S.isZERO()) { 434 return this; 435 } 436 if (isZERO()) { 437 return S; 438 } 439 if (isUnit() || S.isUnit()) { 440 return ring.getONE(); 441 } 442 return new AlgebraicNumber<C>(ring, val.gcd(S.val)); 443 } 444 445 446 /** 447 * AlgebraicNumber extended greatest common divisor. 448 * @param S AlgebraicNumber. 449 * @return [ gcd(this,S), a, b ] with a*this + b*S = gcd(this,S). 450 */ 451 @SuppressWarnings("unchecked") 452 public AlgebraicNumber<C>[] egcd(AlgebraicNumber<C> S) { 453 AlgebraicNumber<C>[] ret = new AlgebraicNumber[3]; 454 ret[0] = null; 455 ret[1] = null; 456 ret[2] = null; 457 if (S == null || S.isZERO()) { 458 ret[0] = this; 459 return ret; 460 } 461 if (isZERO()) { 462 ret[0] = S; 463 return ret; 464 } 465 if (this.isUnit() || S.isUnit()) { 466 ret[0] = ring.getONE(); 467 if (this.isUnit() && S.isUnit()) { 468 AlgebraicNumber<C> half = ring.fromInteger(2).inverse(); 469 ret[1] = this.inverse().multiply(half); 470 ret[2] = S.inverse().multiply(half); 471 return ret; 472 } 473 if (this.isUnit()) { 474 // oder inverse(S-1)? 475 ret[1] = this.inverse(); 476 ret[2] = ring.getZERO(); 477 return ret; 478 } 479 // if ( S.isUnit() ) { 480 // oder inverse(this-1)? 481 ret[1] = ring.getZERO(); 482 ret[2] = S.inverse(); 483 return ret; 484 //} 485 } 486 //System.out.println("this = " + this + ", S = " + S); 487 GenPolynomial<C>[] qr; 488 GenPolynomial<C> q = this.val; 489 GenPolynomial<C> r = S.val; 490 GenPolynomial<C> c1 = ring.ring.getONE(); 491 GenPolynomial<C> d1 = ring.ring.getZERO(); 492 GenPolynomial<C> c2 = ring.ring.getZERO(); 493 GenPolynomial<C> d2 = ring.ring.getONE(); 494 GenPolynomial<C> x1; 495 GenPolynomial<C> x2; 496 while (!r.isZERO()) { 497 qr = q.quotientRemainder(r); 498 q = qr[0]; 499 x1 = c1.subtract(q.multiply(d1)); 500 x2 = c2.subtract(q.multiply(d2)); 501 c1 = d1; 502 c2 = d2; 503 d1 = x1; 504 d2 = x2; 505 q = r; 506 r = qr[1]; 507 } 508 //System.out.println("q = " + q + "\n c1 = " + c1 + "\n c2 = " + c2); 509 ret[0] = new AlgebraicNumber<C>(ring, q); 510 ret[1] = new AlgebraicNumber<C>(ring, c1); 511 ret[2] = new AlgebraicNumber<C>(ring, c2); 512 return ret; 513 } 514 515}