LargeInteger


1   /*
2    * JScience - Java(TM) Tools and Libraries for the Advancement of Sciences.
3    * Copyright (C) 2006 - JScience (http://jscience.org/)
4    * All rights reserved.
5    * 
6    * Permission to use, copy, modify, and distribute this software is
7    * freely granted, provided that this notice is preserved.
8    */
9   package org.jscience.mathematics.numbers;
10  
11  import java.io.IOException  ;
12  
13  import javolution.context.ConcurrentContext;
14  import javolution.context.PoolContext;
15  import javolution.context.PoolContext.Reference;
16  import javolution.context.ConcurrentContext.Logic;
17  import javolution.context.LocalContext;
18  import javolution.lang.MathLib;
19  import javolution.text.Text;
20  import javolution.text.TextBuilder;
21  import javolution.text.TextFormat;
22  import javolution.text.TypeFormat;
23  import javolution.xml.XMLFormat;
24  import javolution.xml.stream.XMLStreamException;
25  import static org.jscience.mathematics.numbers.Calculus.*;
26  
27  /**
28   * <p> This class represents an immutable integer number of arbitrary size.</p>
29   * 
30   * <p> It has the following advantages over the 
31   *     <code>java.math.BigInteger</code> class:
32   * <ul>
33   *     <li> Optimized for 64 bits architectures. But still runs significantly 
34   *          faster on 32 bits processors.</li>
35   *     <li> Real-time compliant for improved performance and predictability
36   *          (no garbage generated when executing in 
37   *          {@link javolution.context.PoolContext PoolContext}).</li>
38   *     <li> Improved algorithms (e.g. Concurrent Karabutsa multiplication in 
39   *          O(n<sup>Log3</sup>) instead of O(n<sup>2</sup>).</li>
40   * </ul></p>
41   * 
42   * <p> <b>Note:</b> This class uses {@link ConcurrentContext concurrent 
43   *     contexts} to accelerate calculations on multi-processors
44   *     systems. Numbers up to 64 KBits are allocated on the stack when 
45   *     executing in a {@link javolution.context.PoolContext PoolContext},
46   *     larger numbers are heap allocated.</p>
47   *     
48   * @author <a HREF="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle</a>
49   * @version 3.3, January 14, 2007
50   * @see <a HREF="http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic">
51   *      Wikipedia: Arbitrary-precision Arithmetic</a>
52   */
53  public final class LargeInteger extends Number  <LargeInteger> {
54  
55      /**
56       * Holds the {@link javolution.context.LocalContext context local} format 
57       * for large integers (decimal representation by default).
58       */
59      public static final LocalContext.Reference<TextFormat<LargeInteger>> FORMAT = new LocalContext.Reference<TextFormat<LargeInteger>>(
60              Format.INSTANCE);
61  
62      /**
63       * Holds the default XML representation for large integers.
64       * This representation consists of a simple <code>value</code> attribute
65       * holding the {@link #toText() textual} representation.
66       */
67      public static final XMLFormat<LargeInteger> XML = new XMLFormat<LargeInteger>(
68              LargeInteger.class) {
69  
70          @Override  
71          public LargeInteger newInstance(Class  <LargeInteger> cls,
72                  InputElement xml) throws XMLStreamException {
73              return LargeInteger.valueOf(xml.getAttribute("value"));
74          }
75  
76          public void write(LargeInteger li, OutputElement xml)
77                  throws XMLStreamException {
78              xml.setAttribute("value", li.toText());
79          }
80  
81          public void read(InputElement xml, LargeInteger li) {
82              // Nothing to do, immutable.
83          }
84      };
85  
86      /**
87       * The large integer representing the additive identity.
88       */
89      public static final LargeInteger ZERO = new LargeInteger(1);
90      static {
91          ZERO._size = 0;
92          ZERO._words[0] = 0;
93          // Note:  _words[0] == 0 for all zero values.
94      }
95  
96      /**
97       * The large integer representing the multiplicative identity.
98       */
99      public static final LargeInteger ONE = new LargeInteger(1);
100     static {
101         ONE._size = 1;
102         ONE._words[0] = 1;
103     }
104 
105     /**
106      * Holds the remainder after a {@link #divide} operation.
107      */
108     private LargeInteger _remainder;
109 
110     /**
111      * Indicates if this large integer is negative.
112      */
113     private boolean _isNegative;
114 
115     /**
116      * The size of this large integer in words. 
117      * The most significand word different from 0 is at index: _size-1
118      */
119     private int _size;
120 
121     /**
122      * This large integer positive words (63 bits). 
123      * Least significant word first (index 0).
124      */
125     private final long[] _words;
126 
127     /**
128      * Creates a large integer with the specified 63 bits word capacity.
129      * 
130      * @link wordLength the internal positive <code>long</code> array length.
131      */
132     private LargeInteger(int wordLength) {
133         _words = new long[wordLength];
134     }
135 
136     /**
137      * Returns the large integer of specified <code>long</code> value.
138      * 
139      * @param  value the <code>long</code> value.
140      * @return the corresponding large integernumber.
141      */
142     public static LargeInteger valueOf(long value) {
143         if (value == 0)
144             return LargeInteger.ZERO;
145         if (value == 1)
146             return LargeInteger.ONE;
147         if (value == Long.MIN_VALUE)
148             return LargeInteger.LONG_MIN_VALUE;
149         LargeInteger li = FACTORY_4.object();
150         boolean negative = li._isNegative = value < 0;
151         li._words[0] = negative ? -value : value;
152         li._size = 1;
153         return li;
154     }
155 
156     /**
157      * Returns the large integer of specified two's-complement binary
158      * representation. The input array is assumed to be in <i>big-endian</i>
159      * byte-order: the most significant byte is at the offset position.
160      * 
161      * <p>Note: This representation is consitent with <code>java.lang.BigInteger
162      *          </code> byte array representation and can be used for conversion 
163      *          between the two classes.</p>
164      * 
165      * @param  bytes the binary representation (two's-complement).
166      * @param  offset the offset at which to start reading the bytes.
167      * @param  length the maximum number of bytes to read.
168      * @return the corresponding large integer number.
169      * @throws IndexOutOfBoundsException 
170      *         if <code>offset + length > bytes.length</code>  
171      * @see    #toByteArray
172      */
173     public static LargeInteger valueOf(byte[] bytes, int offset, int length) {
174         // Ensures result is large enough (takes into account potential
175         // extra bits during negative to positive conversion).
176         LargeInteger z = LargeInteger.newInstance(((length * 8 + 1) / 63) + 1);
177         final boolean isNegative = bytes[offset] < 0;
178         int wordIndex = 0;
179         int bitIndex = 0;
180         z._words[0] = 0;
181         for (int i = offset + length; i > offset; bitIndex += 8) {
182             long bits = (isNegative ? ~bytes[--i] : bytes[--i]) & MASK_8;
183             if (bitIndex < 63 - 8) {
184                 z._words[wordIndex] |= bits << bitIndex;
185             } else { // End of word reached.
186                 z._words[wordIndex] |= (bits << bitIndex) & MASK_63;
187                 bitIndex -= 63; // In range [-8..-1]
188                 z._words[++wordIndex] = bits >> -bitIndex;
189             }
190         }
191         // Calculates size.
192         while (z._words[wordIndex] == 0) {
193             if (--wordIndex < 0) {
194                 break;
195             }
196         }
197         z._size = wordIndex + 1;
198         z._isNegative = isNegative;
199 
200         // Converts one's-complement to two's-complement if negative.
201         if (isNegative) { // Adds ONE.
202             if (z._size > 0) {
203                 z._size = add(z._words, z._size, ONE._words, 1, z._words);
204             } else {
205                 z._size = add(ONE._words, 1, z._words, 0, z._words);
206             }
207         }
208         return z;
209     }
210 
211     /**
212      * Returns the large integer for the specified character sequence in
213      * decimal number.
214      * 
215      * @param chars the character sequence.
216      * @return {@link #valueOf(CharSequence, int) valueOf(chars, 10)}
217      */
218     public static LargeInteger valueOf(CharSequence   chars) {
219         return FORMAT.get().parse(chars);
220     }
221 
222     /**
223      * Returns the large integer for the specified character sequence stated
224      * in the specified radix. The characters must all be digits of the
225      * specified radix, except the first character which may be a plus sign
226      * <code>'+'</code> or a minus sign <code>'-'</code>.
227      * 
228      * @param chars the character sequence to parse.
229      * @param radix the radix to be used while parsing.
230      * @return the corresponding large integer.
231      * @throws NumberFormatException if the specified character sequence does
232      *         not contain a parsable large integer.
233      */
234     public static LargeInteger valueOf(CharSequence   chars, int radix) {
235         TextFormat.Cursor cursor = TextFormat.Cursor.newInstance(0, chars
236                 .length());
237         LargeInteger li = Format.INSTANCE.parse(chars, radix, cursor);
238         TextFormat.Cursor.recycle(cursor);
239         return li;
240     }
241 
242     /**
243      * Returns the large integer corresponding to the specified 
244      * <code>java.math.BigInteger</code> instance.
245      * 
246      * @param  bigInteger the big integer instance.
247      * @return the large integer having the same value.
248      */
249     public static LargeInteger valueOf(java.math.BigInteger   bigInteger) {
250         byte[] bytes = bigInteger.toByteArray();
251         return LargeInteger.valueOf(bytes, 0, bytes.length);
252     }
253 
254     /**
255      * Indicates if this large integer is greater than {@link #ZERO}
256      * ({@link #ZERO}is not included).
257      * 
258      * @return <code>this > ZERO</code>
259      */
260     public boolean isPositive() {
261         return !_isNegative && (_size != 0);
262     }
263 
264     /**
265      * Indicates if this large integer is less than {@link #ZERO}.
266      * 
267      * @return <code>this < ZERO</code>
268      */
269     public boolean isNegative() {
270         return _isNegative;
271     }
272 
273     /**
274      * Indicates if this large integer is equal to {@link #ZERO}.
275      * 
276      * @return <code>this == ZERO</code>
277      */
278     public boolean isZero() {
279         return _size == 0;
280     }
281 
282     /**
283      * Returns the signum function of this large integer.
284      *
285      * @return -1, 0 or 1 as the value of this integer is negative, zero or
286      *         positive.
287      */
288     public int signum() {
289         return _isNegative ? -1 : (_size == 0) ? 0 : 1;
290     }
291 
292     /**
293      * Indicates if this large integer is an even number.
294      * 
295      * @return <code>(this & 1) == ZERO</code>
296      */
297     public boolean isEven() {
298         return (_words[0] & 1) == 0;
299     }
300 
301     /**
302      * Indicates if this large integer is an odd number.
303      * 
304      * @return <code>(this & 1) != ZERO</code>
305      */
306     public boolean isOdd() {
307         return (_words[0] & 1) != 0;
308     }
309 
310     /**
311      * Returns the minimal number of bits to represent this large integer
312      * in the minimal two's-complement (sign excluded).
313      * 
314      * @return the length of this integer in bits (sign excluded).
315      */
316     public int bitLength() {
317         if (_size == 0)
318             return 0;
319         final int n = _size - 1;
320         final int bitLength = MathLib.bitLength(_words[n]) + (n << 6) - n;
321         return (this.isNegative() && this.isPowerOfTwo()) ? bitLength - 1
322                 : bitLength;
323     }
324 
325     /**
326      * Returns the minimal number of decimal digits necessary to represent 
327      * this large integer (sign excluded).
328      * 
329      * @return the maximum number of digits.
330      */
331     public int digitLength() {
332         int bitLength = this.bitLength();
333         int min = (int) (bitLength * BITS_TO_DIGITS) + 1;
334         int max = (int) ((bitLength + 1) * BITS_TO_DIGITS) + 1;
335         if (min == max)
336             return min;
337         return (LargeInteger.ONE.times10pow(min + 1).isLargerThan(this)) ? min
338                 : min + 1;
339     }
340 
341     private static final double BITS_TO_DIGITS = MathLib.LOG2 / MathLib.LOG10;
342 
343     /**
344      * Indicates if this number is a power of two (equals to 2<sup>
345      * ({@link #bitLength bitLength()} - 1)</sup>).
346      * 
347      * @return <code>true</code> if this number is a power of two; 
348      *         <code>false</code> otherwise.
349      */
350     public boolean isPowerOfTwo() {
351         if (_size == 0)
352             return false;
353         final int n = _size - 1;
354         for (int j = 0; j < n; j++) {
355             if (_words[j] != 0)
356                 return false;
357         }
358         final int bitLength = MathLib.bitLength(_words[n]);
359         return _words[n] == (1L << (bitLength - 1));
360     }
361 
362     /**
363      * Returns the index of the lowest-order one bit in this large integer
364      * or <code>-1</code> if <code>this.equals(ZERO)</code>.
365      *
366      * @return the index of the rightmost bit set or <code>-1</code>
367      */
368     public int getLowestSetBit() {
369         if (_size == 0)
370             return -1;
371         for (int i = 0;; i++) {
372             long w = _words[i];
373             if (w == 0)
374                 continue;
375             for (int j = 0;; j++) {
376                 if (((1L << j) & w) != 0)
377                     return i * 63 + j;
378             }
379         }
380     }
381 
382     /**
383      * Returns the final undivided part after division that is less or of 
384      * lower degree than the divisor. This value is only set by the 
385      * {@link #divide} operation and is not considered as part of 
386      * this large integer (ignored by all methods).
387      * 
388      * @return the remainder of the division for which this large integer
389      *         is the quotient.
390      */
391     public LargeInteger getRemainder() {
392         return _remainder;
393     }
394 
395     /**
396      * Indicates if this large integer is larger than the one
397      * specified in absolute value.
398      * 
399      * @param that the integer to be compared with.
400      * @return <code>this.abs().compareTo(that.abs()) > 0</code>.
401      */
402     public boolean isLargerThan(LargeInteger that) {
403         return (this._size > that._size)
404                 || ((this._size == that._size) && Calculus.compare(this._words,
405                         that._words, this._size) > 0);
406     }
407 
408     /**
409      * Returns the two's-complement binary representation of this 
410      * large integer. The output array is in <i>big-endian</i>
411      * byte-order: the most significant byte is at the offset position.
412      * 
413      * <p>Note: This representation is consitent with <code>java.lang.BigInteger
414      *          </code> byte array representation and can be used for conversion 
415      *          between the two classes.</p>
416      * 
417      * @param  bytes the bytes to hold the binary representation 
418      *         (two's-complement) of this large integer.
419      * @param  offset the offset at which to start writing the bytes.
420      * @return the number of bytes written.
421      * @throws IndexOutOfBoundsException 
422      *         if <code>bytes.length < (bitLength() >> 3) + 1</code>  
423      * @see    #valueOf(byte[], int, int)
424      * @see    #bitLength
425      */
426     public int toByteArray(byte[] bytes, int offset) {
427         int bytesLength = (bitLength() >> 3) + 1;
428         int wordIndex = 0;
429         int bitIndex = 0;
430         if (_isNegative) {
431             long word = _words[0] - 1;
432             long borrow = word >> 63; // -1 if borrow
433             word = ~word & MASK_63;
434             for (int i = bytesLength + offset; i > offset; bitIndex += 8) {
435                 if (bitIndex < 63 - 8) {
436                     bytes[--i] = (byte) word;
437                     word >>= 8;
438                 } else { // End of word reached.
439                     byte bits = (byte) word;
440                     word = (++wordIndex < _size) ? _words[wordIndex] + borrow
441                             : borrow;
442                     borrow = word >> 63; // -1 if borrow
443                     word = ~word & MASK_63;
444                     bitIndex -= 63; // In range [-8..-1]
445                     bytes[--i] = (byte) ((word << -bitIndex) | bits);
446                     word >>= (8 + bitIndex);
447                 }
448             }
449         } else {
450             if (_size != 0) {
451                 long word = _words[0];
452                 for (int i = bytesLength + offset; i > offset; bitIndex += 8) {
453                     if (bitIndex < 63 - 8) {
454                         bytes[--i] = (byte) word;
455                         word >>= 8;
456                     } else { // End of word reached.
457                         byte bits = (byte) word;
458                         word = (++wordIndex < _size) ? _words[wordIndex] : 0;
459                         bitIndex -= 63; // In range [-8..-1]
460                         bytes[--i] = (byte) ((word << -bitIndex) | bits);
461                         word >>= (8 + bitIndex);
462                     }
463                 }
464             } else { // ZERO
465                 bytes[offset] = 0;
466             }
467         }
468         return bytesLength;
469     }
470 
471     /**
472      * Returns the opposite of this large integer.
473      * 
474      * @return <code>-this</code>.
475      */
476     public LargeInteger opposite() {
477         if (_size == 0)
478             return LargeInteger.ZERO;
479         LargeInteger li = LargeInteger.newInstance(_size);
480         System.arraycopy(_words, 0, li._words, 0, _size);
481         li._size = _size;
482         li._isNegative = !_isNegative;
483         return li;
484     }
485 
486     /**
487      * Returns the sum of this large integer with the specified 
488      * <code>long</code> integer.
489      * 
490      * @param value the <code>long</code> integer being added.
491      * @return <code>this + value</code>.
492      */
493     public LargeInteger plus(long value) {
494         return this.plus(LargeInteger.valueOf(value));
495     }
496 
497     /**
498      * Returns the sum of this large integer with the one specified.
499      * 
500      * @param that the integer to be added.
501      * @return <code>this + that</code>.
502      */
503     public LargeInteger plus(LargeInteger that) {
504         if (this._size < that._size) // Adds smallest in size to largest. 
505             return that.plus(this);
506         if ((this._isNegative != that._isNegative) && (that._size != 0))
507             return this.minus(that.opposite()); // Switches that sign.
508         LargeInteger li = LargeInteger.newInstance(_size + 1);
509         li._size = Calculus.add(_words, _size, that._words, that._size,
510                 li._words);
511         li._isNegative = _isNegative;
512         return li;
513     }
514 
515     /**
516      * Returns the difference between this large integer and the one
517      * specified.
518      * 
519      * @param that the integer to be subtracted.
520      * @return <code>this - that</code>.
521      */
522     public LargeInteger minus(LargeInteger that) {
523         if ((this._isNegative != that._isNegative) && (that._size != 0))
524             return this.plus(that.opposite()); // Switches that sign.
525         if (that.isLargerThan(this)) // Always subtract the smallest to the largest. 
526             return that.minus(this).opposite();
527         LargeInteger li = LargeInteger.newInstance(this._size);
528         li._size = Calculus.subtract(_words, _size, that._words, that._size,
529                 li._words);
530         li._isNegative = this._isNegative && (li._size != 0);
531         return li;
532     }
533 
534     /** 
535      * Returns the product of this large integer with the specified 
536      * <code>long</code> multiplier.
537      * 
538      * @param multiplier the <code>long</code> multiplier.
539      * @return <code>this · multiplier</code>.
540      */
541     public LargeInteger times(long multiplier) {
542         if ((this._size == 0) || (multiplier == 0))
543             return LargeInteger.ZERO;
544         if (multiplier < 0)
545             return ((multiplier == Long.MIN_VALUE) ? this.shiftLeft(63) : this
546                     .times(-multiplier)).opposite();
547         LargeInteger li = LargeInteger.newInstance(_size + 1);
548         li._size = Calculus.multiply(_words, _size, multiplier, li._words);
549         li._isNegative = _isNegative;
550         return li;
551     }
552 
553     /**
554      * Returns the product of this large integer with the one specified.
555      * 
556      * @param that the large integer multiplier.
557      * @return <code>this · that</code>.
558      */
559     public LargeInteger times(LargeInteger that) {
560         if (that._size > this._size) // Always multiply the smallest to the largest.
561             return that.times(this);
562         if (that._size <= 1) // Direct times(long) multiplication.
563             return this.times(that.longValue());
564         if (that._size < 10) { // Conventional multiplication.
565             LargeInteger li = LargeInteger.newInstance(this._size + that._size);
566             li._size = Calculus.multiply(this._words, this._size, that._words,
567                     that._size, li._words);
568             li._isNegative = (this._isNegative != that._isNegative);
569             return li;
570         } else if (that._size < 20) { // Karatsuba (sequential).
571             int n = (that._size >> 1) + (that._size & 1);
572             // this = a + 2^(n*63) b, that = c + 2^(n*63) d
573             LargeInteger b = this.high(n);
574             LargeInteger a = this.low(n);
575             // Optimization for square (a == c, b == d).
576             LargeInteger d = (this == that) ? b : that.high(n);
577             LargeInteger c = (this == that) ? a : that.low(n);
578             LargeInteger ab = a.plus(b);
579             LargeInteger cd = (this == that) ? ab : c.plus(d);
580             LargeInteger abcd = ab.times(cd);
581             LargeInteger ac = a.times(c);
582             LargeInteger bd = b.times(d);
583             // li = a*c + ((a+b)*(c+d)-(a*c+b*d)) 2^n + b*d 2^2n 
584             return ac.plus(abcd.minus(ac.plus(bd)).shiftWordLeft(n)).plus(
585                     bd.shiftWordLeft(n << 1));
586         } else { // Karatsuba (concurrent).
587             PoolContext.enter();
588             try {
589                 int n = (that._size >> 1) + (that._size & 1);
590                 // this = a + 2^(63*n) b, that = c + 2^(63*n) d
591                 LargeInteger b = this.high(n);
592                 LargeInteger a = this.low(n);
593                 // Optimization for square (a == c, b == d).
594                 LargeInteger d = (this == that) ? b : that.high(n);
595                 LargeInteger c = (this == that) ? a : that.low(n);
596                 LargeInteger ab = a.plus(b);
597                 LargeInteger cd = (this == that) ? ab : c.plus(d);
598                 Reference<LargeInteger> ac = Reference.newInstance();
599                 Reference<LargeInteger> bd = Reference.newInstance();
600                 Reference<LargeInteger> abcd = Reference.newInstance();
601                 ConcurrentContext.enter();
602                 try { // this = a + 2^n b,   that = c + 2^n d
603                     ConcurrentContext.execute(MULTIPLY, ab, cd, abcd);
604                     ConcurrentContext.execute(MULTIPLY, a, c, ac);
605                     ConcurrentContext.execute(MULTIPLY, b, d, bd);
606                 } finally {
607                     ConcurrentContext.exit();
608                 }
609                 // li = a*c + ((a+b)*(c+d)-(a*c+b*d)) 2^n + b*d 2^2n 
610                 LargeInteger li = ac.get().plus(
611                         abcd.get().minus(ac.get().plus(bd.get()))
612                                 .shiftWordLeft(n)).plus(
613                         bd.get().shiftWordLeft(n << 1));
614                 return li.export();
615             } finally {
616                 PoolContext.exit();
617             }
618         }
619     }
620 
621     private LargeInteger high(int w) { // this.shiftRight(w * 63)
622         LargeInteger li = LargeInteger.newInstance(_size - w);
623         li._isNegative = _isNegative;
624         li._size = _size - w;
625         System.arraycopy(_words, w, li._words, 0, _size - w);
626         return li;
627     }
628 
629     private LargeInteger low(int w) { // this.minus(high(w).shiftLeft(w * 63));
630         LargeInteger li = LargeInteger.newInstance(w);
631         li._isNegative = _isNegative;
632         System.arraycopy(_words, 0, li._words, 0, w);
633         for (int i = w; i > 0; i--) {
634             if (_words[i - 1] != 0) {
635                 li._size = i;
636                 return li;
637             }
638         } // Else zero.
639         return LargeInteger.ZERO;
640     }
641 
642     private LargeInteger shiftWordLeft(int w) { // this.minus(high(w).shiftLeft(w * 63));
643         if (_size == 0)
644             return LargeInteger.ZERO;
645         LargeInteger li = LargeInteger.newInstance(w + _size);
646         li._isNegative = _isNegative;
647         li._size = w + _size;
648         for (int i = 0; i < w;) {
649             li._words[i++] = 0;
650         }
651         System.arraycopy(_words, 0, li._words, w, _size);
652         return li;
653     }
654 
655     private static final Logic MULTIPLY = new Logic() {
656         public void run() {
657             LargeInteger left = getArgument(0);
658             LargeInteger right = getArgument(1);
659             PoolContext.Reference<LargeInteger> result = getArgument(2);
660             result.set(left.times(right));// Recursive.
661         }
662     };
663 
664     /**
665      * Returns this large integer divided by the specified <code>int</code>
666      * divisor. The remainder of this division is accessible using 
667      * {@link #getRemainder}. 
668      * 
669      * @param divisor the <code>int</code> divisor.
670      * @return <code>this / divisor</code> and <code>this % divisor</code>
671      *        ({@link #getRemainder})
672      * @throws ArithmeticException if <code>divisor == 0</code>
673      */
674     public LargeInteger divide(int divisor) {
675         if (divisor == 0)
676             throw new ArithmeticException  ("Division by zero");
677         if (divisor == Integer.MIN_VALUE) { // abs(divisor) would overflow.
678             LargeInteger li = this.times2pow(-31).copy();
679             li._isNegative = !_isNegative && (li._size != 0);
680             li._remainder = _isNegative ? LargeInteger
681                     .valueOf(-(_words[0] & MASK_31)) : LargeInteger
682                     .valueOf(_words[0] & MASK_31);
683             return li;
684         }
685         LargeInteger li = LargeInteger.newInstance(_size);
686         long rem = Calculus.divide(_words, _size, MathLib.abs(divisor),
687                 li._words);
688         li._size = (_size > 0) && (li._words[_size - 1] == 0L) ? _size - 1
689                 : _size;
690         li._isNegative = (_isNegative != (divisor < 0)) && (li._size != 0);
691         li._remainder = LargeInteger.valueOf(_isNegative ? -rem : rem);
692         return li;
693     }
694 
695     /**
696      * Returns this large integer divided by the one specified (integer
697      * division). The remainder of this division is accessible using 
698      * {@link #getRemainder}. 
699      * 
700      * @param that the integer divisor.
701      * @return <code>this / that</code> and <code>this % that</code> 
702      *        ({@link #getRemainder})
703      * @throws ArithmeticException if <code>that.equals(ZERO)</code>
704      */
705     public LargeInteger divide(LargeInteger that) {
706         if ((that._size <= 1) && ((that._words[0] >> 32) == 0))
707             return divide(that.intValue());
708         LargeInteger result;
709         LargeInteger remainder;
710         PoolContext.enter();
711         try {
712             LargeInteger thisAbs = this.abs();
713             LargeInteger thatAbs = that.abs();
714             int precision = thisAbs.bitLength() - thatAbs.bitLength() + 1;
715             if (precision <= 0) {
716                 result = LargeInteger.ZERO;
717                 remainder = this;
718             } else {
719                 LargeInteger thatReciprocal = thatAbs.inverseScaled(precision);
720                 result = thisAbs.times(thatReciprocal);
721                 result = result.shiftRight(thisAbs.bitLength() + 1);
722 
723                 // Calculates remainder, corrects for result +/- 1 error. 
724                 remainder = thisAbs.minus(thatAbs.times(result));
725                 if (remainder.compareTo(thatAbs) >= 0) {
726                     remainder = remainder.minus(thatAbs);
727                     result = result.plus(LargeInteger.ONE);
728                     if (remainder.compareTo(thatAbs) >= 0)
729                         throw new Error  ("Verification error for " + this + "/"
730                                 + that + ", please submit a bug report.");
731                 } else if (remainder.isNegative()) {
732                     remainder = remainder.plus(thatAbs);
733                     result = result.minus(ONE);
734                     if (remainder.isNegative())
735                         throw new Error  ("Verification error for " + this + "/"
736                                 + that + ", please submit a bug report.");
737                 }
738             }
739         } finally {
740             PoolContext.exit();
741         }
742         // Setups result and remainder.
743         LargeInteger li = result.copy();
744         li._isNegative = (this._isNegative != that._isNegative)
745                 && (result._size != 0);
746         li._remainder = remainder.copy();
747         li._remainder._isNegative = this._isNegative && (remainder._size != 0);
748         return li;
749     }
750 
751     /**
752      * Returns the remainder of the division of this large integer with 
753      * the one specified (convenience method equivalent to 
754      * <code>this.divide(that).getRemainder()</code>).
755      *
756      * @param that the value by which this integer is to be divided, and the
757      *        remainder returned.
758      * @return <code>this % that</code>
759      * @throws ArithmeticException if <code>that.equals(ZERO)</code>
760      * @see #divide(LargeInteger)
761      */
762     public LargeInteger remainder(LargeInteger that) {
763         return this.divide(that).getRemainder();
764     }
765 
766     /**
767      * Returns a scaled approximation of <code>1 / this</code>.
768      * 
769      * @param precision the requested precision (reciprocal error being ± 1).
770      * @return <code>2<sup>(precision + this.bitLength())</sup> / this</code>
771      * @throws ArithmeticException if <code>this.isZero()</code>
772      */
773     public LargeInteger inverseScaled(int precision) {
774         if (precision <= 30) { // Straight calculation.
775             long divisor = this.shiftRight(this.bitLength() - precision - 1)._words[0];
776             long dividend = 1L << (precision * 2 + 1);
777             return (this.isNegative()) ? LargeInteger.valueOf(-dividend
778                     / divisor) : LargeInteger.valueOf(dividend / divisor);
779         } else { // Newton iteration (x = 2 * x - x^2 * this).
780             LargeInteger x = inverseScaled(precision / 2 + 1); // Estimate.
781             LargeInteger thisTrunc = shiftRight(bitLength() - (precision + 2));
782             LargeInteger prod = thisTrunc.times(x).times(x);
783             int diff = 2 * (precision / 2 + 2);
784             LargeInteger prodTrunc = prod.shiftRight(diff);
785             LargeInteger xPad = x.shiftLeft(precision - precision / 2 - 1);
786             LargeInteger tmp = xPad.minus(prodTrunc);
787             return xPad.plus(tmp);
788         }
789     }
790 
791     /**
792      * Returns this large integer modulo the specified large integer. 
793      * 
794      * <p> Note: The result as the same sign as the divisor unlike the Java 
795      *     remainder (%) operator (which as the same sign as the dividend).</p> 
796      * 
797      * @param m the modulus.
798      * @return <code>this mod m</code>
799      * @see #getRemainder()
800      */
801     public LargeInteger mod(LargeInteger m) {
802         final LargeInteger li = m.isLargerThan(this) ? this : this.divide(m)
803                 .getRemainder();
804         return (this._isNegative == m._isNegative) ? li : li.plus(m);
805     }
806 
807     /**
808      * Returns the large integer whose value is <code>(this<sup>-1</sup> mod m)
809      * </code>.
810      *
811      * @param  m the modulus.
812      * @return <code>this<sup>-1</sup> mod m</code>.
813      * @throws ArithmeticException <code> m &lt;= 0</code>, or this integer
814      *         has no multiplicative inverse mod m (that is, this integer
815      *         is not <i>relatively prime</i> to m).
816      */
817     public LargeInteger modInverse(LargeInteger m) {
818         if (!m.isPositive())
819             throw new ArithmeticException  ("Modulus is not a positive number");
820         PoolContext.enter();
821         try {
822             // Extended Euclidian Algorithm
823             LargeInteger a = this;
824             LargeInteger b = m;
825             LargeInteger p = ONE;
826             LargeInteger q = ZERO;
827             LargeInteger r = ZERO;
828             LargeInteger s = ONE;
829             while (!b.isZero()) {
830                 LargeInteger quot = a.divide(b);
831                 LargeInteger c = quot.getRemainder();
832                 a = b;
833                 b = c;
834                 LargeInteger new_r = p.minus(quot.times(r));
835                 LargeInteger new_s = q.minus(quot.times(s));
836                 p = r;
837                 q = s;
838                 r = new_r;
839                 s = new_s;
840             }
841             if (!a.abs().equals(ONE)) // (a != 1) || (a != -1)
842                 throw new ArithmeticException  ("GCD(" + this + ", " + m + ") = "
843                         + a);
844             if (a.isNegative())
845                 return p.opposite().mod(m).export();
846             return p.mod(m).export();
847         } finally {
848             PoolContext.exit();
849         }
850     }
851 
852     /**
853      * Returns this large integer raised at the specified exponent modulo 
854      * the specified modulus.
855      *
856      * @param  exp the exponent.
857      * @param  m the modulus.
858      * @return <code>this<sup>exp</sup> mod m</code>
859      * @throws ArithmeticException <code>m &lt;= 0</code>
860      * @see    #modInverse
861      */
862     public LargeInteger modPow(LargeInteger exp, LargeInteger m) {
863         if (!m.isPositive())
864             throw new ArithmeticException  ("Modulus is not a positive number");
865         if (exp.isPositive()) {
866             PoolContext.enter();
867             try {
868                 LargeInteger pow2 = this.mod(m);
869                 LargeInteger result = null;
870                 while (exp.compareTo(ONE) >= 0) { // Iteration.
871                     if (exp.isOdd()) {
872                         result = (result == null) ? pow2 : result.times(pow2)
873                                 .mod(m);
874                     }
875                     pow2 = pow2.times(pow2).mod(m);
876                     exp = exp.shiftRight(1);
877                 }
878                 return result.export();
879             } finally {
880                 PoolContext.exit();
881             }
882         } else if (exp.isNegative()) {
883             return this.modPow(exp.opposite(), m).modInverse(m);
884         } else { // exp == 0
885             return LargeInteger.ONE;
886         }
887     }
888 
889     /**
890      * Returns the greatest common divisor of this large integer and 
891      * the one specified.
892      * 
893      * @param  that the other number to compute the GCD with.
894      * @return a positive number or {@link #ZERO} if
895      *         <code>(this.isZero() && that.isZero())</code>.
896      */
897     public LargeInteger gcd(LargeInteger that) {
898         if (this.isZero())
899             return that;
900         if (that.isZero())
901             return this;
902         // Works with local (modifiable) copies of the inputs.
903         LargeInteger u = this.copy();
904         u._isNegative = false; // abs()
905         LargeInteger v = that.copy();
906         v._isNegative = false; // abs()
907 
908         // Euclidian algorithm until u, v about the same size.
909         while (MathLib.abs(u._size - v._size) > 1) {
910             LargeInteger tmp = u.divide(v);
911             LargeInteger rem = tmp.getRemainder();
912             u = v;
913             v = rem;
914             if (v.isZero())
915                 return u;
916         }
917 
918         // Binary GCD Implementation adapted from
919         // http://en.wikipedia.org/wiki/Binary_GCD_algorithm
920         final int uShift = u.getLowestSetBit();
921         u.shiftRightSelf(uShift);
922         final int vShift = v.getLowestSetBit();
923         v.shiftRightSelf(vShift);
924 
925         // From here on, u is always odd.
926         while (true) {
927             // Now u and v are both odd, so diff(u, v) is even.
928             // Let u = min(u, v), v = diff(u, v)/2.
929             if (u.compareTo(v) < 0) {
930                 v.subtract(u);
931             } else {
932                 u.subtract(v);
933                 LargeInteger tmp = u;
934                 u = v;
935                 v = tmp; // Swaps. 
936             }
937             v.shiftRightSelf();
938             if (v.isZero())
939                 break;
940             v.shiftRightSelf(v.getLowestSetBit());
941         }
942         return u.shiftLeft(MathLib.min(uShift, vShift));
943     }
944 
945     private void shiftRightSelf() {
946         if (_size == 0)
947             return;
948         _size = Calculus.shiftRight(0, 1, _words, _size, _words);
949     }
950 
951     private void shiftRightSelf(int n) {
952         if ((n == 0) || (_size == 0))
953             return;
954         int wordShift = n < 63 ? 0 : n / 63;
955         int bitShift = n - ((wordShift << 6) - wordShift); // n - wordShift * 63
956         _size = Calculus.shiftRight(wordShift, bitShift, _words, _size, _words);
957     }
958 
959     private void subtract(LargeInteger that) { // this >= that
960         _size = Calculus.subtract(_words, _size, that._words, that._size,
961                 _words);
962     }
963 
964     /**
965      * Returns the absolute value of this large integer.
966      * 
967      * @return <code>|this|</code>.
968      */
969     public LargeInteger abs() {
970         if (_isNegative)
971             return this.opposite();
972         return this;
973     }
974 
975     /**
976      * Returns the value of this large integer after performing a binary
977      * shift to left. The shift distance, <code>n</code>, may be negative,
978      * in which case this method performs a right shift.
979      * 
980      * @param n the shift distance, in bits.
981      * @return <code>this &lt;&lt; n</code>.
982      * @see #shiftRight
983      */
984     public LargeInteger shiftLeft(int n) {
985         if (n < 0)
986             return shiftRight(-n);
987         if (_size == 0)
988             return LargeInteger.ZERO;
989         final int wordShift = n < 63 ? 0 : n / 63;
990         final int bitShift = n - wordShift * 63;
991         LargeInteger li = newInstance(_size + wordShift + 1);
992         li._isNegative = _isNegative;
993         li._size = Calculus.shiftLeft(wordShift, bitShift, _words, _size,
994                 li._words);
995         return li;
996     }
997 
998     /**
999      * Returns the value of this large integer after performing a binary
1000     * shift to right with sign extension <code>(-1 >> 1 == -1)</code>.
1001     * The shift distance, <code>n</code>, may be negative, in which case 
1002     * this method performs a {@link #shiftLeft(int)}.
1003     * 
1004     * @param n the shift distance, in bits.
1005     * @return <code>this &gt;&gt; n</code>.
1006     */
1007    public LargeInteger shiftRight(int n) {
1008        LargeInteger li = this.times2pow(-n);
1009        return (_isNegative) && (n > 0) && (isShiftRightCorrection(n)) ? li
1010                .minus(LargeInteger.ONE) : li;
1011    }
1012
1013    // Indicates if bits lost when shifting right the two's-complement
1014    // representation (affects only negative numbers).
1015    private boolean isShiftRightCorrection(int n) {
1016        int wordShift = n < 63 ? 0 : n / 63;
1017        int bitShift = n - ((wordShift << 6) - wordShift); // n - wordShift * 63
1018        int i = wordShift;
1019        boolean bitsLost = (bitShift != 0)
1020                && (_words[i] << (64 - bitShift)) != 0;
1021        while ((!bitsLost) && --i >= 0) {
1022            bitsLost = _words[i--] != 0;
1023        }
1024        return bitsLost;
1025    }
1026
1027    /**
1028     * Returns the value of this large integer after multiplication by 
1029     * a power of two. This method is equivalent to {@link #shiftLeft(int)}
1030     * for positive <code>n</code>; but is different from 
1031     * {@link #shiftRight(int)} for negative <code>n</code> as no sign 
1032     * extension is performed (<code>-1 >>> 1 == 0</code>).
1033     * 
1034     * @param n the power of 2 exponent.
1035     * @return <code>this · 2<sup>n</sup></code>.
1036     */
1037    public LargeInteger times2pow(int n) {
1038        if (n >= 0)
1039            return shiftLeft(n);
1040        n = -n; // Works with positive n.
1041        int wordShift = n < 63 ? 0 : n / 63;
1042        int bitShift = n - ((wordShift << 6) - wordShift); // n - wordShift * 63
1043        if (_size <= wordShift) // All bits have been shifted.
1044            return LargeInteger.ZERO;
1045        LargeInteger li = newInstance(_size - wordShift);
1046        li._size = Calculus.shiftRight(wordShift, bitShift, _words, _size,
1047                li._words);
1048        li._isNegative = _isNegative && (li._size != 0);
1049        return li;
1050    }
1051
1052    /**
1053     * Returns the value of this large integer after multiplication by 
1054     * a power of ten. For example:[code]
1055     *     LargeInteger billion = LargeInteger.ONE.times10pow(9); // 1E9
1056     *     LargeInteger million = billion.times10pow(-3);[/code]
1057     *
1058     * @param n the decimal exponent.
1059     * @return <code>this · 10<sup>n</sup></code>
1060     */
1061    public LargeInteger times10pow(int n) {
1062        if (this._size == 0)
1063            return LargeInteger.ZERO;
1064        if (n >= 0) {
1065            int bitLength = (int) (n * DIGITS_TO_BITS);
1066            LargeInteger li = newInstance(_size + (bitLength / 63) + 1); // Approx.
1067            li._isNegative = _isNegative;
1068            int i = (n >= LONG_POW_5.length) ? LONG_POW_5.length - 1 : n;
1069            li._size = Calculus.multiply(_words, _size, LONG_POW_5[i],
1070                    li._words);
1071            for (int j = n - i; j != 0; j -= i) {
1072                i = (j >= LONG_POW_5.length) ? LONG_POW_5.length - 1 : j;
1073                li._size = Calculus.multiply(li._words, li._size,
1074                        LONG_POW_5[i], li._words);
1075            }
1076            // Multiplies by 2^n
1077            final int wordShift = n < 63 ? 0 : n / 63;
1078            final int bitShift = n - ((wordShift << 6) - wordShift); // n - 63 * wordShift
1079            li._size = Calculus.shiftLeft(wordShift, bitShift, li._words,
1080                    li._size, li._words);
1081            return li;
1082        } else {// n < 0
1083            n = -n;
1084            // Divides by 2^n
1085            final int wordShift = n < 63 ? 0 : n / 63;
1086            final int bitShift = n - ((wordShift << 6) - wordShift); // n - 63 * wordShift
1087            if (_size <= wordShift) // All bits would be shifted. 
1088                return LargeInteger.ZERO;
1089            LargeInteger li = newInstance(_size - wordShift);
1090            li._size = Calculus.shiftRight(wordShift, bitShift, _words, _size,
1091                    li._words);
1092            for (int j = n; j != 0;) { // Divides by 5^n
1093                int i = (n >= INT_POW_5.length) ? INT_POW_5.length - 1 : n;
1094                Calculus.divide(li._words, li._size, INT_POW_5[i], li._words);
1095                if ((li._size > 0) && (li._words[li._size - 1] == 0L)) {
1096                    li._size--;
1097                }
1098                j -= i;
1099            }
1100            li._isNegative = _isNegative && (li._size != 0);
1101            return li;
1102        }
1103    }
1104
1105    private static double DIGITS_TO_BITS = MathLib.LOG10 / MathLib.LOG2;
1106
1107    private static int[] INT_POW_5 = new int[] { 1, 5, 25, 125, 625, 3125,
1108            15625, 78125, 390625, 1953125, 9765625, 48828125, 244140625,
1109            1220703125 };
1110
1111    private static long[] LONG_POW_5 = new long[] { 1L, 5L, 25L, 125L, 625L,
1112            3125L, 15625L, 78125L, 390625L, 1953125L, 9765625L, 48828125L,
1113            244140625L, 1220703125L, 6103515625L, 30517578125L, 152587890625L,
1114            762939453125L, 3814697265625L, 19073486328125L, 95367431640625L,
1115            476837158203125L, 2384185791015625L, 11920928955078125L,
1116            59604644775390625L, 298023223876953125L, 1490116119384765625L,
1117            7450580596923828125L };
1118
1119    /**
1120     * Returns the decimal text representation of this number.
1121     *
1122     * @return the text representation of this number.
1123     */
1124    public Text toText() {
1125        return FORMAT.get().format(this);
1126    }
1127
1128    /**
1129     * Returns the text representation of this number in the specified radix.
1130     *
1131     * @param radix the radix of the representation.
1132     * @return the text representation of this number.
1133     */
1134    public Text toText(int radix) {
1135        TextBuilder tmp = TextBuilder.newInstance();
1136        Format.INSTANCE.format(this, radix, tmp);
1137        Text txt = tmp.toText();
1138        TextBuilder.recycle(tmp);
1139        return txt;
1140    }
1141
1142    /**
1143     * Compares this large integer against the specified object.
1144     * 
1145     * @param that the object to compare with.
1146     * @return <code>true</code> if the objects are the same; <code>false</code>
1147     *         otherwise.
1148     */
1149    public boolean equals(Object   that) {
1150        if (!(that instanceof LargeInteger))
1151            return false;
1152        LargeInteger li = (LargeInteger) that;
1153        return (_size == li._size) && (_isNegative == li._isNegative)
1154                && (compare(_words, li._words, _size) == 0);
1155    }
1156
1157    /**
1158     * Returns the hash code for this large integer number.
1159     * 
1160     * @return the hash code value.
1161     */
1162    public int hashCode() {
1163        long code = 0;
1164        for (int i = _size - 1; i >= 0; i--) {
1165            code = code * 31 + _words[i];
1166        }
1167        return _isNegative ? -(int) code : (int) code;
1168    }
1169
1170    /**
1171     * Converts this large integer to <code>int</code>; unlike 
1172     * {@link #intValue} this method raises {@link ArithmeticException} if this 
1173     * integer cannot be represented by an <code>int</code> type.
1174     * 
1175     * @return the numeric value represented by this integer after conversion
1176     *         to type <code>int</code>.
1177     * @throws ArithmeticException if conversion to <code>int</code> is not 
1178     *         possible.
1179     */
1180    public int toInt() {
1181        if (((_size > 1) || (_words[0] > Integer.MAX_VALUE))
1182                && !this.equals(INT_MIN_VALUE))
1183            throw new ArithmeticException  (this
1184                    + " cannot be represented as int");
1185        return (int) longValue();
1186    }
1187
1188    /**
1189     * Converts this large integer to <code>long</code>; unlike 
1190     * {@link #longValue} this method raises {@link ArithmeticException} if this 
1191     * integer cannot be represented by a <code>long</code> type.
1192     * 
1193     * @return the numeric value represented by this integer after conversion
1194     *         to type <code>long</code>.
1195     * @throws ArithmeticException if conversion to <code>long</code> is not 
1196     *         possible.
1197     */
1198    public long toLong() {
1199        if ((_size > 1) && !this.equals(LONG_MIN_VALUE))
1200            throw new ArithmeticException  (this
1201                    + " cannot be represented as long");
1202        return longValue();
1203    }
1204
1205    /**
1206     * Returns the low order bits of this large integer as 
1207     * a <code>long</code>.
1208     * 
1209     * <p>Note: This conversion can lose information about the overall magnitude
1210     *          of the integer value and may return a result with the opposite 
1211     *          sign.</p>
1212     * 
1213     * @return the numeric value represented by this integer after conversion
1214     *         to type <code>long</code>.
1215     */
1216    public long longValue() {
1217        if (_size == 0)
1218            return 0;
1219        if (_size == 1)
1220            return _isNegative ? -_words[0] : _words[0];
1221        // bitLength > 63 bits.
1222        return _isNegative ? -((_words[1] << 63) | _words[0])
1223                : (_words[1] << 63) | _words[0];
1224    }
1225
1226    /**
1227     * Returns the value of this large integeras a <code>double</code>.
1228     * 
1229     * @return the numeric value represented by this integer after conversion
1230     *         to type <code>double</code>.
1231     */
1232    public double doubleValue() {
1233        if (_size == 0)
1234            return 0.0;
1235        if (_size == 1)
1236            return _isNegative ? -_words[0] : _words[0];
1237        // bitLength > 63
1238        int bitLength = this.bitLength();
1239        int pow2 = bitLength - 63;
1240        LargeInteger int63bits = this.shiftRight(pow2);
1241        double d = MathLib.toDoublePow2(int63bits._words[0], pow2);
1242        return _isNegative ? -d : d;
1243
1244    }
1245
1246    /**
1247     * Compares two large integers numerically.
1248     * 
1249     * @param  that the integer to compare with.
1250     * @return -1, 0 or 1 as this integer is numerically less than, equal to,
1251     *         or greater than <code>that</code>.
1252     * @throws ClassCastException <code>that</code> is not a 
1253     *         large integer.
1254     */
1255    public int compareTo(LargeInteger that) {
1256        // Compares sign.
1257        if (_isNegative && !that._isNegative)
1258            return -1;
1259        if (!_isNegative && that._isNegative)
1260            return 1;
1261        // Same sign, compares size.
1262        if (_size > that._size)
1263            return _isNegative ? -1 : 1;
1264        if (that._size > _size)
1265            return _isNegative ? 1 : -1;
1266        // Same size.
1267        return _isNegative ? compare(that._words, _words, _size) : compare(
1268                _words, that._words, _size);
1269    }
1270
1271    /**
1272     * Returns an exact copy of this large integer allocated on the 
1273     * stack when executing in a {@link PoolContext}).
1274     *
1275     * @return an exact copy of this large integer. 
1276     */
1277    public LargeInteger copy() {
1278        LargeInteger li = newInstance(_size);
1279        li._isNegative = _isNegative;
1280        li._size = _size;
1281        if (_size > 1) {
1282            System.arraycopy(_words, 0, li._words, 0, _size);
1283        } else {
1284            li._words[0] = _words[0]; // Ensures zero is correctly copied.
1285        }
1286        return li;
1287    }
1288
1289    /**
1290     * Returns the integer square root of this integer.
1291     * 
1292     * @return <code>k<code> such as <code>k^2 <= this < (k + 1)^2</code>
1293     * @throws ArithmeticException if this integer is negative.
1294     */
1295    public LargeInteger sqrt() {
1296        if (this.isNegative())
1297            throw new ArithmeticException  ("Square root of negative integer");
1298        int bitLength = this.bitLength();
1299        PoolContext.enter();
1300        try {
1301            // First approximation.
1302            LargeInteger k = this
1303                    .times2pow(-((bitLength >> 1) + (bitLength & 1)));
1304            while (true) {
1305                LargeInteger newK = (k.plus(this.divide(k))).times2pow(-1);
1306                if (newK.equals(k))
1307                    return k.export();
1308                k = newK;
1309            }
1310        } finally {
1311            PoolContext.exit();
1312        }
1313    }
1314
1315    ///////////////////////
1316    // Factory creation. //
1317    ///////////////////////
1318
1319    private static LargeInteger newInstance(int nbrWords) {
1320        return (nbrWords <= 4) ? FACTORY_4.object()
1321                : newLargeInstance(nbrWords);
1322    }
1323
1324    private static LargeInteger newLargeInstance(int nbrWords) {
1325        if (nbrWords <= 6)
1326            return FACTORY_6.object();
1327        if (nbrWords <= 10)
1328            return FACTORY_10.object();
1329        if (nbrWords <= 18)
1330            return FACTORY_18.object();
1331        if (nbrWords <= 34)
1332            return FACTORY_34.object();
1333        if (nbrWords <= 67)
1334            return FACTORY_67.object();
1335        if (nbrWords <= 132)
1336            return FACTORY_132.object();
1337        if (nbrWords <= 262)
1338            return FACTORY_262.object();
1339        if (nbrWords <= 522)
1340            return FACTORY_522.object();
1341        if (nbrWords <= 1042)
1342            return FACTORY_1042.object();
1343        return new LargeInteger(nbrWords); // Heap allocated.
1344    }
1345
1346    private static final Factory<LargeInteger> FACTORY_4 = new Factory<LargeInteger>() {
1347        @Override  
1348        protected LargeInteger create() {
1349            return new LargeInteger(4); // Ok for 128 bits additions.
1350        }
1351    };
1352
1353    private static final Factory<LargeInteger> FACTORY_6 = new Factory<LargeInteger>() {
1354        @Override  
1355        protected LargeInteger create() {
1356            return new LargeInteger(6); // Ok for 256 bits additions.
1357        }
1358    };
1359
1360    private static final Factory<LargeInteger> FACTORY_10 = new Factory<LargeInteger>() {
1361        @Override  
1362        protected LargeInteger create() {
1363            return new LargeInteger(10); // Ok for 512 bits additions.
1364        }
1365    };
1366
1367    private static final Factory<LargeInteger> FACTORY_18 = new Factory<LargeInteger>() {
1368        @Override  
1369        protected LargeInteger create() {
1370            return new LargeInteger(18); // Ok for 1024 bits additions.
1371        }
1372    };
1373
1374    private static final Factory<LargeInteger> FACTORY_34 = new Factory<LargeInteger>() {
1375        @Override  
1376        protected LargeInteger create() {
1377            return new LargeInteger(34); // Ok for 2048 bits additions.
1378        }
1379    };
1380
1381    private static final Factory<LargeInteger> FACTORY_67 = new Factory<LargeInteger>() {
1382        @Override  
1383        protected LargeInteger create() {
1384            return new LargeInteger(67); // Ok for 4096 bits additions.
1385        }
1386    };
1387
1388    private static final Factory<LargeInteger> FACTORY_132 = new Factory<LargeInteger>() {
1389        @Override  
1390        protected LargeInteger create() {
1391            return new LargeInteger(132); // Ok for 8192 bits additions.
1392        }
1393    };
1394
1395    private static final Factory<LargeInteger> FACTORY_262 = new Factory<LargeInteger>() {
1396        @Override  
1397        protected LargeInteger create() {
1398            return new LargeInteger(262); // Ok for 16384 bits additions.
1399        }
1400    };
1401
1402    private static final Factory<LargeInteger> FACTORY_522 = new Factory<LargeInteger>() {
1403        @Override  
1404        protected LargeInteger create() {
1405            return new LargeInteger(522); // Ok for 32768 bits additions.
1406        }
1407    };
1408
1409    private static final Factory<LargeInteger> FACTORY_1042 = new Factory<LargeInteger>() {
1410        @Override  
1411        protected LargeInteger create() {
1412            return new LargeInteger(1042); // Ok for 65536 bits additions.
1413        }
1414    };
1415
1416    private static final long serialVersionUID = 1L;
1417
1418    /**
1419     * This class represents a multi-radix format for {@link LargeInteger}.
1420     */
1421    static final class Format extends TextFormat<LargeInteger> {
1422
1423        private static Format INSTANCE = new Format();
1424
1425        Appendable   format(LargeInteger li, int radix, Appendable   out) {
1426            return null;
1427        }
1428
1429        LargeInteger parse(CharSequence   csq, int radix, Cursor cursor) {
1430            return null;
1431        }
1432
1433        @Override  
1434        public Appendable   format(LargeInteger li, Appendable   out)
1435                throws IOException   {
1436            if (li.isNegative()) {
1437                out.append('-');
1438            }
1439            LargeInteger tmp = li.copy();
1440            write(tmp, out);
1441            return out;
1442        }
1443
1444        // Recursive, writes 9 digits at a time.
1445        private void write(LargeInteger li, Appendable   out) throws IOException   {
1446            if ((li._size <= 1)) { // Direct long formatting.
1447                TypeFormat.format(li._words[0], out);
1448                return;
1449            }
1450            int rem = (int) Calculus.divide(li._words, li._size, 1000000000,
1451                    li._words);
1452            li._size = (li._words[li._size - 1] == 0L) ? li._size - 1
1453                    : li._size;
1454            write(li, out);
1455            for (int i = MathLib.digitLength(rem); i < 9; i++) {
1456                out.append('0');
1457            }
1458            TypeFormat.format(rem, out);
1459        }
1460
1461        @Override  
1462        public LargeInteger parse(CharSequence   csq, Cursor cursor) {
1463            final int end = cursor.getEndIndex();
1464            boolean isNegative = cursor.at('-', csq);
1465            cursor.increment(isNegative || cursor.at('+', csq) ? 1 : 0);
1466            LargeInteger li = ZERO.copy();
1467            while (true) { // Reads up to 18 digits at a time.
1468                int start = cursor.getIndex();
1469                cursor.setEndIndex(MathLib.min(start + 18, end));
1470                long l = TypeFormat.parseLong(csq, 10, cursor);
1471                LargeInteger tmp = li.times10pow(cursor.getIndex() - start);
1472                li = tmp.plus(l);
1473                if (cursor.getIndex() == end)
1474                    break; // Reached end.
1475                char c = csq.charAt(cursor.getIndex());
1476                if ((c < '0') || (c > '9'))
1477                    break; // No more digit.
1478            }
1479            cursor.setEndIndex(end); // Restore end index.
1480            li._isNegative = isNegative && (li._size != 0);
1481            return li;
1482        }
1483    }
1484
1485    /**
1486     * The large integer representing the minimum value representable as int.
1487     */
1488    private static final LargeInteger INT_MIN_VALUE = LargeInteger.ONE
1489            .shiftLeft(31).opposite().moveHeap();
1490
1491    /**
1492     * The large integer representing the minimum value representable as long.
1493     */
1494    private static final LargeInteger LONG_MIN_VALUE = LargeInteger.ONE
1495            .shiftLeft(63).opposite().moveHeap();
1496
1497}
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags