001 /*
002 * $Id: BigInteger.java 1663 2008-02-05 17:32:07Z kredel $
003 */
004
005 package edu.jas.arith;
006
007 import java.util.Random;
008 import java.io.Reader;
009
010 //import edu.jas.structure.RingElem;
011 import edu.jas.structure.GcdRingElem;
012 import edu.jas.structure.RingFactory;
013
014 import edu.jas.util.StringUtil;
015
016
017 /**
018 * BigInteger class to make java.math.BigInteger available with RingElem
019 * interface and with the familiar SAC static method names.
020 * Objects of this class are immutable.
021 * @author Heinz Kredel
022 * @see java.math.BigInteger
023 */
024
025 public final class BigInteger implements GcdRingElem<BigInteger>,
026 RingFactory<BigInteger> {
027
028 /** The data structure.
029 */
030 protected final java.math.BigInteger val;
031
032
033 private final static Random random = new Random();
034
035
036 /** The constant 0.
037 */
038 public final static BigInteger ZERO
039 = new BigInteger( java.math.BigInteger.ZERO );
040
041
042 /** The constant 1.
043 */
044 public final static BigInteger ONE
045 = new BigInteger( java.math.BigInteger.ONE );
046
047
048 /**
049 * Constructor for BigInteger from math.BigInteger.
050 * @param a java.math.BigInteger.
051 */
052 public BigInteger(java.math.BigInteger a) {
053 val = a;
054 }
055
056
057 /**
058 * Constructor for BigInteger from long.
059 * @param a long.
060 */
061 public BigInteger(long a) {
062 val = new java.math.BigInteger( String.valueOf(a) );
063 }
064
065
066 /**
067 * Constructor for BigInteger from String.
068 * @param s String.
069 */
070 public BigInteger(String s) {
071 val = new java.math.BigInteger( s.trim() );
072 }
073
074
075 /**
076 * Constructor for BigInteger without parameters.
077 */
078 public BigInteger() {
079 val = java.math.BigInteger.ZERO;
080 }
081
082
083 /** Get the value.
084 * @return val java.math.BigInteger.
085 */
086 public java.math.BigInteger getVal() {
087 return val;
088 }
089
090
091 /** Clone this.
092 * @see java.lang.Object#clone()
093 */
094 @Override
095 public BigInteger clone() {
096 return new BigInteger( val );
097 }
098
099
100 /** Copy BigInteger element c.
101 * @param c BigInteger.
102 * @return a copy of c.
103 */
104 public BigInteger copy(BigInteger c) {
105 return new BigInteger( c.val );
106 }
107
108
109 /** Get the zero element.
110 * @return 0.
111 */
112 public BigInteger getZERO() {
113 return ZERO;
114 }
115
116
117 /** Get the one element.
118 * @return 1.
119 */
120 public BigInteger getONE() {
121 return ONE;
122 }
123
124
125 /**
126 * Query if this ring is commutative.
127 * @return true.
128 */
129 public boolean isCommutative() {
130 return true;
131 }
132
133
134 /**
135 * Query if this ring is associative.
136 * @return true.
137 */
138 public boolean isAssociative() {
139 return true;
140 }
141
142
143 /**
144 * Query if this ring is a field.
145 * @return true.
146 */
147 public boolean isField() {
148 return false;
149 }
150
151
152 /**
153 * Characteristic of this ring.
154 * @return characteristic of this ring.
155 */
156 public java.math.BigInteger characteristic() {
157 return java.math.BigInteger.ZERO;
158 }
159
160
161 /** Get a BigInteger element from a math.BigInteger.
162 * @param a math.BigInteger.
163 * @return a as BigInteger.
164 */
165 public BigInteger fromInteger(java.math.BigInteger a) {
166 return new BigInteger(a);
167 }
168
169
170 /** Get a BigInteger element from a math.BigInteger.
171 * @param a math.BigInteger.
172 * @return a as BigInteger.
173 */
174 public static BigInteger valueOf(java.math.BigInteger a) {
175 return new BigInteger(a);
176 }
177
178
179 /** Get a BigInteger element from long.
180 * @param a long.
181 * @return a as BigInteger.
182 */
183 public BigInteger fromInteger(long a) {
184 return new BigInteger(a);
185 }
186
187
188 /** Get a BigInteger element from long.
189 * @param a long.
190 * @return a as BigInteger.
191 */
192 public static BigInteger valueOf(long a) {
193 return new BigInteger(a);
194 }
195
196
197 /** Is BigInteger number zero.
198 * @return If this is 0 then true is returned, else false.
199 * @see edu.jas.structure.RingElem#isZERO()
200 */
201 public boolean isZERO() {
202 return val.equals( java.math.BigInteger.ZERO );
203 }
204
205
206 /** Is BigInteger number one.
207 * @see edu.jas.structure.RingElem#isONE()
208 */
209 public boolean isONE() {
210 return val.equals( java.math.BigInteger.ONE );
211 }
212
213
214 /** Is BigInteger number unit.
215 * @see edu.jas.structure.RingElem#isUnit()
216 */
217 public boolean isUnit() {
218 return ( this.isONE() || this.negate().isONE() );
219 }
220
221 /** Get the String representation.
222 * @see java.lang.Object#toString()
223 */
224 @Override
225 public String toString() {
226 return val.toString();
227 }
228
229
230 /** Compare to BigInteger b.
231 * @param b BigInteger.
232 * @return 0 if this == b,
233 1 if this > b,
234 -1 if this < b.
235 */
236 public int compareTo(BigInteger b) {
237 return val.compareTo( b.val );
238 }
239
240
241 /** Integer comparison.
242 * @param A BigInteger.
243 * @param B BigInteger.
244 * @return 0 if A == B, 1 if A > B, -1 if A < B.
245 */
246 public static int ICOMP(BigInteger A, BigInteger B) {
247 if ( A == null ) return -B.signum();
248 return A.compareTo(B);
249 }
250
251
252 /** Comparison with any other object.
253 * @see java.lang.Object#equals(java.lang.Object)
254 */
255 @Override
256 public boolean equals(Object b) {
257 if ( ! ( b instanceof BigInteger ) ) {
258 return false;
259 }
260 BigInteger bi = (BigInteger)b;
261 return val.equals( bi.val );
262 }
263
264
265 /** Hash code for this BigInteger.
266 * @see java.lang.Object#hashCode()
267 */
268 @Override
269 public int hashCode() {
270 return val.hashCode();
271 }
272
273
274 /** Absolute value of this.
275 * @see edu.jas.structure.RingElem#abs()
276 */
277 public BigInteger abs() {
278 return new BigInteger( val.abs() );
279 }
280
281
282 /** Absolute value.
283 * @param A BigInteger.
284 * @return abs(A).
285 */
286 public static BigInteger IABS(BigInteger A) {
287 if ( A == null ) return null;
288 return A.abs();
289 }
290
291
292 /* Negative value of this.
293 * @see edu.jas.structure.RingElem#negate()
294 */
295 public BigInteger negate() {
296 return new BigInteger( val.negate() );
297 }
298
299
300 /** Negative value.
301 * @param A BigInteger.
302 * @return -A.
303 */
304 public static BigInteger INEG(BigInteger A) {
305 if ( A == null ) return null;
306 return A.negate();
307 }
308
309
310 /** signum.
311 * @see edu.jas.structure.RingElem#signum()
312 */
313 public int signum() {
314 return val.signum();
315 }
316
317
318 /** Integer signum.
319 * @param A BigInteger.
320 * @return signum(A).
321 */
322 public static int ISIGN(BigInteger A) {
323 if ( A == null ) return 0;
324 return A.signum();
325 }
326
327
328 /** BigInteger subtract.
329 * @param S BigInteger.
330 * @return this-S.
331 */
332 public BigInteger subtract(BigInteger S) {
333 return new BigInteger( val.subtract( S.val ) );
334 }
335
336 /** BigInteger subtract.
337 * @param A BigInteger.
338 * @param B BigInteger.
339 * @return A-B.
340 */
341 public static BigInteger IDIF(BigInteger A, BigInteger B) {
342 if ( A == null ) return B.negate();
343 return A.subtract(B);
344 }
345
346
347 /** BigInteger divide.
348 * @param S BigInteger.
349 * @return this/S.
350 */
351 public BigInteger divide(BigInteger S) {
352 return new BigInteger( val.divide( S.val ) );
353 }
354
355 /** BigInteger divide.
356 * @param A BigInteger.
357 * @param B BigInteger.
358 * @return A/B.
359 */
360 public static BigInteger IQ(BigInteger A, BigInteger B) {
361 if ( A == null ) return null;
362 return A.divide(B);
363 }
364
365
366 /** Integer inverse. R is a non-zero integer.
367 S=1/R if defined else 0.
368 * @see edu.jas.structure.RingElem#inverse()
369 */
370 public BigInteger inverse() {
371 if ( this.isONE() || this.negate().isONE() ) {
372 return this;
373 }
374 return ZERO;
375 }
376
377
378 /** BigInteger remainder.
379 * @param S BigInteger.
380 * @return this - (this/S)*S.
381 */
382 public BigInteger remainder(BigInteger S) {
383 return new BigInteger( val.remainder( S.val ) );
384 }
385
386
387 /** BigInteger remainder.
388 * @param A BigInteger.
389 * @param B BigInteger.
390 * @return A - (A/B)*B.
391 */
392 public static BigInteger IREM(BigInteger A, BigInteger B) {
393 if ( A == null ) return null;
394 return A.remainder(B);
395 }
396
397
398 /** BigInteger compute quotient and remainder.
399 * @param S BigInteger.
400 * @return BigInteger[] { q, r } with q = this/S and r = rem(this,S).
401 */
402 public BigInteger[] divideAndRemainder(BigInteger S) {
403 BigInteger[] qr = new BigInteger[2];
404 java.math.BigInteger[] C = val.divideAndRemainder( S.val );
405 qr[0] = new BigInteger( C[0] );
406 qr[1] = new BigInteger( C[1] );
407 return qr;
408 }
409
410
411 /**
412 Integer quotient and remainder. A and B are integers, B ne 0. Q is
413 the quotient, integral part of A/B, and R is the remainder A-B*Q.
414 * @param A BigInteger.
415 * @param B BigInteger.
416 * @return BigInteger[] { q, r } with q = A/B and r = rem(A,B).
417 */
418 public static BigInteger[] IQR(BigInteger A, BigInteger B) {
419 if ( A == null ) return null;
420 return A.divideAndRemainder(B);
421 }
422
423
424 /** BigInteger greatest common divisor.
425 * @param S BigInteger.
426 * @return gcd(this,S).
427 */
428 public BigInteger gcd(BigInteger S) {
429 return new BigInteger( val.gcd( S.val ) );
430 }
431
432
433 /**
434 * BigInteger extended greatest common divisor.
435 * @param S BigInteger.
436 * @return [ gcd(this,S), a, b ] with a*this + b*S = gcd(this,S).
437 */
438 public BigInteger[] egcd(BigInteger S) {
439 BigInteger[] ret = new BigInteger[3];
440 ret[0] = null;
441 ret[1] = null;
442 ret[2] = null;
443 if ( S == null || S.isZERO() ) {
444 ret[0] = this;
445 return ret;
446 }
447 if ( this.isZERO() ) {
448 ret[0] = S;
449 return ret;
450 }
451 //System.out.println("this = " + this + ", S = " + S);
452 BigInteger[] qr;
453 BigInteger q = this;
454 BigInteger r = S;
455 BigInteger c1 = ONE;
456 BigInteger d1 = ZERO;
457 BigInteger c2 = ZERO;
458 BigInteger d2 = ONE;
459 BigInteger x1;
460 BigInteger x2;
461 while ( !r.isZERO() ) {
462 qr = q.divideAndRemainder(r);
463 q = qr[0];
464 x1 = c1.subtract( q.multiply(d1) );
465 x2 = c2.subtract( q.multiply(d2) );
466 c1 = d1; c2 = d2;
467 d1 = x1; d2 = x2;
468 q = r;
469 r = qr[1];
470 }
471 //System.out.println("q = " + q + "\n c1 = " + c1 + "\n c2 = " + c2);
472 if ( q.signum() < 0 ) {
473 q = q.negate();
474 c1 = c1.negate();
475 c2 = c2.negate();
476 }
477 ret[0] = q;
478 ret[1] = c1;
479 ret[2] = c2;
480 return ret;
481 }
482
483
484 /** BigInteger greatest common divisor.
485 * @param A BigInteger.
486 * @param B BigInteger.
487 * @return gcd(A,B).
488 */
489 public static BigInteger IGCD(BigInteger A, BigInteger B) {
490 if ( A == null ) return null;
491 return A.gcd(B);
492 }
493
494
495 /** BigInteger random.
496 * @param n such that 0 ≤ r ≤ (2<sup>n</sup>-1).
497 * @return r, a random BigInteger.
498 */
499 public BigInteger random(int n) {
500 return random(n,random);
501 }
502
503
504 /** BigInteger random.
505 * @param n such that 0 ≤ r ≤ (2<sup>n</sup>-1).
506 * @param rnd is a source for random bits.
507 * @return r, a random BigInteger.
508 */
509 public BigInteger random(int n, Random rnd) {
510 java.math.BigInteger r = new java.math.BigInteger( n, rnd );
511 if ( rnd.nextBoolean() ) {
512 r = r.negate();
513 }
514 return new BigInteger( r );
515 }
516
517
518 /** BigInteger random.
519 * @param NL such that 0 ≤ r ≤ (2<sup>n</sup>-1).
520 * @return r, a random BigInteger.
521 */
522 public static BigInteger IRAND(int NL) {
523 return ONE.random(NL,random);
524 }
525
526
527 /** BigInteger multiply.
528 * @param S BigInteger.
529 * @return this*S.
530 */
531 public BigInteger multiply(BigInteger S) {
532 return new BigInteger( val.multiply( S.val ) );
533 }
534
535
536 /** BigInteger multiply.
537 * @param A BigInteger.
538 * @param B BigInteger.
539 * @return A*B.
540 */
541 public static BigInteger IPROD(BigInteger A, BigInteger B) {
542 if ( A == null ) return null;
543 return A.multiply(B);
544 }
545
546
547 /** BigInteger summation.
548 * @param S BigInteger.
549 * @return this+S.
550 */
551 public BigInteger sum(BigInteger S) {
552 return new BigInteger( val.add( S.val ) );
553 }
554
555
556 /** BigInteger addition.
557 * @param A BigInteger.
558 * @param B BigInteger.
559 * @return A+B.
560 */
561 public static BigInteger ISUM(BigInteger A, BigInteger B) {
562 if ( A == null ) return null;
563 return A.sum(B);
564 }
565
566
567 /** BigInteger parse from String.
568 * @param s String.
569 * @return Biginteger from s.
570 */
571 public BigInteger parse(String s) {
572 return new BigInteger(s);
573 }
574
575
576 /** BigInteger parse from Reader.
577 * @param r Reader.
578 * @return next Biginteger from r.
579 */
580 public BigInteger parse(Reader r) {
581 return parse( StringUtil.nextString(r) );
582 }
583
584 }