0001: /*
0002: * JScience - Java(TM) Tools and Libraries for the Advancement of Sciences.
0003: * Copyright (C) 2006 - JScience (http://jscience.org/)
0004: * All rights reserved.
0005: *
0006: * Permission to use, copy, modify, and distribute this software is
0007: * freely granted, provided that this notice is preserved.
0008: */
0009: package org.jscience.mathematics.number;
0010:
0011: import java.io.IOException;
0012:
0013: import javolution.context.ArrayFactory;
0014: import javolution.context.ConcurrentContext;
0015: import javolution.context.ObjectFactory;
0016: import javolution.context.StackContext;
0017: import javolution.lang.Configurable;
0018: import javolution.lang.MathLib;
0019: import javolution.text.Text;
0020: import javolution.text.TextBuilder;
0021: import javolution.text.TextFormat;
0022: import javolution.text.TypeFormat;
0023: import javolution.text.TextFormat.Cursor;
0024: import javolution.xml.XMLFormat;
0025: import javolution.xml.stream.XMLStreamException;
0026: import static org.jscience.mathematics.number.Calculus.*;
0027:
0028: /**
0029: * <p> This class represents an immutable integer number of arbitrary size.</p>
0030: *
0031: * <p> It has the following advantages over the
0032: * <code>java.math.BigInteger</code> class:
0033: * <ul>
0034: * <li> Optimized for 64 bits architectures. But still runs significantly
0035: * faster on 32 bits processors.</li>
0036: * <li> Real-time compliant for improved performance and predictability
0037: * (no garbage generated when executing in
0038: * {@link javolution.context.StackContext StackContext}).</li>
0039: * <li> Improved algorithms (e.g. Concurrent Karabutsa multiplication in
0040: * O(n<sup>Log3</sup>) instead of O(n<sup>2</sup>).</li>
0041: * </ul></p>
0042: *
0043: * <p> <b>Note:</b> This class uses {@link ConcurrentContext ConcurrentContext}
0044: * to accelerate calculations on multi-cores systems.</p>
0045: *
0046: * @author <a href="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle</a>
0047: * @version 3.3, January 14, 2007
0048: * @see <a href="http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic">
0049: * Wikipedia: Arbitrary-precision Arithmetic</a>
0050: */
0051: public final class LargeInteger extends Number<LargeInteger> {
0052:
0053: /**
0054: * Holds the certainty required when testing for primality
0055: * (default <code>100</code>, the probability for a composite to
0056: * pass the primality test is less than <code>2<sup>-100</sup></code>).
0057: */
0058: public static final Configurable<Integer> PRIME_CERTAINTY = new Configurable<Integer>(
0059: 100);
0060:
0061: /**
0062: * Holds the format for large integers (decimal representation by default).
0063: *
0064: * @see #parse(CharSequence, int, TextFormat.Cursor)
0065: * @see #format(LargeInteger, int, Appendable)
0066: */
0067: static final TextFormat<LargeInteger> DECIMAL_FORMAT = new TextFormat<LargeInteger>() {
0068:
0069: @Override
0070: public Appendable format(LargeInteger li, Appendable out)
0071: throws IOException {
0072: return LargeInteger.format(li, 10, out);
0073: }
0074:
0075: @Override
0076: public LargeInteger parse(CharSequence csq, Cursor cursor) {
0077: return LargeInteger.parse(csq, 10, cursor);
0078: }
0079: };
0080: static {
0081: TextFormat.setInstance(LargeInteger.class, DECIMAL_FORMAT);
0082: }
0083:
0084: /**
0085: * Holds factory for LargeInteger with variable size arrays.
0086: */
0087: private static final ArrayFactory<LargeInteger> ARRAY_FACTORY = new ArrayFactory<LargeInteger>() {
0088:
0089: @Override
0090: protected LargeInteger create(int capacity) {
0091: return new LargeInteger(capacity);
0092: }
0093:
0094: };
0095:
0096: /**
0097: * Holds the factory for LargeInteger with no intrinsic array (wrapper instances).
0098: */
0099: private static final ObjectFactory<LargeInteger> NO_ARRAY_FACTORY = new ObjectFactory<LargeInteger>() {
0100:
0101: @Override
0102: protected LargeInteger create() {
0103: return new LargeInteger();
0104: }
0105:
0106: };
0107:
0108: /**
0109: * Holds the default XML representation for large integers.
0110: * This representation consists of a simple <code>value</code> attribute
0111: * holding the {@link #toText() textual} representation.
0112: */
0113: static final XMLFormat<LargeInteger> XML = new XMLFormat<LargeInteger>(
0114: LargeInteger.class) {
0115:
0116: @Override
0117: public LargeInteger newInstance(Class<LargeInteger> cls,
0118: InputElement xml) throws XMLStreamException {
0119: return LargeInteger.valueOf(xml.getAttribute("value"));
0120: }
0121:
0122: public void write(LargeInteger li, OutputElement xml)
0123: throws XMLStreamException {
0124: xml.setAttribute("value", li.toText());
0125: }
0126:
0127: public void read(InputElement xml, LargeInteger li) {
0128: // Nothing to do, immutable.
0129: }
0130: };
0131:
0132: /**
0133: * The large integer representing the additive identity.
0134: */
0135: public static final LargeInteger ZERO = new LargeInteger(1);
0136:
0137: /**
0138: * The large integer representing the multiplicative identity.
0139: */
0140: public static final LargeInteger ONE = new LargeInteger(1);
0141: static {
0142: ONE._words[0] = 1;
0143: ONE._size = 1;
0144: }
0145:
0146: /**
0147: * Holds Long.MIN_VALUE
0148: */
0149: static final LargeInteger LONG_MIN_VALUE = new LargeInteger(2);
0150: static {
0151: LONG_MIN_VALUE._words[1] = 1;
0152: LONG_MIN_VALUE._size = 2;
0153: }
0154:
0155: /**
0156: * Holds five.
0157: */
0158: static final LargeInteger FIVE = new LargeInteger(1);
0159: static {
0160: LONG_MIN_VALUE._words[1] = 5;
0161: LONG_MIN_VALUE._size = 1;
0162: }
0163:
0164: /**
0165: * Holds the remainder after a {@link #divide} operation.
0166: */
0167: private LargeInteger _remainder;
0168:
0169: /**
0170: * Indicates if this large integer is negative.
0171: */
0172: private boolean _isNegative;
0173:
0174: /**
0175: * The size of this large integer in words.
0176: * The most significand word different from 0 is at index: _size-1
0177: */
0178: private int _size;
0179:
0180: /**
0181: * This large integer positive words (63 bits).
0182: * Least significant word first (index 0).
0183: */
0184: private long[] _words;
0185:
0186: /**
0187: * Default constructor (no words array).
0188: */
0189: private LargeInteger() {
0190: }
0191:
0192: /**
0193: * Creates a large integer with the specified 63 bits word capacity.
0194: *
0195: * @link wordLength the internal positive <code>long</code> array length.
0196: */
0197: private LargeInteger(int wordLength) {
0198: _words = new long[wordLength];
0199: }
0200:
0201: /**
0202: * Returns the large integer of specified <code>long</code> value.
0203: *
0204: * @param value the <code>long</code> value.
0205: * @return the corresponding large integer number.
0206: */
0207: public static LargeInteger valueOf(long value) {
0208: if (value == 0)
0209: return ZERO;
0210: if (value == Long.MIN_VALUE)
0211: return LONG_MIN_VALUE;
0212: LargeInteger li = ARRAY_FACTORY.array(1);
0213: boolean negative = li._isNegative = value < 0;
0214: li._words[0] = negative ? -value : value;
0215: li._size = 1;
0216: return li;
0217: }
0218:
0219: /**
0220: * Returns the large integer of specified two's-complement binary
0221: * representation. The input array is assumed to be in <i>big-endian</i>
0222: * byte-order: the most significant byte is at the offset position.
0223: *
0224: * @param bytes the binary representation (two's-complement).
0225: * @param offset the offset at which to start reading the bytes.
0226: * @param length the maximum number of bytes to read.
0227: * @return the corresponding large integer number.
0228: * @throws IndexOutOfBoundsException
0229: * if <code>offset + length > bytes.length</code>
0230: * @see #toByteArray
0231: */
0232: public static LargeInteger valueOf(byte[] bytes, int offset,
0233: int length) {
0234: // Ensures result is large enough (takes into account potential
0235: // extra bits during negative to positive conversion).
0236: LargeInteger li = ARRAY_FACTORY
0237: .array(((length * 8 + 1) / 63) + 1);
0238: final boolean isNegative = bytes[offset] < 0;
0239: int wordIndex = 0;
0240: int bitIndex = 0;
0241: li._words[0] = 0;
0242: for (int i = offset + length; i > offset; bitIndex += 8) {
0243: long bits = (isNegative ? ~bytes[--i] : bytes[--i])
0244: & MASK_8;
0245: if (bitIndex < 63 - 8) {
0246: li._words[wordIndex] |= bits << bitIndex;
0247: } else { // End of word reached.
0248: li._words[wordIndex] |= (bits << bitIndex) & MASK_63;
0249: bitIndex -= 63; // In range [-8..-1]
0250: li._words[++wordIndex] = bits >> -bitIndex;
0251: }
0252: }
0253: // Calculates size.
0254: while (li._words[wordIndex] == 0) {
0255: if (--wordIndex < 0)
0256: break;
0257: }
0258: li._size = wordIndex + 1;
0259: li._isNegative = isNegative;
0260:
0261: // Converts one's-complement to two's-complement if negative.
0262: if (isNegative) { // Adds ONE.
0263: li._size = Calculus.add(li._words, li._size, ONE._words, 1,
0264: li._words);
0265: }
0266: return li;
0267: }
0268:
0269: /**
0270: * Returns the two's-complement binary representation of this
0271: * large integer. The output array is in <i>big-endian</i>
0272: * byte-order: the most significant byte is at the offset position.
0273: *
0274: * @param bytes the bytes to hold the binary representation
0275: * (two's-complement) of this large integer.
0276: * @param offset the offset at which to start writing the bytes.
0277: * @return the number of bytes written.
0278: * @throws IndexOutOfBoundsException
0279: * if <code>bytes.length < (bitLength() >> 3) + 1</code>
0280: * @see #valueOf(byte[], int, int)
0281: * @see #bitLength
0282: */
0283: public int toByteArray(byte[] bytes, int offset) {
0284: int bytesLength = (bitLength() >> 3) + 1;
0285: int wordIndex = 0;
0286: int bitIndex = 0;
0287: if (_isNegative) {
0288: long word = _words[0] - 1;
0289: long borrow = word >> 63; // -1 if borrow
0290: word = ~word & MASK_63;
0291: for (int i = bytesLength + offset; i > offset; bitIndex += 8) {
0292: if (bitIndex < 63 - 8) {
0293: bytes[--i] = (byte) word;
0294: word >>= 8;
0295: } else { // End of word reached.
0296: byte bits = (byte) word;
0297: word = (++wordIndex < _size) ? _words[wordIndex]
0298: + borrow : borrow;
0299: borrow = word >> 63; // -1 if borrow
0300: word = ~word & MASK_63;
0301: bitIndex -= 63; // In range [-8..-1]
0302: bytes[--i] = (byte) ((word << -bitIndex) | bits);
0303: word >>= (8 + bitIndex);
0304: }
0305: }
0306: } else {
0307: if (_size != 0) {
0308: long word = _words[0];
0309: for (int i = bytesLength + offset; i > offset; bitIndex += 8) {
0310: if (bitIndex < 63 - 8) {
0311: bytes[--i] = (byte) word;
0312: word >>= 8;
0313: } else { // End of word reached.
0314: byte bits = (byte) word;
0315: word = (++wordIndex < _size) ? _words[wordIndex]
0316: : 0;
0317: bitIndex -= 63; // In range [-8..-1]
0318: bytes[--i] = (byte) ((word << -bitIndex) | bits);
0319: word >>= (8 + bitIndex);
0320: }
0321: }
0322: } else { // ZERO
0323: bytes[offset] = 0;
0324: }
0325: }
0326: return bytesLength;
0327: }
0328:
0329: /**
0330: * Returns the large integer for the specified character sequence
0331: * using the current {@link TextFormat#getInstance(Class) format}.
0332: *
0333: * @param csq the character sequence to parse.
0334: * @return <code>TextFormat.getInstance(LargeInteger.class).parse(csq)</code>
0335: * @throws NumberFormatException if error when parsing.
0336: */
0337: public static LargeInteger valueOf(CharSequence csq) {
0338: return TextFormat.getInstance(LargeInteger.class).parse(csq);
0339: }
0340:
0341: /**
0342: * Returns the large integer for the specified character sequence in
0343: * the specified radix.
0344: *
0345: * @param csq the character sequence to parse.
0346: * @param radix the radix of the representation.
0347: * @return <code>LargeInteger.parse(csq, radix, cursor)</code>
0348: * @throws NumberFormatException if error when parsing.
0349: */
0350: public static LargeInteger valueOf(CharSequence csq, int radix) {
0351: Cursor cursor = Cursor.newInstance(0, csq.length());
0352: try {
0353: return LargeInteger.parse(csq, radix, cursor);
0354: } finally {
0355: if (cursor.hasNext())
0356: throw new NumberFormatException("Cannot parse " + csq
0357: + " at " + cursor);
0358: Cursor.recycle(cursor);
0359: }
0360: }
0361:
0362: /**
0363: * Returns the large integer corresponding to the specified
0364: * <code>java.math.BigInteger</code> instance.
0365: *
0366: * @param bigInteger the big integer instance.
0367: * @return the large integer having the same value.
0368: */
0369: public static LargeInteger valueOf(java.math.BigInteger bigInteger) {
0370: byte[] bytes = bigInteger.toByteArray();
0371: return LargeInteger.valueOf(bytes, 0, bytes.length);
0372: }
0373:
0374: /**
0375: * Indicates if this large integer is greater than {@link #ZERO}
0376: * ({@link #ZERO}is not included).
0377: *
0378: * @return <code>this > ZERO</code>
0379: */
0380: public boolean isPositive() {
0381: return !_isNegative && (_size != 0);
0382: }
0383:
0384: /**
0385: * Indicates if this large integer is less than {@link #ZERO}.
0386: *
0387: * @return <code>this < ZERO</code>
0388: */
0389: public boolean isNegative() {
0390: return _isNegative;
0391: }
0392:
0393: /**
0394: * Indicates if this large integer is equal to {@link #ZERO}.
0395: *
0396: * @return <code>this == ZERO</code>
0397: */
0398: public boolean isZero() {
0399: return _size == 0;
0400: }
0401:
0402: /**
0403: * Indicates if this large integer is an even number.
0404: *
0405: * @return <code>(this & 1) == ZERO</code>
0406: */
0407: public boolean isEven() {
0408: return (_size == 0) || ((_words[0] & 1) == 0);
0409: }
0410:
0411: /**
0412: * Indicates if this large integer is an odd number.
0413: *
0414: * @return <code>(this & 1) != ZERO</code>
0415: */
0416: public boolean isOdd() {
0417: return !isEven();
0418: }
0419:
0420: /**
0421: * Indicates if this large integer is probably prime.
0422: *
0423: * @return <code>true</code> if this large integer is probable prime;
0424: * <code>false</code> otherwise.
0425: */
0426: public boolean isProbablyPrime() {
0427: throw new UnsupportedOperationException("Not Implemented");
0428: }
0429:
0430: /**
0431: * Returns the minimal number of bits to represent this large integer
0432: * in the minimal two's-complement (sign excluded).
0433: *
0434: * @return the length of this integer in bits (sign excluded).
0435: */
0436: public int bitLength() {
0437: if (_size == 0)
0438: return 0;
0439: final int n = _size - 1;
0440: final int bitLength = MathLib.bitLength(_words[n]) + (n << 6)
0441: - n;
0442: return (this .isNegative() && this .isPowerOfTwo()) ? bitLength - 1
0443: : bitLength;
0444: }
0445:
0446: /**
0447: * Returns the minimal number of decimal digits necessary to represent
0448: * this large integer (sign excluded).
0449: *
0450: * @return the maximum number of digits.
0451: */
0452: public int digitLength() {
0453: int bitLength = this .bitLength();
0454: int min = (int) (bitLength * BITS_TO_DIGITS) + 1;
0455: int max = (int) ((bitLength + 1) * BITS_TO_DIGITS) + 1;
0456: if (min == max)
0457: return min;
0458: return (LargeInteger.ONE.times10pow(min + 1).isLargerThan(this )) ? min
0459: : min + 1;
0460: }
0461:
0462: private static final double BITS_TO_DIGITS = MathLib.LOG2
0463: / MathLib.LOG10;
0464:
0465: /**
0466: * Indicates if this number is a power of two (equals to 2<sup>
0467: * ({@link #bitLength bitLength()} - 1)</sup>).
0468: *
0469: * @return <code>true</code> if this number is a power of two;
0470: * <code>false</code> otherwise.
0471: */
0472: public boolean isPowerOfTwo() {
0473: if (_size == 0)
0474: return false;
0475: final int n = _size - 1;
0476: for (int j = 0; j < n; j++) {
0477: if (_words[j] != 0)
0478: return false;
0479: }
0480: final int bitLength = MathLib.bitLength(_words[n]);
0481: return _words[n] == (1L << (bitLength - 1));
0482: }
0483:
0484: /**
0485: * Returns the index of the lowest-order one bit in this large integer
0486: * or <code>-1</code> if <code>this.equals(ZERO)</code>.
0487: *
0488: * @return the index of the rightmost bit set or <code>-1</code>
0489: */
0490: public int getLowestSetBit() {
0491: if (_size == 0)
0492: return -1;
0493: for (int i = 0;; i++) {
0494: long w = _words[i];
0495: if (w == 0)
0496: continue;
0497: for (int j = 0;; j++) {
0498: if (((1L << j) & w) != 0)
0499: return i * 63 + j;
0500: }
0501: }
0502: }
0503:
0504: /**
0505: * Returns the final undivided part after division that is less or of
0506: * lower degree than the divisor. This value is only set by the
0507: * {@link #divide} operation and is not considered as part of
0508: * this large integer (ignored by all methods).
0509: *
0510: * @return the remainder of the division for which this large integer
0511: * is the quotient.
0512: */
0513: public LargeInteger getRemainder() {
0514: return _remainder;
0515: }
0516:
0517: /**
0518: * Indicates if this large integer is larger than the one
0519: * specified in absolute value.
0520: *
0521: * @param that the integer to be compared with.
0522: * @return <code>this.abs().compareTo(that.abs()) > 0</code>.
0523: */
0524: public boolean isLargerThan(LargeInteger that) {
0525: return (this ._size > that._size)
0526: || ((this ._size == that._size) && Calculus.compare(
0527: this ._words, that._words, this ._size) > 0);
0528: }
0529:
0530: /**
0531: * Returns the absolute value of this large integer.
0532: *
0533: * @return <code>|this|</code>.
0534: */
0535: public LargeInteger abs() {
0536: if (_isNegative)
0537: return this .opposite();
0538: return this ;
0539: }
0540:
0541: /**
0542: * Returns the opposite of this large integer.
0543: *
0544: * @return <code>-this</code>.
0545: */
0546: public LargeInteger opposite() {
0547: LargeInteger li = NO_ARRAY_FACTORY.object();
0548: li._words = _words;
0549: li._size = _size;
0550: li._isNegative = !_isNegative && (_size != 0);
0551: return li;
0552: }
0553:
0554: /**
0555: * Returns the sum of this large integer with the specified
0556: * <code>long</code> integer (convenience method)
0557: *
0558: * @param value the <code>long</code> integer being added.
0559: * @return <code>this + value</code>.
0560: */
0561: public LargeInteger plus(long value) {
0562: return this .plus(LargeInteger.valueOf(value));
0563: }
0564:
0565: /**
0566: * Returns the sum of this large integer with the one specified.
0567: *
0568: * @param that the integer to be added.
0569: * @return <code>this + that</code>.
0570: */
0571: public LargeInteger plus(LargeInteger that) {
0572: if (this ._size < that._size) // Adds smallest in size to largest.
0573: return that.plus(this );
0574: if ((this ._isNegative != that._isNegative) && (that._size != 0))
0575: return this .minus(that.opposite()); // Switches that sign.
0576: LargeInteger li = ARRAY_FACTORY.array(_size + 1);
0577: li._size = Calculus.add(_words, _size, that._words, that._size,
0578: li._words);
0579: li._isNegative = _isNegative;
0580: return li;
0581: }
0582:
0583: /**
0584: * Returns the difference between this large integer and the one
0585: * specified.
0586: *
0587: * @param that the integer to be subtracted.
0588: * @return <code>this - that</code>.
0589: */
0590: public LargeInteger minus(LargeInteger that) {
0591: if ((this ._isNegative != that._isNegative) && (that._size != 0))
0592: return this .plus(that.opposite()); // Switches that sign.
0593: if (that.isLargerThan(this )) // Always subtract the smallest to the largest.
0594: return that.minus(this ).opposite();
0595: LargeInteger li = ARRAY_FACTORY.array(this ._size);
0596: li._size = Calculus.subtract(_words, _size, that._words,
0597: that._size, li._words);
0598: li._isNegative = this ._isNegative && (li._size != 0);
0599: return li;
0600: }
0601:
0602: /**
0603: * Returns the difference between this large integer and the specified
0604: * value
0605: *
0606: * @param value the value to be subtracted.
0607: * @return <code>this - value</code>.
0608: */
0609: public LargeInteger minus(long value) {
0610: return this .minus(LargeInteger.valueOf(value));
0611: }
0612:
0613: /**
0614: * Returns the product of this large integer with the one specified.
0615: *
0616: * @param that the large integer multiplier.
0617: * @return <code>this · that</code>.
0618: */
0619: public LargeInteger times(LargeInteger that) {
0620: if (that._size > this ._size) // Always multiply the smallest to the largest.
0621: return that.times(this );
0622: if (that._size <= 1) // Direct times(long) multiplication.
0623: return this .times(that.longValue());
0624: if (that._size < 10) { // Conventional multiplication.
0625: LargeInteger li = ARRAY_FACTORY.array(this ._size
0626: + that._size);
0627: li._size = Calculus.multiply(this ._words, this ._size,
0628: that._words, that._size, li._words);
0629: li._isNegative = (this ._isNegative != that._isNegative);
0630: return li;
0631: } else if (that._size < 20) { // Karatsuba (sequential).
0632: int n = (that._size >> 1) + (that._size & 1);
0633: // this = a + 2^(n*63) b, that = c + 2^(n*63) d
0634: LargeInteger b = this .high(n);
0635: LargeInteger a = this .low(n);
0636: // Optimization for square (a == c, b == d).
0637: LargeInteger d = (this == that) ? b : that.high(n);
0638: LargeInteger c = (this == that) ? a : that.low(n);
0639: LargeInteger ab = a.plus(b);
0640: LargeInteger cd = (this == that) ? ab : c.plus(d);
0641: LargeInteger abcd = ab.times(cd);
0642: LargeInteger ac = a.times(c);
0643: LargeInteger bd = b.times(d);
0644: // li = a*c + ((a+b)*(c+d)-(a*c+b*d)) 2^n + b*d 2^2n
0645: return ac.plus(abcd.minus(ac.plus(bd)).shiftWordLeft(n))
0646: .plus(bd.shiftWordLeft(n << 1));
0647: } else { // Karatsuba (concurrent).
0648: int n = (that._size >> 1) + (that._size & 1);
0649: // this = a + 2^(63*n) b, that = c + 2^(63*n) d
0650: LargeInteger b = this .high(n);
0651: LargeInteger a = this .low(n);
0652: // Optimization for square (a == c, b == d).
0653: LargeInteger d = (this == that) ? b : that.high(n);
0654: LargeInteger c = (this == that) ? a : that.low(n);
0655: LargeInteger ab = a.plus(b);
0656: LargeInteger cd = (this == that) ? ab : c.plus(d);
0657: MultiplyLogic abcd = MultiplyLogic.newInstance(ab, cd);
0658: MultiplyLogic ac = MultiplyLogic.newInstance(a, c);
0659: MultiplyLogic bd = MultiplyLogic.newInstance(b, d);
0660: ConcurrentContext.enter();
0661: try { // this = a + 2^n b, that = c + 2^n d
0662: ConcurrentContext.execute(abcd);
0663: ConcurrentContext.execute(ac);
0664: ConcurrentContext.execute(bd);
0665: } finally {
0666: ConcurrentContext.exit();
0667: }
0668: // result = a*c + ((a+b)*(c+d)-(a*c+b*d)) 2^n + b*d 2^2n
0669: LargeInteger result = ac.value().plus(
0670: abcd.value().minus(ac.value().plus(bd.value()))
0671: .shiftWordLeft(n)).plus(
0672: bd.value().shiftWordLeft(n << 1));
0673: return result;
0674: }
0675: }
0676:
0677: private LargeInteger high(int w) { // this.shiftRight(w * 63)
0678: LargeInteger li = ARRAY_FACTORY.array(_size - w);
0679: li._isNegative = _isNegative;
0680: li._size = _size - w;
0681: System.arraycopy(_words, w, li._words, 0, _size - w);
0682: return li;
0683: }
0684:
0685: private LargeInteger low(int w) { // this.minus(high(w).shiftLeft(w * 63));
0686: LargeInteger li = NO_ARRAY_FACTORY.object();
0687: li._words = _words;
0688: li._isNegative = _isNegative;
0689: for (int i = w; i > 0; i--) {
0690: if (_words[i - 1] != 0) {
0691: li._size = i;
0692: return li;
0693: }
0694: } // Else zero.
0695: return LargeInteger.ZERO;
0696: }
0697:
0698: private LargeInteger shiftWordLeft(int w) { // this.minus(high(w).shiftLeft(w * 63));
0699: if (_size == 0)
0700: return LargeInteger.ZERO;
0701: LargeInteger li = ARRAY_FACTORY.array(w + _size);
0702: li._isNegative = _isNegative;
0703: li._size = w + _size;
0704: for (int i = 0; i < w;) {
0705: li._words[i++] = 0;
0706: }
0707: System.arraycopy(_words, 0, li._words, w, _size);
0708: return li;
0709: }
0710:
0711: /**
0712: * Returns the product of this large integer with the specified
0713: * <code>long</code> multiplier.
0714: *
0715: * @param multiplier the <code>long</code> multiplier.
0716: * @return <code>this · multiplier</code>.
0717: */
0718: public LargeInteger times(long multiplier) {
0719: if ((this ._size == 0) || (multiplier == 0))
0720: return LargeInteger.ZERO;
0721: if (multiplier == Long.MIN_VALUE)
0722: return times(LONG_MIN_VALUE); // Size 2.
0723: boolean isNegative = _isNegative ^ (multiplier < 0);
0724: multiplier = MathLib.abs(multiplier);
0725: LargeInteger li = ARRAY_FACTORY.array(_size + 1);
0726: li._size = Calculus.multiply(_words, _size, multiplier,
0727: li._words);
0728: li._isNegative = isNegative;
0729: return li;
0730: }
0731:
0732: /**
0733: * Returns this large integer divided by the one specified (integer
0734: * division). The remainder of this division is accessible using
0735: * {@link #getRemainder}.
0736: *
0737: * @param that the integer divisor.
0738: * @return <code>this / that</code> and <code>this % that</code>
0739: * ({@link #getRemainder})
0740: * @throws ArithmeticException if <code>that.equals(ZERO)</code>
0741: */
0742: public LargeInteger divide(LargeInteger that) {
0743: if ((that._size <= 1) && ((that._words[0] >> 32) == 0))
0744: return divide(that.intValue());
0745: LargeInteger result;
0746: LargeInteger remainder;
0747: LargeInteger this Abs = this .abs();
0748: LargeInteger thatAbs = that.abs();
0749: int precision = this Abs.bitLength() - thatAbs.bitLength() + 1;
0750: if (precision <= 0) {
0751: result = LargeInteger.ZERO;
0752: remainder = this ;
0753: } else {
0754: LargeInteger thatReciprocal = thatAbs
0755: .inverseScaled(precision);
0756: result = this Abs.times(thatReciprocal);
0757: result = result.shiftRight(this Abs.bitLength() + 1);
0758:
0759: // Calculates remainder, corrects for result +/- 1 error.
0760: remainder = this Abs.minus(thatAbs.times(result));
0761: if (remainder.compareTo(thatAbs) >= 0) {
0762: remainder = remainder.minus(thatAbs);
0763: result = result.plus(LargeInteger.ONE);
0764: if (remainder.compareTo(thatAbs) >= 0)
0765: throw new Error("Verification error for " + this
0766: + "/" + that
0767: + ", please submit a bug report.");
0768: } else if (remainder.isNegative()) {
0769: remainder = remainder.plus(thatAbs);
0770: result = result.minus(ONE);
0771: if (remainder.isNegative())
0772: throw new Error("Verification error for " + this
0773: + "/" + that
0774: + ", please submit a bug report.");
0775: }
0776: }
0777: // Setups result and remainder.
0778: LargeInteger li = NO_ARRAY_FACTORY.object();
0779: li._words = result._words;
0780: li._size = result._size;
0781: li._isNegative = (this ._isNegative != that._isNegative)
0782: && (result._size != 0);
0783: li._remainder = _isNegative ? remainder.opposite() : remainder;
0784: return li;
0785: }
0786:
0787: /**
0788: * Returns this large integer divided by the specified <code>int</code>
0789: * divisor. The remainder of this division is accessible using
0790: * {@link #getRemainder}.
0791: *
0792: * @param divisor the <code>int</code> divisor.
0793: * @return <code>this / divisor</code> and <code>this % divisor</code>
0794: * ({@link #getRemainder})
0795: * @throws ArithmeticException if <code>divisor == 0</code>
0796: */
0797: public LargeInteger divide(int divisor) {
0798: if (divisor == 0)
0799: throw new ArithmeticException("Division by zero");
0800: if (divisor == Integer.MIN_VALUE) { // abs(divisor) would overflow.
0801: LargeInteger li = this .times2pow(-31).copy();
0802: li._isNegative = !_isNegative && (li._size != 0);
0803: li._remainder = _isNegative ? LargeInteger
0804: .valueOf(-(_words[0] & MASK_31)) : LargeInteger
0805: .valueOf(_words[0] & MASK_31);
0806: return li;
0807: }
0808: LargeInteger li = ARRAY_FACTORY.array(_size);
0809: long rem = Calculus.divide(_words, _size, MathLib.abs(divisor),
0810: li._words);
0811: li._size = (_size > 0) && (li._words[_size - 1] == 0L) ? _size - 1
0812: : _size;
0813: li._isNegative = (_isNegative != (divisor < 0))
0814: && (li._size != 0);
0815: li._remainder = LargeInteger.valueOf(_isNegative ? -rem : rem);
0816: return li;
0817: }
0818:
0819: /**
0820: * Returns the remainder of the division of this large integer with
0821: * the one specified (convenience method equivalent to
0822: * <code>this.divide(that).getRemainder()</code>).
0823: *
0824: * @param that the value by which this integer is to be divided, and the
0825: * remainder returned.
0826: * @return <code>this % that</code>
0827: * @throws ArithmeticException if <code>that.equals(ZERO)</code>
0828: * @see #divide(LargeInteger)
0829: */
0830: public LargeInteger remainder(LargeInteger that) {
0831: return this .divide(that).getRemainder();
0832: }
0833:
0834: /**
0835: * Returns a scaled approximation of <code>1 / this</code>.
0836: *
0837: * @param precision the requested precision (reciprocal error being ± 1).
0838: * @return <code>2<sup>(precision + this.bitLength())</sup> / this</code>
0839: * @throws ArithmeticException if <code>this.isZero()</code>
0840: */
0841: public LargeInteger inverseScaled(int precision) {
0842: if (precision <= 30) { // Straight calculation.
0843: long divisor = this .shiftRight(this .bitLength() - precision
0844: - 1)._words[0];
0845: long dividend = 1L << (precision * 2 + 1);
0846: return (this .isNegative()) ? LargeInteger.valueOf(-dividend
0847: / divisor) : LargeInteger.valueOf(dividend
0848: / divisor);
0849: } else { // Newton iteration (x = 2 * x - x^2 * this).
0850: LargeInteger x = inverseScaled(precision / 2 + 1); // Estimate.
0851: LargeInteger this Trunc = shiftRight(bitLength()
0852: - (precision + 2));
0853: LargeInteger prod = this Trunc.times(x).times(x);
0854: int diff = 2 * (precision / 2 + 2);
0855: LargeInteger prodTrunc = prod.shiftRight(diff);
0856: LargeInteger xPad = x.shiftLeft(precision - precision / 2
0857: - 1);
0858: LargeInteger tmp = xPad.minus(prodTrunc);
0859: return xPad.plus(tmp);
0860: }
0861: }
0862:
0863: /**
0864: * Returns the integer square root of this integer.
0865: *
0866: * @return <code>k<code> such as <code>k^2 <= this < (k + 1)^2</code>
0867: * @throws ArithmeticException if this integer is negative.
0868: */
0869: public LargeInteger sqrt() {
0870: if (this .isNegative())
0871: throw new ArithmeticException(
0872: "Square root of negative integer");
0873: int bitLength = this .bitLength();
0874: StackContext.enter();
0875: try {
0876: // First approximation.
0877: LargeInteger k = this
0878: .times2pow(-((bitLength >> 1) + (bitLength & 1)));
0879: while (true) {
0880: LargeInteger newK = (k.plus(this .divide(k)))
0881: .times2pow(-1);
0882: if (newK.equals(k))
0883: return StackContext.outerCopy(k);
0884: k = newK;
0885: }
0886: } finally {
0887: StackContext.exit();
0888: }
0889: }
0890:
0891: /**
0892: * Returns this large integer modulo the specified large integer.
0893: *
0894: * <p> Note: The result as the same sign as the divisor unlike the Java
0895: * remainder (%) operator (which as the same sign as the dividend).</p>
0896: *
0897: * @param m the modulus.
0898: * @return <code>this mod m</code>
0899: * @see #getRemainder()
0900: */
0901: public LargeInteger mod(LargeInteger m) {
0902: final LargeInteger li = m.isLargerThan(this ) ? this : this
0903: .divide(m).getRemainder();
0904: return (this ._isNegative == m._isNegative) ? li : li.plus(m);
0905: }
0906:
0907: /**
0908: * Returns the large integer whose value is <code>(this<sup>-1</sup> mod m)
0909: * </code>.
0910: *
0911: * @param m the modulus.
0912: * @return <code>this<sup>-1</sup> mod m</code>.
0913: * @throws ArithmeticException <code> m <= 0</code>, or this integer
0914: * has no multiplicative inverse mod m (that is, this integer
0915: * is not <i>relatively prime</i> to m).
0916: */
0917: public LargeInteger modInverse(LargeInteger m) {
0918: if (!m.isPositive())
0919: throw new ArithmeticException(
0920: "Modulus is not a positive number");
0921: StackContext.enter();
0922: try {
0923: // Extended Euclidian Algorithm
0924: LargeInteger a = this ;
0925: LargeInteger b = m;
0926: LargeInteger p = ONE;
0927: LargeInteger q = ZERO;
0928: LargeInteger r = ZERO;
0929: LargeInteger s = ONE;
0930: while (!b.isZero()) {
0931: LargeInteger quot = a.divide(b);
0932: LargeInteger c = quot.getRemainder();
0933: a = b;
0934: b = c;
0935:
0936: LargeInteger new_r = p.minus(quot.times(r));
0937: LargeInteger new_s = q.minus(quot.times(s));
0938: p = r;
0939: q = s;
0940: r = new_r;
0941: s = new_s;
0942: }
0943: if (!a.abs().equals(ONE)) // (a != 1) || (a != -1)
0944: throw new ArithmeticException("GCD(" + this + ", " + m
0945: + ") = " + a);
0946: return StackContext.outerCopy(a.isNegative() ? p.opposite()
0947: .mod(m) : p.mod(m));
0948: } finally {
0949: StackContext.exit();
0950: }
0951: }
0952:
0953: /**
0954: * Returns this large integer raised at the specified exponent modulo
0955: * the specified modulus.
0956: *
0957: * @param exp the exponent.
0958: * @param m the modulus.
0959: * @return <code>this<sup>exp</sup> mod m</code>
0960: * @throws ArithmeticException <code>m <= 0</code>
0961: * @see #modInverse
0962: */
0963: public LargeInteger modPow(LargeInteger exp, LargeInteger m) {
0964: if (!m.isPositive())
0965: throw new ArithmeticException(
0966: "Modulus is not a positive number");
0967: if (exp.isPositive()) {
0968: StackContext.enter();
0969: try {
0970: LargeInteger result = null;
0971: LargeInteger pow2 = this .mod(m);
0972: while (exp.compareTo(ONE) >= 0) { // Iteration.
0973: if (exp.isOdd()) {
0974: result = (result == null) ? pow2 : result
0975: .times(pow2).mod(m);
0976: }
0977: pow2 = pow2.times(pow2).mod(m);
0978: exp = exp.shiftRight(1);
0979: }
0980: return StackContext.outerCopy(result);
0981: } finally {
0982: StackContext.exit();
0983: }
0984: } else if (exp.isNegative()) {
0985: return this .modPow(exp.opposite(), m).modInverse(m);
0986: } else { // exp == 0
0987: return LargeInteger.ONE;
0988: }
0989: }
0990:
0991: /**
0992: * Returns the greatest common divisor of this large integer and
0993: * the one specified.
0994: *
0995: * @param that the other number to compute the GCD with.
0996: * @return a positive number or {@link #ZERO} if
0997: * <code>(this.isZero() && that.isZero())</code>.
0998: */
0999: public LargeInteger gcd(LargeInteger that) {
1000: if (this .isZero())
1001: return that;
1002: if (that.isZero())
1003: return this ;
1004: // Works with local (modifiable) copies of the inputs.
1005: LargeInteger u = this .copy();
1006: u._isNegative = false; // abs()
1007: LargeInteger v = that.copy();
1008: v._isNegative = false; // abs()
1009:
1010: // Euclidian algorithm until u, v about the same size.
1011: while (MathLib.abs(u._size - v._size) > 1) {
1012: LargeInteger tmp = u.divide(v);
1013: LargeInteger rem = tmp.getRemainder();
1014: u = v;
1015: v = rem;
1016: if (v.isZero())
1017: return u;
1018: }
1019:
1020: // Binary GCD Implementation adapted from
1021: // http://en.wikipedia.org/wiki/Binary_GCD_algorithm
1022: final int uShift = u.getLowestSetBit();
1023: u.shiftRightSelf(uShift);
1024: final int vShift = v.getLowestSetBit();
1025: v.shiftRightSelf(vShift);
1026:
1027: // From here on, u is always odd.
1028: while (true) {
1029: // Now u and v are both odd, so diff(u, v) is even.
1030: // Let u = min(u, v), v = diff(u, v)/2.
1031: if (u.compareTo(v) < 0) {
1032: v.subtract(u);
1033: } else {
1034: u.subtract(v);
1035: LargeInteger tmp = u;
1036: u = v;
1037: v = tmp; // Swaps.
1038: }
1039: v.shiftRightSelf();
1040: if (v.isZero())
1041: break;
1042: v.shiftRightSelf(v.getLowestSetBit());
1043: }
1044: return u.shiftLeft(MathLib.min(uShift, vShift));
1045: }
1046:
1047: private void shiftRightSelf() {
1048: if (_size == 0)
1049: return;
1050: _size = Calculus.shiftRight(0, 1, _words, _size, _words);
1051: }
1052:
1053: private void shiftRightSelf(int n) {
1054: if ((n == 0) || (_size == 0))
1055: return;
1056: int wordShift = n < 63 ? 0 : n / 63;
1057: int bitShift = n - ((wordShift << 6) - wordShift); // n - wordShift * 63
1058: _size = Calculus.shiftRight(wordShift, bitShift, _words, _size,
1059: _words);
1060: }
1061:
1062: private void subtract(LargeInteger that) { // this >= that
1063: _size = Calculus.subtract(_words, _size, that._words,
1064: that._size, _words);
1065: }
1066:
1067: /**
1068: * Returns the value of this large integer after performing a binary
1069: * shift to left. The shift distance, <code>n</code>, may be negative,
1070: * in which case this method performs a right shift.
1071: *
1072: * @param n the shift distance, in bits.
1073: * @return <code>this << n</code>.
1074: * @see #shiftRight
1075: */
1076: public LargeInteger shiftLeft(int n) {
1077: if (n < 0)
1078: return shiftRight(-n);
1079: if (_size == 0)
1080: return LargeInteger.ZERO;
1081: final int wordShift = n < 63 ? 0 : n / 63;
1082: final int bitShift = n - wordShift * 63;
1083: LargeInteger li = ARRAY_FACTORY.array(_size + wordShift + 1);
1084: li._isNegative = _isNegative;
1085: li._size = Calculus.shiftLeft(wordShift, bitShift, _words,
1086: _size, li._words);
1087: return li;
1088: }
1089:
1090: /**
1091: * Returns the value of this large integer after performing a binary
1092: * shift to right with sign extension <code>(-1 >> 1 == -1)</code>.
1093: * The shift distance, <code>n</code>, may be negative, in which case
1094: * this method performs a {@link #shiftLeft(int)}.
1095: *
1096: * @param n the shift distance, in bits.
1097: * @return <code>this >> n</code>.
1098: */
1099: public LargeInteger shiftRight(int n) {
1100: LargeInteger li = this .times2pow(-n);
1101: return (_isNegative) && (n > 0) && (isShiftRightCorrection(n)) ? li
1102: .minus(LargeInteger.ONE)
1103: : li;
1104: }
1105:
1106: // Indicates if bits lost when shifting right the two's-complement
1107: // representation (affects only negative numbers).
1108: private boolean isShiftRightCorrection(int n) {
1109: int wordShift = n < 63 ? 0 : n / 63;
1110: int bitShift = n - ((wordShift << 6) - wordShift); // n - wordShift * 63
1111: int i = wordShift;
1112: boolean bitsLost = (bitShift != 0)
1113: && (_words[i] << (64 - bitShift)) != 0;
1114: while ((!bitsLost) && --i >= 0) {
1115: bitsLost = _words[i--] != 0;
1116: }
1117: return bitsLost;
1118: }
1119:
1120: /**
1121: * Returns the value of this large integer after multiplication by
1122: * a power of two. This method is equivalent to {@link #shiftLeft(int)}
1123: * for positive <code>n</code>; but is different from
1124: * {@link #shiftRight(int)} for negative <code>n</code> as no sign
1125: * extension is performed (<code>-1 >>> 1 == 0</code>).
1126: *
1127: * @param n the power of 2 exponent.
1128: * @return <code>this · 2<sup>n</sup></code>.
1129: */
1130: public LargeInteger times2pow(int n) {
1131: if (n >= 0)
1132: return shiftLeft(n);
1133: n = -n; // Works with positive n.
1134: int wordShift = n < 63 ? 0 : n / 63;
1135: int bitShift = n - ((wordShift << 6) - wordShift); // n - wordShift * 63
1136: if (_size <= wordShift) // All bits have been shifted.
1137: return LargeInteger.ZERO;
1138: LargeInteger li = ARRAY_FACTORY.array(_size - wordShift);
1139: li._size = Calculus.shiftRight(wordShift, bitShift, _words,
1140: _size, li._words);
1141: li._isNegative = _isNegative && (li._size != 0);
1142: return li;
1143: }
1144:
1145: /**
1146: * Returns the value of this large integer after multiplication by
1147: * a power of ten. For example:[code]
1148: * LargeInteger billion = LargeInteger.ONE.times10pow(9); // 1E9
1149: * LargeInteger million = billion.times10pow(-3);[/code]
1150: *
1151: * @param n the decimal exponent.
1152: * @return <code>this · 10<sup>n</sup></code>
1153: */
1154: public LargeInteger times10pow(int n) {
1155: if (this ._size == 0)
1156: return LargeInteger.ZERO;
1157: if (n >= 0) {
1158: int bitLength = (int) (n * DIGITS_TO_BITS);
1159: LargeInteger li = ARRAY_FACTORY.array(_size
1160: + (bitLength / 63) + 1); // Approx.
1161: li._isNegative = _isNegative;
1162: int i = (n >= LONG_POW_5.length) ? LONG_POW_5.length - 1
1163: : n;
1164: li._size = Calculus.multiply(_words, _size, LONG_POW_5[i],
1165: li._words);
1166: for (int j = n - i; j != 0; j -= i) {
1167: i = (j >= LONG_POW_5.length) ? LONG_POW_5.length - 1
1168: : j;
1169: li._size = Calculus.multiply(li._words, li._size,
1170: LONG_POW_5[i], li._words);
1171: }
1172: // Multiplies by 2^n
1173: final int wordShift = n < 63 ? 0 : n / 63;
1174: final int bitShift = n - ((wordShift << 6) - wordShift); // n - 63 * wordShift
1175: li._size = Calculus.shiftLeft(wordShift, bitShift,
1176: li._words, li._size, li._words);
1177: return li;
1178: } else {// n < 0
1179: n = -n;
1180: // Divides by 2^n
1181: final int wordShift = n < 63 ? 0 : n / 63;
1182: final int bitShift = n - ((wordShift << 6) - wordShift); // n - 63 * wordShift
1183: if (_size <= wordShift) // All bits would be shifted.
1184: return LargeInteger.ZERO;
1185: LargeInteger li = ARRAY_FACTORY.array(_size - wordShift);
1186: li._size = Calculus.shiftRight(wordShift, bitShift, _words,
1187: _size, li._words);
1188: for (int j = n; j != 0;) { // Divides by 5^n
1189: int i = (j >= INT_POW_5.length) ? INT_POW_5.length - 1
1190: : j;
1191: Calculus.divide(li._words, li._size, INT_POW_5[i],
1192: li._words);
1193: if ((li._size > 0) && (li._words[li._size - 1] == 0L)) {
1194: li._size--;
1195: }
1196: j -= i;
1197: }
1198: li._isNegative = _isNegative && (li._size != 0);
1199: return li;
1200: }
1201: }
1202:
1203: private static final double DIGITS_TO_BITS = MathLib.LOG10
1204: / MathLib.LOG2;
1205:
1206: private static final int[] INT_POW_5 = new int[] { 1, 5, 25, 125,
1207: 625, 3125, 15625, 78125, 390625, 1953125, 9765625,
1208: 48828125, 244140625, 1220703125 };
1209:
1210: private static final long[] LONG_POW_5 = new long[] { 1L, 5L, 25L,
1211: 125L, 625L, 3125L, 15625L, 78125L, 390625L, 1953125L,
1212: 9765625L, 48828125L, 244140625L, 1220703125L, 6103515625L,
1213: 30517578125L, 152587890625L, 762939453125L, 3814697265625L,
1214: 19073486328125L, 95367431640625L, 476837158203125L,
1215: 2384185791015625L, 11920928955078125L, 59604644775390625L,
1216: 298023223876953125L, 1490116119384765625L,
1217: 7450580596923828125L };
1218:
1219: /**
1220: * Compares this large integer against the specified object.
1221: *
1222: * @param that the object to compare with.
1223: * @return <code>true</code> if the objects are the same; <code>false</code>
1224: * otherwise.
1225: */
1226: public boolean equals(Object that) {
1227: if (!(that instanceof LargeInteger))
1228: return false;
1229: LargeInteger li = (LargeInteger) that;
1230: return (_size == li._size) && (_isNegative == li._isNegative)
1231: && (compare(_words, li._words, _size) == 0);
1232: }
1233:
1234: /**
1235: * Compares this large integer against the specified <code>long</code>
1236: * value.
1237: *
1238: * @param value <code>long</code> value to compare with.
1239: * @return <code>true</code> if this large integer has the specified value;
1240: * <code>false</code> otherwise.
1241: */
1242: public boolean equals(long value) {
1243: if (_size == 0)
1244: return value == 0;
1245: return ((_size <= 1) && (_isNegative ? -_words[0] == value
1246: : _words[0] == value))
1247: || ((value == Long.MIN_VALUE) && (_isNegative)
1248: && (_size == 2) && (_words[1] == 1) && (_words[0] == 0));
1249: }
1250:
1251: /**
1252: * Returns the hash code for this large integer number.
1253: *
1254: * @return the hash code value.
1255: */
1256: public int hashCode() {
1257: long code = 0;
1258: for (int i = _size - 1; i >= 0; i--) {
1259: code = code * 31 + _words[i];
1260: }
1261: return _isNegative ? -(int) code : (int) code;
1262: }
1263:
1264: /**
1265: * Returns the low order bits of this large integer as a <code>long</code>.
1266: *
1267: * <p>Note: This conversion can lose information about the overall magnitude
1268: * of the integer value and may return a result with the opposite
1269: * sign.</p>
1270: *
1271: * @return the numeric value represented by this integer after conversion
1272: * to type <code>long</code>.
1273: */
1274: public long longValue() {
1275: if (_size == 0)
1276: return 0;
1277: return (_size <= 1) ? (_isNegative ? -_words[0] : _words[0])
1278: : (_isNegative ? -((_words[1] << 63) | _words[0])
1279: : (_words[1] << 63) | _words[0]); // bitLength > 63 bits.
1280: }
1281:
1282: /**
1283: * Returns the value of this large integer as a <code>double</code>.
1284: *
1285: * @return the numeric value represented by this integer after conversion
1286: * to type <code>double</code>.
1287: */
1288: public double doubleValue() {
1289: if (_size == 0)
1290: return 0;
1291: if (_size <= 1)
1292: return _isNegative ? -_words[0] : _words[0];
1293:
1294: // Calculates bits length (ignores sign).
1295: final int n = _size - 1;
1296: final int bitLength = MathLib.bitLength(_words[n]) + (n << 6)
1297: - n;
1298:
1299: // Keep 63 most significant bits.
1300: int shift = 63 - bitLength;
1301: LargeInteger int63 = this .times2pow(shift);
1302: double d = MathLib.toDoublePow2(int63._words[0], -shift);
1303: return _isNegative ? -d : d;
1304: }
1305:
1306: /**
1307: * Compares two large integers numerically.
1308: *
1309: * @param that the integer to compare with.
1310: * @return -1, 0 or 1 as this integer is numerically less than, equal to,
1311: * or greater than <code>that</code>.
1312: * @throws ClassCastException <code>that</code> is not a
1313: * large integer.
1314: */
1315: public int compareTo(LargeInteger that) {
1316: // Compares sign.
1317: if (_isNegative && !that._isNegative)
1318: return -1;
1319: if (!_isNegative && that._isNegative)
1320: return 1;
1321: // Same sign, compares size.
1322: if (_size > that._size)
1323: return _isNegative ? -1 : 1;
1324: if (that._size > _size)
1325: return _isNegative ? 1 : -1;
1326: // Same size.
1327: return _isNegative ? compare(that._words, _words, _size)
1328: : compare(_words, that._words, _size);
1329: }
1330:
1331: /**
1332: * Compares this large integer to the specified <code>long</code> value.
1333: *
1334: * @param value the <code>long</code> value to compare with.
1335: * @return -1, 0 or 1 as this integer is numerically less than, equal to,
1336: * or greater than the specified value.
1337: */
1338: public int compareTo(long value) {
1339: if (_size > 1)
1340: return (value == Long.MAX_VALUE)
1341: && (this .equals(Long.MIN_VALUE)) ? 0
1342: : (_isNegative ? -1 : 1);
1343: // size <= 1
1344: long this Value = _isNegative ? -_words[0] : _words[0];
1345: return this Value < value ? -1 : ((this Value == value) ? 0 : 1);
1346: }
1347:
1348: @Override
1349: public LargeInteger copy() {
1350: LargeInteger li = ARRAY_FACTORY.array(_size);
1351: li._isNegative = _isNegative;
1352: li._size = _size;
1353: if (_size <= 1) {
1354: li._words[0] = _words[0];
1355: return li;
1356: }
1357: System.arraycopy(_words, 0, li._words, 0, _size);
1358: return li;
1359: }
1360:
1361: ////////////////////////
1362: // Parsing/Formatting //
1363: ////////////////////////
1364:
1365: /**
1366: * Returns the text representation of this number using the current
1367: * {@link TextFormat#getInstance(Class) format}.
1368: *
1369: * @return <code>TextFormat.getInstance(LargeInteger.class).format(this)</code>
1370: */
1371: public Text toText() {
1372: return TextFormat.getInstance(LargeInteger.class).format(this );
1373: }
1374:
1375: /**
1376: * Returns the text representation of this number in the specified radix.
1377: *
1378: * @param radix the radix of the representation.
1379: * @return the text representation of this number in the specified radix.
1380: */
1381: public Text toText(int radix) {
1382: TextBuilder tmp = TextBuilder.newInstance();
1383: try {
1384: format(this , radix, tmp);
1385: return tmp.toText();
1386: } catch (IOException e) {
1387: throw new Error(e);
1388: } finally {
1389: TextBuilder.recycle(tmp);
1390: }
1391: }
1392:
1393: /**
1394: * Parses the specified character sequence from the specified position
1395: * as a large integer in the specified radix.
1396: *
1397: * @param csq the character sequence to parse.
1398: * @param radix the radix to be used while parsing.
1399: * @param cursor the current cursor position (being maintained).
1400: * @return the corresponding large integer.
1401: * @throws NumberFormatException if error when parsing.
1402: */
1403: public static LargeInteger parse(CharSequence csq, int radix,
1404: Cursor cursor) {
1405: final int end = cursor.getEndIndex();
1406: boolean isNegative = cursor.at('-', csq);
1407: cursor.increment(isNegative || cursor.at('+', csq) ? 1 : 0);
1408: LargeInteger li = null;
1409: final int maxDigits = (radix <= 10) ? 18 : (radix <= 16) ? 15
1410: : 12;
1411: while (true) { // Reads up to digitsCount at a time.
1412: int start = cursor.getIndex();
1413: cursor.setEndIndex(MathLib.min(start + maxDigits, end));
1414: long l = TypeFormat.parseLong(csq, radix, cursor);
1415: int readCount = cursor.getIndex() - start;
1416: if (li == null) {
1417: li = LargeInteger.valueOf(l);
1418: } else {
1419: if (li._words.length < li._size + 2) { // Resizes.
1420: LargeInteger tmp = ARRAY_FACTORY
1421: .array(li._size + 2);
1422: System.arraycopy(li._words, 0, tmp._words, 0,
1423: li._size);
1424: tmp._isNegative = li._isNegative;
1425: tmp._size = li._size;
1426: li = tmp;
1427: }
1428: long factor = pow(radix, readCount);
1429: li._size = Calculus.multiply(li._words, li._size,
1430: factor, li._words);
1431: li._size = Calculus.add(li._words, li._size, l);
1432: }
1433: if (cursor.getIndex() == end)
1434: break; // Reached end.
1435: char c = csq.charAt(cursor.getIndex());
1436: int digit = (c <= '9') ? c - '0'
1437: : ((c <= 'Z') && (c >= 'A')) ? c - 'A' + 10
1438: : ((c <= 'z') && (c >= 'a')) ? c - 'a' + 10
1439: : -1;
1440: if ((digit < 0) || (digit >= radix))
1441: break; // No more digit.
1442: }
1443: cursor.setEndIndex(end); // Restore end index.
1444: return isNegative ? li.opposite() : li;
1445: }
1446:
1447: private static long pow(int radix, int n) {
1448: if (radix == 10)
1449: return LONG_POW_10[n];
1450: if (radix == 16)
1451: return LONG_POW_16[n];
1452: long l = 1;
1453: for (int i = 0; i < n; i++) {
1454: l *= radix;
1455: }
1456: return l;
1457: }
1458:
1459: private static final long[] LONG_POW_10 = new long[] { 1, 10, 100,
1460: 1000, 10000, 100000, 1000000, 10000000, 100000000,
1461: 1000000000, 10000000000L, 100000000000L, 1000000000000L,
1462: 10000000000000L, 100000000000000L, 1000000000000000L,
1463: 10000000000000000L, 100000000000000000L,
1464: 1000000000000000000L };
1465:
1466: private static final long[] LONG_POW_16 = new long[] { 0x1, 0x10,
1467: 0x100, 0x1000, 0x10000, 0x100000, 0x1000000, 0x10000000,
1468: 0x100000000L, 0x1000000000L, 0x10000000000L,
1469: 0x100000000000L, 0x1000000000000L, 0x10000000000000L,
1470: 0x100000000000000L, 0x1000000000000000L };
1471:
1472: /**
1473: * Formats the specified large integer in the specified radix and into
1474: * the specified <code>Appendable</code> argument.
1475: *
1476: * @param li the large integer to format.
1477: * @param radix the radix.
1478: * @param out the <code>Appendable</code> to append.
1479: * @return the specified <code>Appendable</code> object.
1480: * @throws IllegalArgumentException if radix is not in [2 .. 36] range.
1481: * @throws IOException if an I/O exception occurs.
1482: */
1483: public static Appendable format(LargeInteger li, int radix,
1484: Appendable out) throws IOException {
1485: if (li._isNegative) {
1486: out.append('-');
1487: }
1488: final int maxDigits = (radix <= 10) ? 9 : (radix <= 16) ? 7 : 5;
1489: return write(li.copy(), radix, (int) pow(radix, maxDigits), out);
1490: }
1491:
1492: private static Appendable write(LargeInteger li, int radix,
1493: int divisor, Appendable out) throws IOException {
1494: if (li._size <= 1) // Direct long formatting.
1495: return TypeFormat.format(li._size == 0 ? 0 : li._words[0],
1496: radix, out);
1497: int rem = (int) Calculus.divide(li._words, li._size, divisor,
1498: li._words);
1499: if (li._words[li._size - 1] == 0L) {
1500: li._size--;
1501: }
1502: write(li, radix, divisor, out); // Writes high.
1503: divisor /= radix;
1504: while (rem < divisor) {
1505: out.append('0');
1506: divisor /= radix;
1507: }
1508: return TypeFormat.format(rem, radix, out); // Writes low.
1509: }
1510:
1511: private static final long serialVersionUID = 1L;
1512: }
|