Source Code Cross Referenced for BigInteger.java in  » 6.0-JDK-Modules » j2me » java » math » Java Source Code / Java DocumentationJava Source Code and Java Documentation

Java Source Code / Java Documentation
1. 6.0 JDK Core
2. 6.0 JDK Modules
3. 6.0 JDK Modules com.sun
4. 6.0 JDK Modules com.sun.java
5. 6.0 JDK Modules sun
6. 6.0 JDK Platform
7. Ajax
8. Apache Harmony Java SE
9. Aspect oriented
10. Authentication Authorization
11. Blogger System
12. Build
13. Byte Code
14. Cache
15. Chart
16. Chat
17. Code Analyzer
18. Collaboration
19. Content Management System
20. Database Client
21. Database DBMS
22. Database JDBC Connection Pool
23. Database ORM
24. Development
25. EJB Server geronimo
26. EJB Server GlassFish
27. EJB Server JBoss 4.2.1
28. EJB Server resin 3.1.5
29. ERP CRM Financial
30. ESB
31. Forum
32. GIS
33. Graphic Library
34. Groupware
35. HTML Parser
36. IDE
37. IDE Eclipse
38. IDE Netbeans
39. Installer
40. Internationalization Localization
41. Inversion of Control
42. Issue Tracking
43. J2EE
44. JBoss
45. JMS
46. JMX
47. Library
48. Mail Clients
49. Net
50. Parser
51. PDF
52. Portal
53. Profiler
54. Project Management
55. Report
56. RSS RDF
57. Rule Engine
58. Science
59. Scripting
60. Search Engine
61. Security
62. Sevlet Container
63. Source Control
64. Swing Library
65. Template Engine
66. Test Coverage
67. Testing
68. UML
69. Web Crawler
70. Web Framework
71. Web Mail
72. Web Server
73. Web Services
74. Web Services apache cxf 2.0.1
75. Web Services AXIS2
76. Wiki Engine
77. Workflow Engines
78. XML
79. XML UI
Java
Java Tutorial
Java Open Source
Jar File Download
Java Articles
Java Products
Java by API
Photoshop Tutorials
Maya Tutorials
Flash Tutorials
3ds-Max Tutorials
Illustrator Tutorials
GIMP Tutorials
C# / C Sharp
C# / CSharp Tutorial
C# / CSharp Open Source
ASP.Net
ASP.NET Tutorial
JavaScript DHTML
JavaScript Tutorial
JavaScript Reference
HTML / CSS
HTML CSS Reference
C / ANSI-C
C Tutorial
C++
C++ Tutorial
Ruby
PHP
Python
Python Tutorial
Python Open Source
SQL Server / T-SQL
SQL Server / T-SQL Tutorial
Oracle PL / SQL
Oracle PL/SQL Tutorial
PostgreSQL
SQL / MySQL
MySQL Tutorial
VB.Net
VB.Net Tutorial
Flash / Flex / ActionScript
VBA / Excel / Access / Word
XML
XML Tutorial
Microsoft Office PowerPoint 2007 Tutorial
Microsoft Office Excel 2007 Tutorial
Microsoft Office Word 2007 Tutorial
Java Source Code / Java Documentation » 6.0 JDK Modules » j2me » java.math 
Source Cross Referenced  Class Diagram Java Document (Java Doc) 


0001:        /*
0002:         * @(#)BigInteger.java	1.47 06/10/23
0003:         *
0004:         * Copyright  1990-2006 Sun Microsystems, Inc. All Rights Reserved.  
0005:         * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER  
0006:         *   
0007:         * This program is free software; you can redistribute it and/or  
0008:         * modify it under the terms of the GNU General Public License version  
0009:         * 2 only, as published by the Free Software Foundation.   
0010:         *   
0011:         * This program is distributed in the hope that it will be useful, but  
0012:         * WITHOUT ANY WARRANTY; without even the implied warranty of  
0013:         * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU  
0014:         * General Public License version 2 for more details (a copy is  
0015:         * included at /legal/license.txt).   
0016:         *   
0017:         * You should have received a copy of the GNU General Public License  
0018:         * version 2 along with this work; if not, write to the Free Software  
0019:         * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  
0020:         * 02110-1301 USA   
0021:         *   
0022:         * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa  
0023:         * Clara, CA 95054 or visit www.sun.com if you need additional  
0024:         * information or have any questions. 
0025:         *
0026:         */
0027:
0028:        package java.math;
0029:
0030:        import java.util.Random;
0031:        import java.io.*;
0032:
0033:        /**
0034:         * Immutable arbitrary-precision integers.  All operations behave as if
0035:         * BigIntegers were represented in two's-complement notation (like Java's
0036:         * primitive integer types).  BigInteger provides analogues to all of Java's
0037:         * primitive integer operators, and all relevant methods from java.lang.Math.
0038:         * Additionally, BigInteger provides operations for modular arithmetic, GCD
0039:         * calculation, primality testing, prime generation, bit manipulation,
0040:         * and a few other miscellaneous operations.
0041:         * <p>
0042:         * Semantics of arithmetic operations exactly mimic those of Java's integer
0043:         * arithmetic operators, as defined in <i>The Java Language Specification</i>.
0044:         * For example, division by zero throws an <tt>ArithmeticException</tt>, and
0045:         * division of a negative by a positive yields a negative (or zero) remainder.
0046:         * All of the details in the Spec concerning overflow are ignored, as
0047:         * BigIntegers are made as large as necessary to accommodate the results of an
0048:         * operation.
0049:         * <p>
0050:         * Semantics of shift operations extend those of Java's shift operators
0051:         * to allow for negative shift distances.  A right-shift with a negative
0052:         * shift distance results in a left shift, and vice-versa.  The unsigned
0053:         * right shift operator (&gt;&gt;&gt;) is omitted, as this operation makes
0054:         * little sense in combination with the "infinite word size" abstraction
0055:         * provided by this class.
0056:         * <p>
0057:         * Semantics of bitwise logical operations exactly mimic those of Java's
0058:         * bitwise integer operators.  The binary operators (<tt>and</tt>,
0059:         * <tt>or</tt>, <tt>xor</tt>) implicitly perform sign extension on the shorter
0060:         * of the two operands prior to performing the operation.
0061:         * <p>
0062:         * Comparison operations perform signed integer comparisons, analogous to
0063:         * those performed by Java's relational and equality operators.
0064:         * <p>
0065:         * Modular arithmetic operations are provided to compute residues, perform
0066:         * exponentiation, and compute multiplicative inverses.  These methods always
0067:         * return a non-negative result, between <tt>0</tt> and <tt>(modulus - 1)</tt>,
0068:         * inclusive.
0069:         * <p>
0070:         * Bit operations operate on a single bit of the two's-complement
0071:         * representation of their operand.  If necessary, the operand is sign-
0072:         * extended so that it contains the designated bit.  None of the single-bit
0073:         * operations can produce a BigInteger with a different sign from the
0074:         * BigInteger being operated on, as they affect only a single bit, and the
0075:         * "infinite word size" abstraction provided by this class ensures that there
0076:         * are infinitely many "virtual sign bits" preceding each BigInteger.
0077:         * <p>
0078:         * For the sake of brevity and clarity, pseudo-code is used throughout the
0079:         * descriptions of BigInteger methods.  The pseudo-code expression
0080:         * <tt>(i + j)</tt> is shorthand for "a BigInteger whose value is
0081:         * that of the BigInteger <tt>i</tt> plus that of the BigInteger <tt>j</tt>."
0082:         * The pseudo-code expression <tt>(i == j)</tt> is shorthand for
0083:         * "<tt>true</tt> if and only if the BigInteger <tt>i</tt> represents the same
0084:         * value as the the BigInteger <tt>j</tt>."  Other pseudo-code expressions are
0085:         * interpreted similarly.
0086:         * <p>
0087:         * All methods and constructors in this class throw
0088:         * <CODE>NullPointerException</CODE> when passed
0089:         * a null object reference for any input parameter.
0090:         *
0091:         * @see     BigDecimal
0092:         * @version 1.36, 04/21/00
0093:         * @author  Josh Bloch
0094:         * @author  Michael McCloskey
0095:         * @since JDK1.1
0096:         */
0097:
0098:        public class BigInteger extends Number implements  Comparable {
0099:            /**
0100:             * The signum of this BigInteger: -1 for negative, 0 for zero, or
0101:             * 1 for positive.  Note that the BigInteger zero <i>must</i> have
0102:             * a signum of 0.  This is necessary to ensures that there is exactly one
0103:             * representation for each BigInteger value.
0104:             *
0105:             * @serial
0106:             */
0107:            int signum;
0108:
0109:            /**
0110:             * The magnitude of this BigInteger, in <i>big-endian</i> order: the
0111:             * zeroth element of this array is the most-significant int of the
0112:             * magnitude.  The magnitude must be "minimal" in that the most-significant
0113:             * int (<tt>mag[0]</tt>) must be non-zero.  This is necessary to
0114:             * ensure that there is exactly one representation for each BigInteger
0115:             * value.  Note that this implies that the BigInteger zero has a
0116:             * zero-length mag array.
0117:             */
0118:            transient int[] mag;
0119:
0120:            /**
0121:             * This field is required for historical reasons. The magnitude of a
0122:             * BigInteger used to be in a byte representation, and is still serialized
0123:             * that way. The mag field is used in all real computations but the
0124:             * magnitude field is required for storage.
0125:             *
0126:             * @serial
0127:             */
0128:            private byte[] magnitude;
0129:
0130:            // These "redundant fields" are initialized with recognizable nonsense
0131:            // values, and cached the first time they are needed (or never, if they
0132:            // aren't needed).
0133:
0134:            /**
0135:             * The bitCount of this BigInteger, as returned by bitCount(), or -1
0136:             * (either value is acceptable).
0137:             *
0138:             * @serial
0139:             * @see #bitCount
0140:             */
0141:            private int bitCount = -1;
0142:
0143:            /**
0144:             * The bitLength of this BigInteger, as returned by bitLength(), or -1
0145:             * (either value is acceptable).
0146:             *
0147:             * @serial
0148:             * @see #bitLength
0149:             */
0150:            private int bitLength = -1;
0151:
0152:            /**
0153:             * The lowest set bit of this BigInteger, as returned by getLowestSetBit(),
0154:             * or -2 (either value is acceptable).
0155:             *
0156:             * @serial
0157:             * @see #getLowestSetBit
0158:             */
0159:            private int lowestSetBit = -2;
0160:
0161:            /**
0162:             * The index of the lowest-order byte in the magnitude of this BigInteger
0163:             * that contains a nonzero byte, or -2 (either value is acceptable).  The
0164:             * least significant byte has int-number 0, the next byte in order of
0165:             * increasing significance has byte-number 1, and so forth.
0166:             *
0167:             * @serial
0168:             */
0169:            private int firstNonzeroByteNum = -2;
0170:
0171:            /**
0172:             * The index of the lowest-order int in the magnitude of this BigInteger
0173:             * that contains a nonzero int, or -2 (either value is acceptable).  The
0174:             * least significant int has int-number 0, the next int in order of
0175:             * increasing significance has int-number 1, and so forth.
0176:             */
0177:            private transient int firstNonzeroIntNum = -2;
0178:
0179:            /**
0180:             * This mask is used to obtain the value of an int as if it were unsigned.
0181:             */
0182:            private final static long LONG_MASK = 0xffffffffL;
0183:
0184:            //Constructors
0185:
0186:            /**
0187:             * Translates a byte array containing the two's-complement binary
0188:             * representation of a BigInteger into a BigInteger.  The input array is
0189:             * assumed to be in <i>big-endian</i> byte-order: the most significant
0190:             * byte is in the zeroth element.
0191:             *
0192:             * @param  val big-endian two's-complement binary representation of
0193:             *	       BigInteger.
0194:             * @throws NumberFormatException <tt>val</tt> is zero bytes long.
0195:             */
0196:            public BigInteger(byte[] val) {
0197:                if (val.length == 0)
0198:                    throw new NumberFormatException("Zero length BigInteger");
0199:
0200:                if (val[0] < 0) {
0201:                    mag = makePositive(val);
0202:                    signum = -1;
0203:                } else {
0204:                    mag = stripLeadingZeroBytes(val);
0205:                    signum = (mag.length == 0 ? 0 : 1);
0206:                }
0207:            }
0208:
0209:            /**
0210:             * This private constructor translates an int array containing the
0211:             * two's-complement binary representation of a BigInteger into a
0212:             * BigInteger. The input array is assumed to be in <i>big-endian</i>
0213:             * int-order: the most significant int is in the zeroth element.
0214:             */
0215:            private BigInteger(int[] val) {
0216:                if (val.length == 0)
0217:                    throw new NumberFormatException("Zero length BigInteger");
0218:
0219:                if (val[0] < 0) {
0220:                    mag = makePositive(val);
0221:                    signum = -1;
0222:                } else {
0223:                    mag = trustedStripLeadingZeroInts(val);
0224:                    signum = (mag.length == 0 ? 0 : 1);
0225:                }
0226:            }
0227:
0228:            /**
0229:             * Translates the sign-magnitude representation of a BigInteger into a
0230:             * BigInteger.  The sign is represented as an integer signum value: -1 for
0231:             * negative, 0 for zero, or 1 for positive.  The magnitude is a byte array
0232:             * in <i>big-endian</i> byte-order: the most significant byte is in the
0233:             * zeroth element.  A zero-length magnitude array is permissible, and will
0234:             * result in in a BigInteger value of 0, whether signum is -1, 0 or 1.
0235:             *
0236:             * @param  signum signum of the number (-1 for negative, 0 for zero, 1
0237:             * 	       for positive).
0238:             * @param  magnitude big-endian binary representation of the magnitude of
0239:             * 	       the number.
0240:             * @throws NumberFormatException <tt>signum</tt> is not one of the three
0241:             *	       legal values (-1, 0, and 1), or <tt>signum</tt> is 0 and
0242:             *	       <tt>magnitude</tt> contains one or more non-zero bytes.
0243:             */
0244:            public BigInteger(int signum, byte[] magnitude) {
0245:                this .mag = stripLeadingZeroBytes(magnitude);
0246:
0247:                if (signum < -1 || signum > 1)
0248:                    throw (new NumberFormatException("Invalid signum value"));
0249:
0250:                if (this .mag.length == 0) {
0251:                    this .signum = 0;
0252:                } else {
0253:                    if (signum == 0)
0254:                        throw (new NumberFormatException(
0255:                                "signum-magnitude mismatch"));
0256:                    this .signum = signum;
0257:                }
0258:            }
0259:
0260:            /**
0261:             * A constructor for internal use that translates the sign-magnitude
0262:             * representation of a BigInteger into a BigInteger. It checks the
0263:             * arguments and copies the magnitude so this constructor would be
0264:             * safe for external use.
0265:             */
0266:            private BigInteger(int signum, int[] magnitude) {
0267:                this .mag = stripLeadingZeroInts(magnitude);
0268:
0269:                if (signum < -1 || signum > 1)
0270:                    throw (new NumberFormatException("Invalid signum value"));
0271:
0272:                if (this .mag.length == 0) {
0273:                    this .signum = 0;
0274:                } else {
0275:                    if (signum == 0)
0276:                        throw (new NumberFormatException(
0277:                                "signum-magnitude mismatch"));
0278:                    this .signum = signum;
0279:                }
0280:            }
0281:
0282:            /**
0283:             * Translates the String representation of a BigInteger in the specified
0284:             * radix into a BigInteger.  The String representation consists of an
0285:             * optional minus sign followed by a sequence of one or more digits in the
0286:             * specified radix.  The character-to-digit mapping is provided by
0287:             * <tt>Character.digit</tt>.  The String may not contain any extraneous
0288:             * characters (whitespace, for example).
0289:             *
0290:             * @param val String representation of BigInteger.
0291:             * @param radix radix to be used in interpreting <tt>val</tt>.
0292:             * @throws NumberFormatException <tt>val</tt> is not a valid representation
0293:             *	       of a BigInteger in the specified radix, or <tt>radix</tt> is
0294:             *	       outside the range from {@link Character#MIN_RADIX} to
0295:             *	       {@link Character#MAX_RADIX}, inclusive.
0296:             * @see    Character#digit
0297:             */
0298:            public BigInteger(String val, int radix) {
0299:                int cursor = 0, numDigits;
0300:                int len = val.length();
0301:
0302:                if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
0303:                    throw new NumberFormatException("Radix out of range");
0304:                if (val.length() == 0)
0305:                    throw new NumberFormatException("Zero length BigInteger");
0306:
0307:                // Check for minus sign
0308:                signum = 1;
0309:                int index = val.indexOf('-');
0310:                if (index != -1) {
0311:                    if (index == 0) {
0312:                        if (val.length() == 1)
0313:                            throw new NumberFormatException(
0314:                                    "Zero length BigInteger");
0315:                        signum = -1;
0316:                        cursor = 1;
0317:                    } else {
0318:                        throw new NumberFormatException(
0319:                                "Illegal embedded minus sign");
0320:                    }
0321:                }
0322:
0323:                // Skip leading zeros and compute number of digits in magnitude
0324:                while (cursor < len
0325:                        && Character.digit(val.charAt(cursor), radix) == 0)
0326:                    cursor++;
0327:                if (cursor == len) {
0328:                    signum = 0;
0329:                    mag = ZERO.mag;
0330:                    return;
0331:                } else {
0332:                    numDigits = len - cursor;
0333:                }
0334:
0335:                // Pre-allocate array of expected size. May be too large but can
0336:                // never be too small. Typically exact.
0337:                int numBits = (int) (((numDigits * bitsPerDigit[radix]) >>> 10) + 1);
0338:                int numWords = (numBits + 31) / 32;
0339:                mag = new int[numWords];
0340:
0341:                // Process first (potentially short) digit group
0342:                int firstGroupLen = numDigits % digitsPerInt[radix];
0343:                if (firstGroupLen == 0)
0344:                    firstGroupLen = digitsPerInt[radix];
0345:                String group = val.substring(cursor, cursor += firstGroupLen);
0346:                mag[mag.length - 1] = Integer.parseInt(group, radix);
0347:                if (mag[mag.length - 1] < 0)
0348:                    throw new NumberFormatException("Illegal digit");
0349:
0350:                // Process remaining digit groups
0351:                int super Radix = intRadix[radix];
0352:                int groupVal = 0;
0353:                while (cursor < val.length()) {
0354:                    group = val
0355:                            .substring(cursor, cursor += digitsPerInt[radix]);
0356:                    groupVal = Integer.parseInt(group, radix);
0357:                    if (groupVal < 0)
0358:                        throw new NumberFormatException("Illegal digit");
0359:                    destructiveMulAdd(mag, super Radix, groupVal);
0360:                }
0361:                // Required for cases where the array was overallocated.
0362:                mag = trustedStripLeadingZeroInts(mag);
0363:            }
0364:
0365:            // Constructs a new BigInteger using a char array with radix=10
0366:            BigInteger(char[] val) {
0367:                int cursor = 0, numDigits;
0368:                int len = val.length;
0369:
0370:                // Check for leading minus sign
0371:                signum = 1;
0372:                if (val[0] == '-') {
0373:                    if (len == 1)
0374:                        throw new NumberFormatException(
0375:                                "Zero length BigInteger");
0376:                    signum = -1;
0377:                    cursor = 1;
0378:                }
0379:
0380:                // Skip leading zeros and compute number of digits in magnitude
0381:                while (cursor < len && Character.digit(val[cursor], 10) == 0)
0382:                    cursor++;
0383:                if (cursor == len) {
0384:                    signum = 0;
0385:                    mag = ZERO.mag;
0386:                    return;
0387:                } else {
0388:                    numDigits = len - cursor;
0389:                }
0390:
0391:                // Pre-allocate array of expected size
0392:                int numWords;
0393:                if (len < 10) {
0394:                    numWords = 1;
0395:                } else {
0396:                    int numBits = (int) (((numDigits * bitsPerDigit[10]) >>> 10) + 1);
0397:                    numWords = (numBits + 31) / 32;
0398:                }
0399:                mag = new int[numWords];
0400:
0401:                // Process first (potentially short) digit group
0402:                int firstGroupLen = numDigits % digitsPerInt[10];
0403:                if (firstGroupLen == 0)
0404:                    firstGroupLen = digitsPerInt[10];
0405:                mag[mag.length - 1] = parseInt(val, cursor,
0406:                        cursor += firstGroupLen);
0407:
0408:                // Process remaining digit groups
0409:                while (cursor < len) {
0410:                    int groupVal = parseInt(val, cursor,
0411:                            cursor += digitsPerInt[10]);
0412:                    destructiveMulAdd(mag, intRadix[10], groupVal);
0413:                }
0414:                mag = trustedStripLeadingZeroInts(mag);
0415:            }
0416:
0417:            // Create an integer with the digits between the two indexes
0418:            // Assumes start < end. The result may be negative, but it
0419:            // is to be treated as an unsigned value.
0420:            private int parseInt(char[] source, int start, int end) {
0421:                int result = Character.digit(source[start++], 10);
0422:                if (result == -1)
0423:                    throw new NumberFormatException(new String(source));
0424:
0425:                for (int index = start; index < end; index++) {
0426:                    int nextVal = Character.digit(source[index], 10);
0427:                    if (nextVal == -1)
0428:                        throw new NumberFormatException(new String(source));
0429:                    result = 10 * result + nextVal;
0430:                }
0431:
0432:                return result;
0433:            }
0434:
0435:            // bitsPerDigit in the given radix times 1024
0436:            // Rounded up to avoid underallocation.
0437:            private static long bitsPerDigit[] = { 0, 0, 1024, 1624, 2048,
0438:                    2378, 2648, 2875, 3072, 3247, 3402, 3543, 3672, 3790, 3899,
0439:                    4001, 4096, 4186, 4271, 4350, 4426, 4498, 4567, 4633, 4696,
0440:                    4756, 4814, 4870, 4923, 4975, 5025, 5074, 5120, 5166, 5210,
0441:                    5253, 5295 };
0442:
0443:            // Multiply x array times word y in place, and add word z
0444:            private static void destructiveMulAdd(int[] x, int y, int z) {
0445:                // Perform the multiplication word by word
0446:                long ylong = y & LONG_MASK;
0447:                long zlong = z & LONG_MASK;
0448:                int len = x.length;
0449:
0450:                long product = 0;
0451:                long carry = 0;
0452:                for (int i = len - 1; i >= 0; i--) {
0453:                    product = ylong * (x[i] & LONG_MASK) + carry;
0454:                    x[i] = (int) product;
0455:                    carry = product >>> 32;
0456:                }
0457:
0458:                // Perform the addition
0459:                long sum = (x[len - 1] & LONG_MASK) + zlong;
0460:                x[len - 1] = (int) sum;
0461:                carry = sum >>> 32;
0462:                for (int i = len - 2; i >= 0; i--) {
0463:                    sum = (x[i] & LONG_MASK) + carry;
0464:                    x[i] = (int) sum;
0465:                    carry = sum >>> 32;
0466:                }
0467:            }
0468:
0469:            /**
0470:             * Translates the decimal String representation of a BigInteger into a
0471:             * BigInteger.  The String representation consists of an optional minus
0472:             * sign followed by a sequence of one or more decimal digits.  The
0473:             * character-to-digit mapping is provided by <tt>Character.digit</tt>.
0474:             * The String may not contain any extraneous characters (whitespace, for
0475:             * example).
0476:             *
0477:             * @param val decimal String representation of BigInteger.
0478:             * @throws NumberFormatException <tt>val</tt> is not a valid representation
0479:             *	       of a BigInteger.
0480:             * @see    Character#digit
0481:             */
0482:            public BigInteger(String val) {
0483:                this (val, 10);
0484:            }
0485:
0486:            /**
0487:             * Constructs a randomly generated BigInteger, uniformly distributed over
0488:             * the range <tt>0</tt> to <tt>(2<sup>numBits</sup> - 1)</tt>, inclusive.
0489:             * The uniformity of the distribution assumes that a fair source of random
0490:             * bits is provided in <tt>rnd</tt>.  Note that this constructor always
0491:             * constructs a non-negative BigInteger.
0492:             *
0493:             * @param  numBits maximum bitLength of the new BigInteger.
0494:             * @param  rnd source of randomness to be used in computing the new
0495:             *	       BigInteger.
0496:             * @throws IllegalArgumentException <tt>numBits</tt> is negative.
0497:             * @see #bitLength
0498:             */
0499:            public BigInteger(int numBits, Random rnd) {
0500:                this (1, randomBits(numBits, rnd));
0501:            }
0502:
0503:            private static byte[] randomBits(int numBits, Random rnd) {
0504:                if (numBits < 0)
0505:                    throw new IllegalArgumentException(
0506:                            "numBits must be non-negative");
0507:                int numBytes = (numBits + 7) / 8;
0508:                byte[] randomBits = new byte[numBytes];
0509:
0510:                // Generate random bytes and mask out any excess bits
0511:                if (numBytes > 0) {
0512:                    rnd.nextBytes(randomBits);
0513:                    int excessBits = 8 * numBytes - numBits;
0514:                    randomBits[0] &= (1 << (8 - excessBits)) - 1;
0515:                }
0516:                return randomBits;
0517:            }
0518:
0519:            /**
0520:             * Constructs a randomly generated positive BigInteger that is probably
0521:             * prime, with the specified bitLength.<p>
0522:             *
0523:             * It is recommended that the {@link #probablePrime probablePrime}
0524:             * method be used in preference to this constructor unless there
0525:             * is a compelling need to specify a certainty.
0526:             *
0527:             * @param  bitLength bitLength of the returned BigInteger.
0528:             * @param  certainty a measure of the uncertainty that the caller is
0529:             *         willing to tolerate.  The probability that the new BigInteger
0530:             *	       represents a prime number will exceed
0531:             *	       <tt>(1 - 1/2<sup>certainty</sup></tt>).  The execution time of
0532:             *	       this constructor is proportional to the value of this parameter.
0533:             * @param  rnd source of random bits used to select candidates to be
0534:             *	       tested for primality.
0535:             * @throws ArithmeticException <tt>bitLength &lt; 2</tt>.
0536:             * @see    #bitLength
0537:             */
0538:            public BigInteger(int bitLength, int certainty, Random rnd) {
0539:                BigInteger prime;
0540:
0541:                if (bitLength < 2)
0542:                    throw new ArithmeticException("bitLength < 2");
0543:                // The cutoff of 95 was chosen empirically for best performance
0544:                prime = (bitLength < 95 ? smallPrime(bitLength, certainty, rnd)
0545:                        : largePrime(bitLength, certainty, rnd));
0546:                signum = 1;
0547:                mag = prime.mag;
0548:            }
0549:
0550:            // Minimum size in bits that the requested prime number has
0551:            // before we use the large prime number generating algorithms
0552:            private static final int SMALL_PRIME_THRESHOLD = 95;
0553:
0554:            /**
0555:             * Returns a positive BigInteger that is probably prime, with the
0556:             * specified bitLength. The probability that a BigInteger returned
0557:             * by this method is composite does not exceed 2<sup>-100</sup>.
0558:             *
0559:             * @param  bitLength bitLength of the returned BigInteger.
0560:             * @param  rnd source of random bits used to select candidates to be
0561:             *	       tested for primality.
0562:             * @return a BigInteger of <tt>bitLength</tt> bits that is probably prime
0563:             * @throws ArithmeticException <tt>bitLength &lt; 2</tt>.
0564:             * @see    #bitLength
0565:             */
0566:            private static BigInteger probablePrime(int bitLength, Random rnd) {
0567:                if (bitLength < 2)
0568:                    throw new ArithmeticException("bitLength < 2");
0569:
0570:                // The cutoff of 95 was chosen empirically for best performance
0571:                return (bitLength < SMALL_PRIME_THRESHOLD ? smallPrime(
0572:                        bitLength, 100, rnd) : largePrime(bitLength, 100, rnd));
0573:            }
0574:
0575:            /**
0576:             * Find a random number of the specified bitLength that is probably prime.
0577:             * This method is used for smaller primes, its performance degrades on
0578:             * larger bitlengths.
0579:             *
0580:             * This method assumes bitLength > 1.
0581:             */
0582:            private static BigInteger smallPrime(int bitLength, int certainty,
0583:                    Random rnd) {
0584:                int magLen = (bitLength + 31) >>> 5;
0585:                int temp[] = new int[magLen];
0586:                int highBit = 1 << ((bitLength + 31) & 0x1f); // High bit of high int
0587:                int highMask = (highBit << 1) - 1; // Bits to keep in high int
0588:
0589:                while (true) {
0590:                    // Construct a candidate
0591:                    for (int i = 0; i < magLen; i++)
0592:                        temp[i] = rnd.nextInt();
0593:                    temp[0] = (temp[0] & highMask) | highBit; // Ensure exact length
0594:                    if (bitLength > 2)
0595:                        temp[magLen - 1] |= 1; // Make odd if bitlen > 2
0596:
0597:                    BigInteger p = new BigInteger(temp, 1);
0598:
0599:                    // Do cheap "pre-test" if applicable
0600:                    if (bitLength > 6) {
0601:                        long r = p.remainder(SMALL_PRIME_PRODUCT).longValue();
0602:                        if ((r % 3 == 0) || (r % 5 == 0) || (r % 7 == 0)
0603:                                || (r % 11 == 0) || (r % 13 == 0)
0604:                                || (r % 17 == 0) || (r % 19 == 0)
0605:                                || (r % 23 == 0) || (r % 29 == 0)
0606:                                || (r % 31 == 0) || (r % 37 == 0)
0607:                                || (r % 41 == 0))
0608:                            continue; // Candidate is composite; try another
0609:                    }
0610:
0611:                    // All candidates of bitLength 2 and 3 are prime by this point
0612:                    if (bitLength < 4)
0613:                        return p;
0614:
0615:                    // Do expensive test if we survive pre-test (or it's inapplicable)
0616:                    if (p.primeToCertainty(certainty))
0617:                        return p;
0618:                }
0619:            }
0620:
0621:            private static final BigInteger SMALL_PRIME_PRODUCT = valueOf(3L
0622:                    * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41);
0623:
0624:            /**
0625:             * Find a random number of the specified bitLength that is probably prime.
0626:             * This method is more appropriate for larger bitlengths since it uses
0627:             * a sieve to eliminate most composites before using a more expensive
0628:             * test.
0629:             */
0630:            private static BigInteger largePrime(int bitLength, int certainty,
0631:                    Random rnd) {
0632:                BigInteger p;
0633:                p = new BigInteger(bitLength, rnd).setBit(bitLength - 1);
0634:                p.mag[p.mag.length - 1] &= 0xfffffffe;
0635:
0636:                // Use a sieve length likely to contain the next prime number
0637:                int searchLen = (bitLength / 20) * 64;
0638:                BitSieve searchSieve = new BitSieve(p, searchLen);
0639:                BigInteger candidate = searchSieve.retrieve(p, certainty);
0640:
0641:                while ((candidate == null)
0642:                        || (candidate.bitLength() != bitLength)) {
0643:                    p = p.add(BigInteger.valueOf(2 * searchLen));
0644:                    if (p.bitLength() != bitLength)
0645:                        p = new BigInteger(bitLength, rnd)
0646:                                .setBit(bitLength - 1);
0647:                    p.mag[p.mag.length - 1] &= 0xfffffffe;
0648:                    searchSieve = new BitSieve(p, searchLen);
0649:                    candidate = searchSieve.retrieve(p, certainty);
0650:                }
0651:                return candidate;
0652:            }
0653:
0654:            /**
0655:             * Returns <tt>true</tt> if this BigInteger is probably prime,
0656:             * <tt>false</tt> if it's definitely composite.
0657:             *
0658:             * This method assumes bitLength > 2.
0659:             *
0660:             * @param  certainty a measure of the uncertainty that the caller is
0661:             *	       willing to tolerate: if the call returns <tt>true</tt>
0662:             *	       the probability that this BigInteger is prime exceeds
0663:             *	       <tt>(1 - 1/2<sup>certainty</sup>)</tt>.  The execution time of
0664:             * 	       this method is proportional to the value of this parameter.
0665:             * @return <tt>true</tt> if this BigInteger is probably prime,
0666:             * 	       <tt>false</tt> if it's definitely composite.
0667:             */
0668:            boolean primeToCertainty(int certainty) {
0669:                int rounds = 0;
0670:                int n = (Math.min(certainty, Integer.MAX_VALUE - 1) + 1) / 2;
0671:
0672:                // The relationship between the certainty and the number of rounds
0673:                // we perform is given in the draft standard ANSI X9.80, "PRIME
0674:                // NUMBER GENERATION, PRIMALITY TESTING, AND PRIMALITY CERTIFICATES".
0675:                int sizeInBits = this .bitLength();
0676:                if (sizeInBits < 100) {
0677:                    rounds = 50;
0678:                    rounds = n < rounds ? n : rounds;
0679:                    return passesMillerRabin(rounds);
0680:                }
0681:
0682:                if (sizeInBits < 256) {
0683:                    rounds = 27;
0684:                } else if (sizeInBits < 512) {
0685:                    rounds = 15;
0686:                } else if (sizeInBits < 768) {
0687:                    rounds = 8;
0688:                } else if (sizeInBits < 1024) {
0689:                    rounds = 4;
0690:                } else {
0691:                    rounds = 2;
0692:                }
0693:                rounds = n < rounds ? n : rounds;
0694:
0695:                return passesMillerRabin(rounds) && passesLucasLehmer();
0696:            }
0697:
0698:            /**
0699:             * Returns true iff this BigInteger is a Lucas-Lehmer probable prime.
0700:             *
0701:             * The following assumptions are made:
0702:             * This BigInteger is a positive, odd number.
0703:             */
0704:            private boolean passesLucasLehmer() {
0705:                BigInteger this PlusOne = this .add(ONE);
0706:
0707:                // Step 1
0708:                int d = 5;
0709:                while (jacobiSymbol(d, this ) != -1) {
0710:                    // 5, -7, 9, -11, ...
0711:                    d = (d < 0) ? Math.abs(d) + 2 : -(d + 2);
0712:                }
0713:
0714:                // Step 2
0715:                BigInteger u = lucasLehmerSequence(d, this PlusOne, this );
0716:
0717:                // Step 3
0718:                return u.mod(this ).equals(ZERO);
0719:            }
0720:
0721:            /**
0722:             * Computes Jacobi(p,n).
0723:             * Assumes n is positive, odd.
0724:             */
0725:            int jacobiSymbol(int p, BigInteger n) {
0726:                if (p == 0)
0727:                    return 0;
0728:
0729:                // Algorithm and comments adapted from Colin Plumb's C library.
0730:                int j = 1;
0731:                int u = n.mag[n.mag.length - 1];
0732:
0733:                // Make p positive
0734:                if (p < 0) {
0735:                    p = -p;
0736:                    int n8 = u & 7;
0737:                    if ((n8 == 3) || (n8 == 7))
0738:                        j = -j; // 3 (011) or 7 (111) mod 8
0739:                }
0740:
0741:                // Get rid of factors of 2 in p
0742:                while ((p & 3) == 0)
0743:                    p >>= 2;
0744:                if ((p & 1) == 0) {
0745:                    p >>= 1;
0746:                    if (((u ^ u >> 1) & 2) != 0)
0747:                        j = -j; // 3 (011) or 5 (101) mod 8
0748:                }
0749:                if (p == 1)
0750:                    return j;
0751:                // Then, apply quadratic reciprocity
0752:                if ((p & u & 2) != 0) // p = u = 3 (mod 4)?
0753:                    j = -j;
0754:                // And reduce u mod p
0755:                u = n.mod(BigInteger.valueOf(p)).intValue();
0756:
0757:                // Now compute Jacobi(u,p), u < p
0758:                while (u != 0) {
0759:                    while ((u & 3) == 0)
0760:                        u >>= 2;
0761:                    if ((u & 1) == 0) {
0762:                        u >>= 1;
0763:                        if (((p ^ p >> 1) & 2) != 0)
0764:                            j = -j; // 3 (011) or 5 (101) mod 8
0765:                    }
0766:                    if (u == 1)
0767:                        return j;
0768:                    // Now both u and p are odd, so use quadratic reciprocity
0769:                    if (u < p) {
0770:                        int t = u;
0771:                        u = p;
0772:                        p = t;
0773:                        if ((u & p & 2) != 0)// u = p = 3 (mod 4)?
0774:                            j = -j;
0775:                    }
0776:                    // Now u >= p, so it can be reduced
0777:                    u %= p;
0778:                }
0779:                return 0;
0780:            }
0781:
0782:            private static BigInteger lucasLehmerSequence(int z, BigInteger k,
0783:                    BigInteger n) {
0784:                BigInteger d = BigInteger.valueOf(z);
0785:                BigInteger u = ONE;
0786:                BigInteger u2;
0787:                BigInteger v = ONE;
0788:                BigInteger v2;
0789:
0790:                for (int i = k.bitLength() - 2; i >= 0; i--) {
0791:                    u2 = u.multiply(v).mod(n);
0792:
0793:                    v2 = v.square().add(d.multiply(u.square())).mod(n);
0794:                    if (v2.testBit(0)) {
0795:                        v2 = n.subtract(v2);
0796:                        v2.signum = -v2.signum;
0797:                    }
0798:                    v2 = v2.shiftRight(1);
0799:
0800:                    u = u2;
0801:                    v = v2;
0802:                    if (k.testBit(i)) {
0803:                        u2 = u.add(v).mod(n);
0804:                        if (u2.testBit(0)) {
0805:                            u2 = n.subtract(u2);
0806:                            u2.signum = -u2.signum;
0807:                        }
0808:                        u2 = u2.shiftRight(1);
0809:
0810:                        v2 = v.add(d.multiply(u)).mod(n);
0811:                        if (v2.testBit(0)) {
0812:                            v2 = n.subtract(v2);
0813:                            v2.signum = -v2.signum;
0814:                        }
0815:                        v2 = v2.shiftRight(1);
0816:
0817:                        u = u2;
0818:                        v = v2;
0819:                    }
0820:                }
0821:                return u;
0822:            }
0823:
0824:            /**
0825:             * Returns true iff this BigInteger passes the specified number of
0826:             * Miller-Rabin tests. This test is taken from the DSA spec (NIST FIPS
0827:             * 186-2).
0828:             *
0829:             * The following assumptions are made:
0830:             * This BigInteger is a positive, odd number greater than 2.
0831:             * iterations<=50.
0832:             */
0833:            private boolean passesMillerRabin(int iterations) {
0834:                // Find a and m such that m is odd and this == 1 + 2**a * m
0835:                BigInteger this MinusOne = this .subtract(ONE);
0836:                BigInteger m = this MinusOne;
0837:                int a = m.getLowestSetBit();
0838:                m = m.shiftRight(a);
0839:
0840:                // Do the tests
0841:                Random rnd = new Random();
0842:                for (int i = 0; i < iterations; i++) {
0843:                    // Generate a uniform random on (1, this)
0844:                    BigInteger b;
0845:                    do {
0846:                        b = new BigInteger(this .bitLength(), rnd);
0847:                    } while (b.compareTo(ONE) <= 0 || b.compareTo(this ) >= 0);
0848:
0849:                    int j = 0;
0850:                    BigInteger z = b.modPow(m, this );
0851:                    while (!((j == 0 && z.equals(ONE)) || z
0852:                            .equals(this MinusOne))) {
0853:                        if (j > 0 && z.equals(ONE) || ++j == a)
0854:                            return false;
0855:                        z = z.modPow(TWO, this );
0856:                    }
0857:                }
0858:                return true;
0859:            }
0860:
0861:            /**
0862:             * This private constructor differs from its public cousin
0863:             * with the arguments reversed in two ways: it assumes that its
0864:             * arguments are correct, and it doesn't copy the magnitude array.
0865:             */
0866:            private BigInteger(int[] magnitude, int signum) {
0867:                this .signum = (magnitude.length == 0 ? 0 : signum);
0868:                this .mag = magnitude;
0869:            }
0870:
0871:            /**
0872:             * This private constructor is for internal use and assumes that its
0873:             * arguments are correct.
0874:             */
0875:            private BigInteger(byte[] magnitude, int signum) {
0876:                this .signum = (magnitude.length == 0 ? 0 : signum);
0877:                this .mag = stripLeadingZeroBytes(magnitude);
0878:            }
0879:
0880:            /**
0881:             * This private constructor is for internal use in converting
0882:             * from a MutableBigInteger object into a BigInteger.
0883:             */
0884:            BigInteger(MutableBigInteger val, int sign) {
0885:                if (val.offset > 0 || val.value.length != val.intLen) {
0886:                    mag = new int[val.intLen];
0887:                    for (int i = 0; i < val.intLen; i++)
0888:                        mag[i] = val.value[val.offset + i];
0889:                } else {
0890:                    mag = val.value;
0891:                }
0892:
0893:                this .signum = (val.intLen == 0) ? 0 : sign;
0894:            }
0895:
0896:            //Static Factory Methods
0897:
0898:            /**
0899:             * Returns a BigInteger whose value is equal to that of the
0900:             * specified <code>long</code>.  This "static factory method" is
0901:             * provided in preference to a (<code>long</code>) constructor
0902:             * because it allows for reuse of frequently used BigIntegers.
0903:             *
0904:             * @param  val value of the BigInteger to return.
0905:             * @return a BigInteger with the specified value.
0906:             */
0907:            public static BigInteger valueOf(long val) {
0908:                // If -MAX_CONSTANT < val < MAX_CONSTANT, return stashed constant
0909:                if (val == 0)
0910:                    return ZERO;
0911:                if (val > 0 && val <= MAX_CONSTANT)
0912:                    return posConst[(int) val];
0913:                else if (val < 0 && val >= -MAX_CONSTANT)
0914:                    return negConst[(int) -val];
0915:
0916:                return new BigInteger(val);
0917:            }
0918:
0919:            /**
0920:             * Constructs a BigInteger with the specified value, which may not be zero.
0921:             */
0922:            private BigInteger(long val) {
0923:                if (val < 0) {
0924:                    signum = -1;
0925:                    val = -val;
0926:                } else {
0927:                    signum = 1;
0928:                }
0929:
0930:                int highWord = (int) (val >>> 32);
0931:                if (highWord == 0) {
0932:                    mag = new int[1];
0933:                    mag[0] = (int) val;
0934:                } else {
0935:                    mag = new int[2];
0936:                    mag[0] = highWord;
0937:                    mag[1] = (int) val;
0938:                }
0939:            }
0940:
0941:            /**
0942:             * Returns a BigInteger with the given two's complement representation.
0943:             * Assumes that the input array will not be modified (the returned
0944:             * BigInteger will reference the input array if feasible).
0945:             */
0946:            private static BigInteger valueOf(int val[]) {
0947:                return (val[0] > 0 ? new BigInteger(val, 1) : new BigInteger(
0948:                        val));
0949:            }
0950:
0951:            // Constants
0952:
0953:            /**
0954:             * Initialize static constant array when class is loaded.
0955:             */
0956:            private final static int MAX_CONSTANT = 16;
0957:            private static BigInteger posConst[] = new BigInteger[MAX_CONSTANT + 1];
0958:            private static BigInteger negConst[] = new BigInteger[MAX_CONSTANT + 1];
0959:            static {
0960:                for (int i = 1; i <= MAX_CONSTANT; i++) {
0961:                    int[] magnitude = new int[1];
0962:                    magnitude[0] = (int) i;
0963:                    posConst[i] = new BigInteger(magnitude, 1);
0964:                    negConst[i] = new BigInteger(magnitude, -1);
0965:                }
0966:            }
0967:
0968:            /**
0969:             * The BigInteger constant zero.
0970:             *
0971:             * @since   1.2
0972:             */
0973:            public static final BigInteger ZERO = new BigInteger(new int[0], 0);
0974:
0975:            /**
0976:             * The BigInteger constant one.
0977:             *
0978:             * @since   1.2
0979:             */
0980:            public static final BigInteger ONE = valueOf(1);
0981:
0982:            /**
0983:             * The BigInteger constant two.  (Not exported.)
0984:             */
0985:            private static final BigInteger TWO = valueOf(2);
0986:
0987:            // Arithmetic Operations
0988:
0989:            /**
0990:             * Returns a BigInteger whose value is <tt>(this + val)</tt>.
0991:             *
0992:             * @param  val value to be added to this BigInteger.
0993:             * @return <tt>this + val</tt>
0994:             */
0995:            public BigInteger add(BigInteger val) {
0996:                int[] resultMag;
0997:                if (val.signum == 0)
0998:                    return this ;
0999:                if (signum == 0)
1000:                    return val;
1001:                if (val.signum == signum)
1002:                    return new BigInteger(add(mag, val.mag), signum);
1003:
1004:                int cmp = intArrayCmp(mag, val.mag);
1005:                if (cmp == 0)
1006:                    return ZERO;
1007:                resultMag = (cmp > 0 ? subtract(mag, val.mag) : subtract(
1008:                        val.mag, mag));
1009:                resultMag = trustedStripLeadingZeroInts(resultMag);
1010:
1011:                return new BigInteger(resultMag, cmp * signum);
1012:            }
1013:
1014:            /**
1015:             * Adds the contents of the int arrays x and y. This method allocates
1016:             * a new int array to hold the answer and returns a reference to that
1017:             * array.
1018:             */
1019:            private static int[] add(int[] x, int[] y) {
1020:                // If x is shorter, swap the two arrays
1021:                if (x.length < y.length) {
1022:                    int[] tmp = x;
1023:                    x = y;
1024:                    y = tmp;
1025:                }
1026:
1027:                int xIndex = x.length;
1028:                int yIndex = y.length;
1029:                int result[] = new int[xIndex];
1030:                long sum = 0;
1031:
1032:                // Add common parts of both numbers
1033:                while (yIndex > 0) {
1034:                    sum = (x[--xIndex] & LONG_MASK) + (y[--yIndex] & LONG_MASK)
1035:                            + (sum >>> 32);
1036:                    result[xIndex] = (int) sum;
1037:                }
1038:
1039:                // Copy remainder of longer number while carry propagation is required
1040:                boolean carry = (sum >>> 32 != 0);
1041:                while (xIndex > 0 && carry)
1042:                    carry = ((result[--xIndex] = x[xIndex] + 1) == 0);
1043:
1044:                // Copy remainder of longer number
1045:                while (xIndex > 0)
1046:                    result[--xIndex] = x[xIndex];
1047:
1048:                // Grow result if necessary
1049:                if (carry) {
1050:                    int newLen = result.length + 1;
1051:                    int temp[] = new int[newLen];
1052:                    for (int i = 1; i < newLen; i++)
1053:                        temp[i] = result[i - 1];
1054:                    temp[0] = 0x01;
1055:                    result = temp;
1056:                }
1057:                return result;
1058:            }
1059:
1060:            /**
1061:             * Returns a BigInteger whose value is <tt>(this - val)</tt>.
1062:             *
1063:             * @param  val value to be subtracted from this BigInteger.
1064:             * @return <tt>this - val</tt>
1065:             */
1066:            public BigInteger subtract(BigInteger val) {
1067:                int[] resultMag;
1068:                if (val.signum == 0)
1069:                    return this ;
1070:                if (signum == 0)
1071:                    return val.negate();
1072:                if (val.signum != signum)
1073:                    return new BigInteger(add(mag, val.mag), signum);
1074:
1075:                int cmp = intArrayCmp(mag, val.mag);
1076:                if (cmp == 0)
1077:                    return ZERO;
1078:                resultMag = (cmp > 0 ? subtract(mag, val.mag) : subtract(
1079:                        val.mag, mag));
1080:                resultMag = trustedStripLeadingZeroInts(resultMag);
1081:                return new BigInteger(resultMag, cmp * signum);
1082:            }
1083:
1084:            /**
1085:             * Subtracts the contents of the second int arrays (little) from the
1086:             * first (big).  The first int array (big) must represent a larger number
1087:             * than the second.  This method allocates the space necessary to hold the
1088:             * answer.
1089:             */
1090:            private static int[] subtract(int[] big, int[] little) {
1091:                int bigIndex = big.length;
1092:                int result[] = new int[bigIndex];
1093:                int littleIndex = little.length;
1094:                long difference = 0;
1095:
1096:                // Subtract common parts of both numbers
1097:                while (littleIndex > 0) {
1098:                    difference = (big[--bigIndex] & LONG_MASK)
1099:                            - (little[--littleIndex] & LONG_MASK)
1100:                            + (difference >> 32);
1101:                    result[bigIndex] = (int) difference;
1102:                }
1103:
1104:                // Subtract remainder of longer number while borrow propagates
1105:                boolean borrow = (difference >> 32 != 0);
1106:                while (bigIndex > 0 && borrow)
1107:                    borrow = ((result[--bigIndex] = big[bigIndex] - 1) == -1);
1108:
1109:                // Copy remainder of longer number
1110:                while (bigIndex > 0)
1111:                    result[--bigIndex] = big[bigIndex];
1112:
1113:                return result;
1114:            }
1115:
1116:            /**
1117:             * Returns a BigInteger whose value is <tt>(this * val)</tt>.
1118:             *
1119:             * @param  val value to be multiplied by this BigInteger.
1120:             * @return <tt>this * val</tt>
1121:             */
1122:            public BigInteger multiply(BigInteger val) {
1123:                if (signum == 0 || val.signum == 0)
1124:                    return ZERO;
1125:
1126:                int[] result = multiplyToLen(mag, mag.length, val.mag,
1127:                        val.mag.length, null);
1128:                result = trustedStripLeadingZeroInts(result);
1129:                return new BigInteger(result, signum * val.signum);
1130:            }
1131:
1132:            /**
1133:             * Multiplies int arrays x and y to the specified lengths and places
1134:             * the result into z.
1135:             */
1136:            private int[] multiplyToLen(int[] x, int xlen, int[] y, int ylen,
1137:                    int[] z) {
1138:                int xstart = xlen - 1;
1139:                int ystart = ylen - 1;
1140:
1141:                if (z == null || z.length < (xlen + ylen))
1142:                    z = new int[xlen + ylen];
1143:
1144:                long carry = 0;
1145:                for (int j = ystart, k = ystart + 1 + xstart; j >= 0; j--, k--) {
1146:                    long product = (y[j] & LONG_MASK) * (x[xstart] & LONG_MASK)
1147:                            + carry;
1148:                    z[k] = (int) product;
1149:                    carry = product >>> 32;
1150:                }
1151:                z[xstart] = (int) carry;
1152:
1153:                for (int i = xstart - 1; i >= 0; i--) {
1154:                    carry = 0;
1155:                    for (int j = ystart, k = ystart + 1 + i; j >= 0; j--, k--) {
1156:                        long product = (y[j] & LONG_MASK) * (x[i] & LONG_MASK)
1157:                                + (z[k] & LONG_MASK) + carry;
1158:                        z[k] = (int) product;
1159:                        carry = product >>> 32;
1160:                    }
1161:                    z[i] = (int) carry;
1162:                }
1163:                return z;
1164:            }
1165:
1166:            /**
1167:             * Returns a BigInteger whose value is <tt>(this<sup>2</sup>)</tt>.
1168:             *
1169:             * @return <tt>this<sup>2</sup></tt>
1170:             */
1171:            private BigInteger square() {
1172:                if (signum == 0)
1173:                    return ZERO;
1174:                int[] z = squareToLen(mag, mag.length, null);
1175:                return new BigInteger(trustedStripLeadingZeroInts(z), 1);
1176:            }
1177:
1178:            /**
1179:             * Squares the contents of the int array x. The result is placed into the
1180:             * int array z.  The contents of x are not changed.
1181:             */
1182:            private static final int[] squareToLen(int[] x, int len, int[] z) {
1183:                /*
1184:                 * The algorithm used here is adapted from Colin Plumb's C library.
1185:                 * Technique: Consider the partial products in the multiplication
1186:                 * of "abcde" by itself:
1187:                 *
1188:                 *               a  b  c  d  e
1189:                 *            *  a  b  c  d  e
1190:                 *          ==================
1191:                 *              ae be ce de ee
1192:                 *           ad bd cd dd de
1193:                 *        ac bc cc cd ce
1194:                 *     ab bb bc bd be
1195:                 *  aa ab ac ad ae
1196:                 *
1197:                 * Note that everything above the main diagonal:
1198:                 *              ae be ce de = (abcd) * e
1199:                 *           ad bd cd       = (abc) * d
1200:                 *        ac bc             = (ab) * c
1201:                 *     ab                   = (a) * b
1202:                 *
1203:                 * is a copy of everything below the main diagonal:
1204:                 *                       de
1205:                 *                 cd ce
1206:                 *           bc bd be
1207:                 *     ab ac ad ae
1208:                 *
1209:                 * Thus, the sum is 2 * (off the diagonal) + diagonal.
1210:                 *
1211:                 * This is accumulated beginning with the diagonal (which
1212:                 * consist of the squares of the digits of the input), which is then
1213:                 * divided by two, the off-diagonal added, and multiplied by two
1214:                 * again.  The low bit is simply a copy of the low bit of the
1215:                 * input, so it doesn't need special care.
1216:                 */
1217:                int zlen = len << 1;
1218:                if (z == null || z.length < zlen)
1219:                    z = new int[zlen];
1220:
1221:                // Store the squares, right shifted one bit (i.e., divided by 2)
1222:                int lastProductLowWord = 0;
1223:                for (int j = 0, i = 0; j < len; j++) {
1224:                    long piece = (x[j] & LONG_MASK);
1225:                    long product = piece * piece;
1226:                    z[i++] = (lastProductLowWord << 31)
1227:                            | (int) (product >>> 33);
1228:                    z[i++] = (int) (product >>> 1);
1229:                    lastProductLowWord = (int) product;
1230:                }
1231:
1232:                // Add in off-diagonal sums
1233:                for (int i = len, offset = 1; i > 0; i--, offset += 2) {
1234:                    int t = x[i - 1];
1235:                    t = mulAdd(z, x, offset, i - 1, t);
1236:                    addOne(z, offset - 1, i, t);
1237:                }
1238:
1239:                // Shift back up and set low bit
1240:                primitiveLeftShift(z, zlen, 1);
1241:                z[zlen - 1] |= x[len - 1] & 1;
1242:
1243:                return z;
1244:            }
1245:
1246:            /**
1247:             * Returns a BigInteger whose value is <tt>(this / val)</tt>.
1248:             *
1249:             * @param  val value by which this BigInteger is to be divided.
1250:             * @return <tt>this / val</tt>
1251:             * @throws ArithmeticException <tt>val==0</tt>
1252:             */
1253:            public BigInteger divide(BigInteger val) {
1254:                MutableBigInteger q = new MutableBigInteger(), r = new MutableBigInteger(), a = new MutableBigInteger(
1255:                        this .mag), b = new MutableBigInteger(val.mag);
1256:
1257:                a.divide(b, q, r);
1258:                return new BigInteger(q, this .signum * val.signum);
1259:            }
1260:
1261:            /**
1262:             * Returns an array of two BigIntegers containing <tt>(this / val)</tt>
1263:             * followed by <tt>(this % val)</tt>.
1264:             *
1265:             * @param  val value by which this BigInteger is to be divided, and the
1266:             *	       remainder computed.
1267:             * @return an array of two BigIntegers: the quotient <tt>(this / val)</tt>
1268:             *	       is the initial element, and the remainder <tt>(this % val)</tt>
1269:             *	       is the final element.
1270:             * @throws ArithmeticException <tt>val==0</tt>
1271:             */
1272:            public BigInteger[] divideAndRemainder(BigInteger val) {
1273:                BigInteger[] result = new BigInteger[2];
1274:                MutableBigInteger q = new MutableBigInteger(), r = new MutableBigInteger(), a = new MutableBigInteger(
1275:                        this .mag), b = new MutableBigInteger(val.mag);
1276:                a.divide(b, q, r);
1277:                result[0] = new BigInteger(q, this .signum * val.signum);
1278:                result[1] = new BigInteger(r, this .signum);
1279:                return result;
1280:            }
1281:
1282:            /**
1283:             * Returns a BigInteger whose value is <tt>(this % val)</tt>.
1284:             *
1285:             * @param  val value by which this BigInteger is to be divided, and the
1286:             *	       remainder computed.
1287:             * @return <tt>this % val</tt>
1288:             * @throws ArithmeticException <tt>val==0</tt>
1289:             */
1290:            public BigInteger remainder(BigInteger val) {
1291:                MutableBigInteger q = new MutableBigInteger(), r = new MutableBigInteger(), a = new MutableBigInteger(
1292:                        this .mag), b = new MutableBigInteger(val.mag);
1293:
1294:                a.divide(b, q, r);
1295:                return new BigInteger(r, this .signum);
1296:            }
1297:
1298:            /**
1299:             * Returns a BigInteger whose value is <tt>(this<sup>exponent</sup>)</tt>.
1300:             * Note that <tt>exponent</tt> is an integer rather than a BigInteger.
1301:             *
1302:             * @param  exponent exponent to which this BigInteger is to be raised.
1303:             * @return <tt>this<sup>exponent</sup></tt>
1304:             * @throws ArithmeticException <tt>exponent</tt> is negative.  (This would
1305:             *	       cause the operation to yield a non-integer value.)
1306:             */
1307:            public BigInteger pow(int exponent) {
1308:                if (exponent < 0)
1309:                    throw new ArithmeticException("Negative exponent");
1310:                if (signum == 0)
1311:                    return (exponent == 0 ? ONE : this );
1312:
1313:                // Perform exponentiation using repeated squaring method
1314:                int newSign = (signum < 0 && (exponent & 1) == 1 ? -1 : 1);
1315:                int[] baseToPow2 = this .mag;
1316:                int[] result = { 1 };
1317:
1318:                while (exponent != 0) {
1319:                    if ((exponent & 1) == 1) {
1320:                        result = multiplyToLen(result, result.length,
1321:                                baseToPow2, baseToPow2.length, null);
1322:                        result = trustedStripLeadingZeroInts(result);
1323:                    }
1324:                    if ((exponent >>>= 1) != 0) {
1325:                        baseToPow2 = squareToLen(baseToPow2, baseToPow2.length,
1326:                                null);
1327:                        baseToPow2 = trustedStripLeadingZeroInts(baseToPow2);
1328:                    }
1329:                }
1330:                return new BigInteger(result, newSign);
1331:            }
1332:
1333:            /**
1334:             * Returns a BigInteger whose value is the greatest common divisor of
1335:             * <tt>abs(this)</tt> and <tt>abs(val)</tt>.  Returns 0 if
1336:             * <tt>this==0 &amp;&amp; val==0</tt>.
1337:             *
1338:             * @param  val value with with the GCD is to be computed.
1339:             * @return <tt>GCD(abs(this), abs(val))</tt>
1340:             */
1341:            public BigInteger gcd(BigInteger val) {
1342:                if (val.signum == 0)
1343:                    return this .abs();
1344:                else if (this .signum == 0)
1345:                    return val.abs();
1346:
1347:                MutableBigInteger a = new MutableBigInteger(this );
1348:                MutableBigInteger b = new MutableBigInteger(val);
1349:
1350:                MutableBigInteger result = a.hybridGCD(b);
1351:
1352:                return new BigInteger(result, 1);
1353:            }
1354:
1355:            /**
1356:             * Left shift int array a up to len by n bits. Returns the array that
1357:             * results from the shift since space may have to be reallocated.
1358:             */
1359:            private static int[] leftShift(int[] a, int len, int n) {
1360:                int nInts = n >>> 5;
1361:                int nBits = n & 0x1F;
1362:                int bitsInHighWord = bitLen(a[0]);
1363:
1364:                // If shift can be done without recopy, do so
1365:                if (n <= (32 - bitsInHighWord)) {
1366:                    primitiveLeftShift(a, len, nBits);
1367:                    return a;
1368:                } else { // Array must be resized
1369:                    if (nBits <= (32 - bitsInHighWord)) {
1370:                        int result[] = new int[nInts + len];
1371:                        for (int i = 0; i < len; i++)
1372:                            result[i] = a[i];
1373:                        primitiveLeftShift(result, result.length, nBits);
1374:                        return result;
1375:                    } else {
1376:                        int result[] = new int[nInts + len + 1];
1377:                        for (int i = 0; i < len; i++)
1378:                            result[i] = a[i];
1379:                        primitiveRightShift(result, result.length, 32 - nBits);
1380:                        return result;
1381:                    }
1382:                }
1383:            }
1384:
1385:            // shifts a up to len right n bits assumes no leading zeros, 0<n<32
1386:            static void primitiveRightShift(int[] a, int len, int n) {
1387:                int n2 = 32 - n;
1388:                for (int i = len - 1, c = a[i]; i > 0; i--) {
1389:                    int b = c;
1390:                    c = a[i - 1];
1391:                    a[i] = (c << n2) | (b >>> n);
1392:                }
1393:                a[0] >>>= n;
1394:            }
1395:
1396:            // shifts a up to len left n bits assumes no leading zeros, 0<=n<32
1397:            static void primitiveLeftShift(int[] a, int len, int n) {
1398:                if (len == 0 || n == 0)
1399:                    return;
1400:
1401:                int n2 = 32 - n;
1402:                for (int i = 0, c = a[i], m = i + len - 1; i < m; i++) {
1403:                    int b = c;
1404:                    c = a[i + 1];
1405:                    a[i] = (b << n) | (c >>> n2);
1406:                }
1407:                a[len - 1] <<= n;
1408:            }
1409:
1410:            /**
1411:             * Calculate bitlength of contents of the first len elements an int array,
1412:             * assuming there are no leading zero ints.
1413:             */
1414:            private static int bitLength(int[] val, int len) {
1415:                if (len == 0)
1416:                    return 0;
1417:                return ((len - 1) << 5) + bitLen(val[0]);
1418:            }
1419:
1420:            /**
1421:             * Returns a BigInteger whose value is the absolute value of this
1422:             * BigInteger. 
1423:             *
1424:             * @return <tt>abs(this)</tt>
1425:             */
1426:            public BigInteger abs() {
1427:                return (signum >= 0 ? this  : this .negate());
1428:            }
1429:
1430:            /**
1431:             * Returns a BigInteger whose value is <tt>(-this)</tt>.
1432:             *
1433:             * @return <tt>-this</tt>
1434:             */
1435:            public BigInteger negate() {
1436:                return new BigInteger(this .mag, -this .signum);
1437:            }
1438:
1439:            /**
1440:             * Returns the signum function of this BigInteger.
1441:             *
1442:             * @return -1, 0 or 1 as the value of this BigInteger is negative, zero or
1443:             *	       positive.
1444:             */
1445:            public int signum() {
1446:                return this .signum;
1447:            }
1448:
1449:            // Modular Arithmetic Operations
1450:
1451:            /**
1452:             * Returns a BigInteger whose value is <tt>(this mod m</tt>).  This method
1453:             * differs from <tt>remainder</tt> in that it always returns a
1454:             * <i>non-negative</i> BigInteger.
1455:             *
1456:             * @param  m the modulus.
1457:             * @return <tt>this mod m</tt>
1458:             * @throws ArithmeticException <tt>m &lt;= 0</tt>
1459:             * @see    #remainder
1460:             */
1461:            public BigInteger mod(BigInteger m) {
1462:                if (m.signum <= 0)
1463:                    throw new ArithmeticException(
1464:                            "BigInteger: modulus not positive");
1465:
1466:                BigInteger result = this .remainder(m);
1467:                return (result.signum >= 0 ? result : result.add(m));
1468:            }
1469:
1470:            /**
1471:             * Returns a BigInteger whose value is
1472:             * <tt>(this<sup>exponent</sup> mod m)</tt>.  (Unlike <tt>pow</tt>, this
1473:             * method permits negative exponents.)
1474:             *
1475:             * @param  exponent the exponent.
1476:             * @param  m the modulus.
1477:             * @return <tt>this<sup>exponent</sup> mod m</tt>
1478:             * @throws ArithmeticException <tt>m &lt;= 0</tt>
1479:             * @see    #modInverse
1480:             */
1481:            public BigInteger modPow(BigInteger exponent, BigInteger m) {
1482:                if (m.signum <= 0)
1483:                    throw new ArithmeticException(
1484:                            "BigInteger: modulus not positive");
1485:
1486:                // Trivial cases
1487:                if (exponent.signum == 0)
1488:                    return (m.equals(ONE) ? ZERO : ONE);
1489:
1490:                if (this .equals(ONE))
1491:                    return (m.equals(ONE) ? ZERO : ONE);
1492:
1493:                if (this .equals(ZERO) && exponent.signum >= 0)
1494:                    return ZERO;
1495:
1496:                if (this .equals(negConst[1]) && (!exponent.testBit(0)))
1497:                    return (m.equals(ONE) ? ZERO : ONE);
1498:
1499:                boolean invertResult;
1500:                if ((invertResult = (exponent.signum < 0)))
1501:                    exponent = exponent.negate();
1502:
1503:                BigInteger base = (this .signum < 0 || this .compareTo(m) >= 0 ? this 
1504:                        .mod(m)
1505:                        : this );
1506:                BigInteger result;
1507:                if (m.testBit(0)) { // odd modulus
1508:                    result = base.oddModPow(exponent, m);
1509:                } else {
1510:                    /*
1511:                     * Even modulus.  Tear it into an "odd part" (m1) and power of two
1512:                     * (m2), exponentiate mod m1, manually exponentiate mod m2, and
1513:                     * use Chinese Remainder Theorem to combine results.
1514:                     */
1515:
1516:                    // Tear m apart into odd part (m1) and power of 2 (m2)
1517:                    int p = m.getLowestSetBit(); // Max pow of 2 that divides m
1518:
1519:                    BigInteger m1 = m.shiftRight(p); // m/2**p
1520:                    BigInteger m2 = ONE.shiftLeft(p); // 2**p
1521:
1522:                    // Calculate new base from m1
1523:                    BigInteger base2 = (this .signum < 0
1524:                            || this .compareTo(m1) >= 0 ? this .mod(m1) : this );
1525:
1526:                    // Caculate (base ** exponent) mod m1.
1527:                    BigInteger a1 = (m1.equals(ONE) ? ZERO : base2.oddModPow(
1528:                            exponent, m1));
1529:
1530:                    // Calculate (this ** exponent) mod m2
1531:                    BigInteger a2 = base.modPow2(exponent, p);
1532:
1533:                    // Combine results using Chinese Remainder Theorem
1534:                    BigInteger y1 = m2.modInverse(m1);
1535:                    BigInteger y2 = m1.modInverse(m2);
1536:
1537:                    result = a1.multiply(m2).multiply(y1).add(
1538:                            a2.multiply(m1).multiply(y2)).mod(m);
1539:                }
1540:
1541:                return (invertResult ? result.modInverse(m) : result);
1542:            }
1543:
1544:            static int[] bnExpModThreshTable = { 7, 25, 81, 241, 673, 1793,
1545:                    Integer.MAX_VALUE }; // Sentinel
1546:
1547:            /**
1548:             * Returns a BigInteger whose value is x to the power of y mod z.
1549:             * Assumes: z is odd && x < z.
1550:             */
1551:            private BigInteger oddModPow(BigInteger y, BigInteger z) {
1552:                /*
1553:                 * The algorithm is adapted from Colin Plumb's C library.
1554:                 *
1555:                 * The window algorithm:
1556:                 * The idea is to keep a running product of b1 = n^(high-order bits of exp)
1557:                 * and then keep appending exponent bits to it.  The following patterns
1558:                 * apply to a 3-bit window (k = 3):
1559:                 * To append   0: square
1560:                 * To append   1: square, multiply by n^1
1561:                 * To append  10: square, multiply by n^1, square
1562:                 * To append  11: square, square, multiply by n^3
1563:                 * To append 100: square, multiply by n^1, square, square
1564:                 * To append 101: square, square, square, multiply by n^5
1565:                 * To append 110: square, square, multiply by n^3, square
1566:                 * To append 111: square, square, square, multiply by n^7
1567:                 *
1568:                 * Since each pattern involves only one multiply, the longer the pattern
1569:                 * the better, except that a 0 (no multiplies) can be appended directly.
1570:                 * We precompute a table of odd powers of n, up to 2^k, and can then
1571:                 * multiply k bits of exponent at a time.  Actually, assuming random
1572:                 * exponents, there is on average one zero bit between needs to
1573:                 * multiply (1/2 of the time there's none, 1/4 of the time there's 1,
1574:                 * 1/8 of the time, there's 2, 1/32 of the time, there's 3, etc.), so
1575:                 * you have to do one multiply per k+1 bits of exponent.
1576:                 *
1577:                 * The loop walks down the exponent, squaring the result buffer as
1578:                 * it goes.  There is a wbits+1 bit lookahead buffer, buf, that is
1579:                 * filled with the upcoming exponent bits.  (What is read after the
1580:                 * end of the exponent is unimportant, but it is filled with zero here.)
1581:                 * When the most-significant bit of this buffer becomes set, i.e.
1582:                 * (buf & tblmask) != 0, we have to decide what pattern to multiply
1583:                 * by, and when to do it.  We decide, remember to do it in future
1584:                 * after a suitable number of squarings have passed (e.g. a pattern
1585:                 * of "100" in the buffer requires that we multiply by n^1 immediately;
1586:                 * a pattern of "110" calls for multiplying by n^3 after one more
1587:                 * squaring), clear the buffer, and continue.
1588:                 *
1589:                 * When we start, there is one more optimization: the result buffer
1590:                 * is implcitly one, so squaring it or multiplying by it can be
1591:                 * optimized away.  Further, if we start with a pattern like "100"
1592:                 * in the lookahead window, rather than placing n into the buffer
1593:                 * and then starting to square it, we have already computed n^2
1594:                 * to compute the odd-powers table, so we can place that into
1595:                 * the buffer and save a squaring.
1596:                 *
1597:                 * This means that if you have a k-bit window, to compute n^z,
1598:                 * where z is the high k bits of the exponent, 1/2 of the time
1599:                 * it requires no squarings.  1/4 of the time, it requires 1
1600:                 * squaring, ... 1/2^(k-1) of the time, it reqires k-2 squarings.
1601:                 * And the remaining 1/2^(k-1) of the time, the top k bits are a
1602:                 * 1 followed by k-1 0 bits, so it again only requires k-2
1603:                 * squarings, not k-1.  The average of these is 1.  Add that
1604:                 * to the one squaring we have to do to compute the table,
1605:                 * and you'll see that a k-bit window saves k-2 squarings
1606:                 * as well as reducing the multiplies.  (It actually doesn't
1607:                 * hurt in the case k = 1, either.)
1608:                 */
1609:                // Special case for exponent of one
1610:                if (y.equals(ONE))
1611:                    return this ;
1612:
1613:                // Special case for base of zero
1614:                if (signum == 0)
1615:                    return ZERO;
1616:
1617:                int[] base = (int[]) mag.clone();
1618:                int[] exp = y.mag;
1619:                int[] mod = z.mag;
1620:                int modLen = mod.length;
1621:
1622:                // Select an appropriate window size
1623:                int wbits = 0;
1624:                int ebits = bitLength(exp, exp.length);
1625:                while (ebits > bnExpModThreshTable[wbits])
1626:                    wbits++;
1627:
1628:                // Calculate appropriate table size
1629:                int tblmask = 1 << wbits;
1630:
1631:                // Allocate table for precomputed odd powers of base in Montgomery form
1632:                int[][] table = new int[tblmask][];
1633:                for (int i = 0; i < tblmask; i++)
1634:                    table[i] = new int[modLen];
1635:
1636:                // Compute the modular inverse
1637:                int inv = -MutableBigInteger.inverseMod32(mod[modLen - 1]);
1638:
1639:                // Convert base to Montgomery form
1640:                int[] a = leftShift(base, base.length, modLen << 5);
1641:
1642:                MutableBigInteger q = new MutableBigInteger(), r = new MutableBigInteger(), a2 = new MutableBigInteger(
1643:                        a), b2 = new MutableBigInteger(mod);
1644:
1645:                a2.divide(b2, q, r);
1646:                table[0] = r.toIntArray();
1647:
1648:                // Pad table[0] with leading zeros so its length is at least modLen
1649:                if (table[0].length < modLen) {
1650:                    int offset = modLen - table[0].length;
1651:                    int[] t2 = new int[modLen];
1652:                    for (int i = 0; i < table[0].length; i++)
1653:                        t2[i + offset] = table[0][i];
1654:                    table[0] = t2;
1655:                }
1656:
1657:                // Set b to the square of the base
1658:                int[] b = squareToLen(table[0], modLen, null);
1659:                b = montReduce(b, mod, modLen, inv);
1660:
1661:                // Set t to high half of b
1662:                int[] t = new int[modLen];
1663:                for (int i = 0; i < modLen; i++)
1664:                    t[i] = b[i];
1665:
1666:                // Fill in the table with odd powers of the base        
1667:                for (int i = 1; i < tblmask; i++) {
1668:                    int[] prod = multiplyToLen(t, modLen, table[i - 1], modLen,
1669:                            null);
1670:                    table[i] = montReduce(prod, mod, modLen, inv);
1671:                }
1672:
1673:                // Pre load the window that slides over the exponent
1674:                int bitpos = 1 << ((ebits - 1) & (32 - 1));
1675:
1676:                int buf = 0;
1677:                int elen = exp.length;
1678:                int eIndex = 0;
1679:                for (int i = 0; i <= wbits; i++) {
1680:                    buf = (buf << 1) | (((exp[eIndex] & bitpos) != 0) ? 1 : 0);
1681:                    bitpos >>>= 1;
1682:                    if (bitpos == 0) {
1683:                        eIndex++;
1684:                        bitpos = 1 << (32 - 1);
1685:                        elen--;
1686:                    }
1687:                }
1688:
1689:                int multpos = ebits;
1690:
1691:                // The first iteration, which is hoisted out of the main loop
1692:                ebits--;
1693:                boolean isone = true;
1694:
1695:                multpos = ebits - wbits;
1696:                while ((buf & 1) == 0) {
1697:                    buf >>>= 1;
1698:                    multpos++;
1699:                }
1700:
1701:                int[] mult = table[buf >>> 1];
1702:
1703:                buf = 0;
1704:                if (multpos == ebits)
1705:                    isone = false;
1706:
1707:                // The main loop
1708:                while (true) {
1709:                    ebits--;
1710:                    // Advance the window
1711:                    buf <<= 1;
1712:
1713:                    if (elen != 0) {
1714:                        buf |= ((exp[eIndex] & bitpos) != 0) ? 1 : 0;
1715:                        bitpos >>>= 1;
1716:                        if (bitpos == 0) {
1717:                            eIndex++;
1718:                            bitpos = 1 << (32 - 1);
1719:                            elen--;
1720:                        }
1721:                    }
1722:
1723:                    // Examine the window for pending multiplies
1724:                    if ((buf & tblmask) != 0) {
1725:                        multpos = ebits - wbits;
1726:                        while ((buf & 1) == 0) {
1727:                            buf >>>= 1;
1728:                            multpos++;
1729:                        }
1730:                        mult = table[buf >>> 1];
1731:                        buf = 0;
1732:                    }
1733:
1734:                    // Perform multiply
1735:                    if (ebits == multpos) {
1736:                        if (isone) {
1737:                            b = (int[]) mult.clone();
1738:                            isone = false;
1739:                        } else {
1740:                            t = b;
1741:                            a = multiplyToLen(t, modLen, mult, modLen, a);
1742:                            a = montReduce(a, mod, modLen, inv);
1743:                            t = a;
1744:                            a = b;
1745:                            b = t;
1746:                        }
1747:                    }
1748:
1749:                    // Check if done
1750:                    if (ebits == 0)
1751:                        break;
1752:
1753:                    // Square the input
1754:                    if (!isone) {
1755:                        t = b;
1756:                        a = squareToLen(t, modLen, a);
1757:                        a = montReduce(a, mod, modLen, inv);
1758:                        t = a;
1759:                        a = b;
1760:                        b = t;
1761:                    }
1762:                }
1763:
1764:                // Convert result out of Montgomery form and return
1765:                int[] t2 = new int[2 * modLen];
1766:                for (int i = 0; i < modLen; i++)
1767:                    t2[i + modLen] = b[i];
1768:
1769:                b = montReduce(t2, mod, modLen, inv);
1770:
1771:                t2 = new int[modLen];
1772:                for (int i = 0; i < modLen; i++)
1773:                    t2[i] = b[i];
1774:
1775:                return new BigInteger(1, t2);
1776:            }
1777:
1778:            /**
1779:             * Montgomery reduce n, modulo mod.  This reduces modulo mod and divides
1780:             * by 2^(32*mlen). Adapted from Colin Plumb's C library.
1781:             */
1782:            private static int[] montReduce(int[] n, int[] mod, int mlen,
1783:                    int inv) {
1784:                int c = 0;
1785:                int len = mlen;
1786:                int offset = 0;
1787:
1788:                do {
1789:                    int nEnd = n[n.length - 1 - offset];
1790:                    int carry = mulAdd(n, mod, offset, mlen, inv * nEnd);
1791:                    c += addOne(n, offset, mlen, carry);
1792:                    offset++;
1793:                } while (--len > 0);
1794:
1795:                while (c > 0)
1796:                    c += subN(n, mod, mlen);
1797:
1798:                while (intArrayCmpToLen(n, mod, mlen) >= 0)
1799:                    subN(n, mod, mlen);
1800:
1801:                return n;
1802:            }
1803:
1804:            /*
1805:             * Returns -1, 0 or +1 as big-endian unsigned int array arg1 is less than,
1806:             * equal to, or greater than arg2 up to length len.
1807:             */
1808:            private static int intArrayCmpToLen(int[] arg1, int[] arg2, int len) {
1809:                for (int i = 0; i < len; i++) {
1810:                    long b1 = arg1[i] & LONG_MASK;
1811:                    long b2 = arg2[i] & LONG_MASK;
1812:                    if (b1 < b2)
1813:                        return -1;
1814:                    if (b1 > b2)
1815:                        return 1;
1816:                }
1817:                return 0;
1818:            }
1819:
1820:            /**
1821:             * Subtracts two numbers of same length, returning borrow.
1822:             */
1823:            private static int subN(int[] a, int[] b, int len) {
1824:                long sum = 0;
1825:
1826:                while (--len >= 0) {
1827:                    sum = (a[len] & LONG_MASK) - (b[len] & LONG_MASK)
1828:                            + (sum >> 32);
1829:                    a[len] = (int) sum;
1830:                }
1831:
1832:                return (int) (sum >> 32);
1833:            }
1834:
1835:            /**
1836:             * Multiply an array by one word k and add to result, return the carry
1837:             */
1838:            static int mulAdd(int[] out, int[] in, int offset, int len, int k) {
1839:                long kLong = k & LONG_MASK;
1840:                long carry = 0;
1841:
1842:                offset = out.length - offset - 1;
1843:                for (int j = len - 1; j >= 0; j--) {
1844:                    long product = (in[j] & LONG_MASK) * kLong
1845:                            + (out[offset] & LONG_MASK) + carry;
1846:                    out[offset--] = (int) product;
1847:                    carry = product >>> 32;
1848:                }
1849:                return (int) carry;
1850:            }
1851:
1852:            /**
1853:             * Add one word to the number a mlen words into a. Return the resulting
1854:             * carry.
1855:             */
1856:            static int addOne(int[] a, int offset, int mlen, int carry) {
1857:                offset = a.length - 1 - mlen - offset;
1858:                long t = (a[offset] & LONG_MASK) + (carry & LONG_MASK);
1859:
1860:                a[offset] = (int) t;
1861:                if ((t >>> 32) == 0)
1862:                    return 0;
1863:                while (--mlen >= 0) {
1864:                    if (--offset < 0) { // Carry out of number
1865:                        return 1;
1866:                    } else {
1867:                        a[offset]++;
1868:                        if (a[offset] != 0)
1869:                            return 0;
1870:                    }
1871:                }
1872:                return 1;
1873:            }
1874:
1875:            /**
1876:             * Returns a BigInteger whose value is (this ** exponent) mod (2**p)
1877:             */
1878:            private BigInteger modPow2(BigInteger exponent, int p) {
1879:                /*
1880:                 * Perform exponentiation using repeated squaring method, chopping off
1881:                 * high order bits as indicated by modulus.
1882:                 */
1883:                BigInteger result = valueOf(1);
1884:                BigInteger baseToPow2 = this .mod2(p);
1885:                int expOffset = 0;
1886:
1887:                int limit = exponent.bitLength();
1888:
1889:                if (this .testBit(0))
1890:                    limit = (p - 1) < limit ? (p - 1) : limit;
1891:
1892:                while (expOffset < limit) {
1893:                    if (exponent.testBit(expOffset))
1894:                        result = result.multiply(baseToPow2).mod2(p);
1895:                    expOffset++;
1896:                    if (expOffset < limit)
1897:                        baseToPow2 = baseToPow2.square().mod2(p);
1898:                }
1899:
1900:                return result;
1901:            }
1902:
1903:            /**
1904:             * Returns a BigInteger whose value is this mod(2**p).
1905:             * Assumes that this BigInteger &gt;= 0 and p &gt; 0.
1906:             */
1907:            private BigInteger mod2(int p) {
1908:                if (bitLength() <= p)
1909:                    return this ;
1910:
1911:                // Copy remaining ints of mag
1912:                int numInts = (p + 31) / 32;
1913:                int[] mag = new int[numInts];
1914:                for (int i = 0; i < numInts; i++)
1915:                    mag[i] = this .mag[i + (this .mag.length - numInts)];
1916:
1917:                // Mask out any excess bits
1918:                int excessBits = (numInts << 5) - p;
1919:                mag[0] &= (1L << (32 - excessBits)) - 1;
1920:
1921:                return (mag[0] == 0 ? new BigInteger(1, mag) : new BigInteger(
1922:                        mag, 1));
1923:            }
1924:
1925:            /**
1926:             * Returns a BigInteger whose value is <tt>(this<sup>-1</sup> mod m)</tt>.
1927:             *
1928:             * @param  m the modulus.
1929:             * @return <tt>this<sup>-1</sup> mod m</tt>.
1930:             * @throws ArithmeticException <tt> m &lt;= 0</tt>, or this BigInteger
1931:             *	       has no multiplicative inverse mod m (that is, this BigInteger
1932:             *	       is not <i>relatively prime</i> to m).
1933:             */
1934:            public BigInteger modInverse(BigInteger m) {
1935:                if (m.signum != 1)
1936:                    throw new ArithmeticException(
1937:                            "BigInteger: modulus not positive");
1938:
1939:                if (m.equals(ONE))
1940:                    return ZERO;
1941:
1942:                // Calculate (this mod m)
1943:                BigInteger modVal = this ;
1944:                if (signum < 0 || (intArrayCmp(mag, m.mag) >= 0))
1945:                    modVal = this .mod(m);
1946:
1947:                if (modVal.equals(ONE))
1948:                    return ONE;
1949:
1950:                MutableBigInteger a = new MutableBigInteger(modVal);
1951:                MutableBigInteger b = new MutableBigInteger(m);
1952:
1953:                MutableBigInteger result = a.mutableModInverse(b);
1954:                return new BigInteger(result, 1);
1955:            }
1956:
1957:            // Shift Operations
1958:
1959:            /**
1960:             * Returns a BigInteger whose value is <tt>(this &lt;&lt; n)</tt>.
1961:             * The shift distance, <tt>n</tt>, may be negative, in which case
1962:             * this method performs a right shift.
1963:             * (Computes <tt>floor(this * 2<sup>n</sup>)</tt>.)
1964:             *
1965:             * @param  n shift distance, in bits.
1966:             * @return <tt>this &lt;&lt; n</tt>
1967:             * @see #shiftRight
1968:             */
1969:            public BigInteger shiftLeft(int n) {
1970:                if (signum == 0)
1971:                    return ZERO;
1972:                if (n == 0)
1973:                    return this ;
1974:                if (n < 0)
1975:                    return shiftRight(-n);
1976:
1977:                int nInts = n >>> 5;
1978:                int nBits = n & 0x1f;
1979:                int magLen = mag.length;
1980:                int newMag[] = null;
1981:
1982:                if (nBits == 0) {
1983:                    newMag = new int[magLen + nInts];
1984:                    for (int i = 0; i < magLen; i++)
1985:                        newMag[i] = mag[i];
1986:                } else {
1987:                    int i = 0;
1988:                    int nBits2 = 32 - nBits;
1989:                    int highBits = mag[0] >>> nBits2;
1990:                    if (highBits != 0) {
1991:                        newMag = new int[magLen + nInts + 1];
1992:                        newMag[i++] = highBits;
1993:                    } else {
1994:                        newMag = new int[magLen + nInts];
1995:                    }
1996:                    int j = 0;
1997:                    while (j < magLen - 1)
1998:                        newMag[i++] = mag[j++] << nBits | mag[j] >>> nBits2;
1999:                    newMag[i] = mag[j] << nBits;
2000:                }
2001:
2002:                return new BigInteger(newMag, signum);
2003:            }
2004:
2005:            /**
2006:             * Returns a BigInteger whose value is <tt>(this &gt;&gt; n)</tt>.  Sign
2007:             * extension is performed.  The shift distance, <tt>n</tt>, may be
2008:             * negative, in which case this method performs a left shift.
2009:             * (Computes <tt>floor(this / 2<sup>n</sup>)</tt>.) 
2010:             *
2011:             * @param  n shift distance, in bits.
2012:             * @return <tt>this &gt;&gt; n</tt>
2013:             * @see #shiftLeft
2014:             */
2015:            public BigInteger shiftRight(int n) {
2016:                if (n == 0)
2017:                    return this ;
2018:                if (n < 0)
2019:                    return shiftLeft(-n);
2020:
2021:                int nInts = n >>> 5;
2022:                int nBits = n & 0x1f;
2023:                int magLen = mag.length;
2024:                int newMag[] = null;
2025:
2026:                // Special case: entire contents shifted off the end
2027:                if (nInts >= magLen)
2028:                    return (signum >= 0 ? ZERO : negConst[1]);
2029:
2030:                if (nBits == 0) {
2031:                    int newMagLen = magLen - nInts;
2032:                    newMag = new int[newMagLen];
2033:                    for (int i = 0; i < newMagLen; i++)
2034:                        newMag[i] = mag[i];
2035:                } else {
2036:                    int i = 0;
2037:                    int highBits = mag[0] >>> nBits;
2038:                    if (highBits != 0) {
2039:                        newMag = new int[magLen - nInts];
2040:                        newMag[i++] = highBits;
2041:                    } else {
2042:                        newMag = new int[magLen - nInts - 1];
2043:                    }
2044:
2045:                    int nBits2 = 32 - nBits;
2046:                    int j = 0;
2047:                    while (j < magLen - nInts - 1)
2048:                        newMag[i++] = (mag[j++] << nBits2) | (mag[j] >>> nBits);
2049:                }
2050:
2051:                if (signum < 0) {
2052:                    // Find out whether any one-bits were shifted off the end.
2053:                    boolean onesLost = false;
2054:                    for (int i = magLen - 1, j = magLen - nInts; i >= j
2055:                            && !onesLost; i--)
2056:                        onesLost = (mag[i] != 0);
2057:                    if (!onesLost && nBits != 0)
2058:                        onesLost = (mag[magLen - nInts - 1] << (32 - nBits) != 0);
2059:
2060:                    if (onesLost)
2061:                        newMag = javaIncrement(newMag);
2062:                }
2063:
2064:                return new BigInteger(newMag, signum);
2065:            }
2066:
2067:            int[] javaIncrement(int[] val) {
2068:                boolean done = false;
2069:                int lastSum = 0;
2070:                for (int i = val.length - 1; i >= 0 && lastSum == 0; i--)
2071:                    lastSum = (val[i] += 1);
2072:                if (lastSum == 0) {
2073:                    val = new int[val.length + 1];
2074:                    val[0] = 1;
2075:                }
2076:                return val;
2077:            }
2078:
2079:            // Bitwise Operations
2080:
2081:            /**
2082:             * Returns a BigInteger whose value is <tt>(this &amp; val)</tt>.  (This
2083:             * method returns a negative BigInteger if and only if this and val are
2084:             * both negative.)
2085:             *
2086:             * @param val value to be AND'ed with this BigInteger.
2087:             * @return <tt>this &amp; val</tt>
2088:             */
2089:            public BigInteger and(BigInteger val) {
2090:                int[] result = new int[Math.max(intLength(), val.intLength())];
2091:                for (int i = 0; i < result.length; i++)
2092:                    result[i] = (int) (getInt(result.length - i - 1) & val
2093:                            .getInt(result.length - i - 1));
2094:
2095:                return valueOf(result);
2096:            }
2097:
2098:            /**
2099:             * Returns a BigInteger whose value is <tt>(this | val)</tt>.  (This method
2100:             * returns a negative BigInteger if and only if either this or val is
2101:             * negative.) 
2102:             *
2103:             * @param val value to be OR'ed with this BigInteger.
2104:             * @return <tt>this | val</tt>
2105:             */
2106:            public BigInteger or(BigInteger val) {
2107:                int[] result = new int[Math.max(intLength(), val.intLength())];
2108:                for (int i = 0; i < result.length; i++)
2109:                    result[i] = (int) (getInt(result.length - i - 1) | val
2110:                            .getInt(result.length - i - 1));
2111:
2112:                return valueOf(result);
2113:            }
2114:
2115:            /**
2116:             * Returns a BigInteger whose value is <tt>(this ^ val)</tt>.  (This method
2117:             * returns a negative BigInteger if and only if exactly one of this and
2118:             * val are negative.)
2119:             *
2120:             * @param val value to be XOR'ed with this BigInteger.
2121:             * @return <tt>this ^ val</tt>
2122:             */
2123:            public BigInteger xor(BigInteger val) {
2124:                int[] result = new int[Math.max(intLength(), val.intLength())];
2125:                for (int i = 0; i < result.length; i++)
2126:                    result[i] = (int) (getInt(result.length - i - 1) ^ val
2127:                            .getInt(result.length - i - 1));
2128:
2129:                return valueOf(result);
2130:            }
2131:
2132:            /**
2133:             * Returns a BigInteger whose value is <tt>(~this)</tt>.  (This method
2134:             * returns a negative value if and only if this BigInteger is
2135:             * non-negative.)
2136:             *
2137:             * @return <tt>~this</tt>
2138:             */
2139:            public BigInteger not() {
2140:                int[] result = new int[intLength()];
2141:                for (int i = 0; i < result.length; i++)
2142:                    result[i] = (int) ~getInt(result.length - i - 1);
2143:
2144:                return valueOf(result);
2145:            }
2146:
2147:            /**
2148:             * Returns a BigInteger whose value is <tt>(this &amp; ~val)</tt>.  This
2149:             * method, which is equivalent to <tt>and(val.not())</tt>, is provided as
2150:             * a convenience for masking operations.  (This method returns a negative
2151:             * BigInteger if and only if <tt>this</tt> is negative and <tt>val</tt> is
2152:             * positive.)
2153:             *
2154:             * @param val value to be complemented and AND'ed with this BigInteger.
2155:             * @return <tt>this &amp; ~val</tt>
2156:             */
2157:            public BigInteger andNot(BigInteger val) {
2158:                int[] result = new int[Math.max(intLength(), val.intLength())];
2159:                for (int i = 0; i < result.length; i++)
2160:                    result[i] = (int) (getInt(result.length - i - 1) & ~val
2161:                            .getInt(result.length - i - 1));
2162:
2163:                return valueOf(result);
2164:            }
2165:
2166:            // Single Bit Operations
2167:
2168:            /**
2169:             * Returns <tt>true</tt> if and only if the designated bit is set.
2170:             * (Computes <tt>((this &amp; (1&lt;&lt;n)) != 0)</tt>.)
2171:             *
2172:             * @param  n index of bit to test.
2173:             * @return <tt>true</tt> if and only if the designated bit is set.
2174:             * @throws ArithmeticException <tt>n</tt> is negative.
2175:             */
2176:            public boolean testBit(int n) {
2177:                if (n < 0)
2178:                    throw new ArithmeticException("Negative bit address");
2179:
2180:                return (getInt(n / 32) & (1 << (n % 32))) != 0;
2181:            }
2182:
2183:            /**
2184:             * Returns a BigInteger whose value is equivalent to this BigInteger
2185:             * with the designated bit set.  (Computes <tt>(this | (1&lt;&lt;n))</tt>.)
2186:             *
2187:             * @param  n index of bit to set.
2188:             * @return <tt>this | (1&lt;&lt;n)</tt>
2189:             * @throws ArithmeticException <tt>n</tt> is negative.
2190:             */
2191:            public BigInteger setBit(int n) {
2192:                if (n < 0)
2193:                    throw new ArithmeticException("Negative bit address");
2194:
2195:                int intNum = n / 32;
2196:                int[] result = new int[Math.max(intLength(), intNum + 2)];
2197:
2198:                for (int i = 0; i < result.length; i++)
2199:                    result[result.length - i - 1] = getInt(i);
2200:
2201:                result[result.length - intNum - 1] |= (1 << (n % 32));
2202:
2203:                return valueOf(result);
2204:            }
2205:
2206:            /**
2207:             * Returns a BigInteger whose value is equivalent to this BigInteger
2208:             * with the designated bit cleared.
2209:             * (Computes <tt>(this &amp; ~(1&lt;&lt;n))</tt>.)
2210:             *
2211:             * @param  n index of bit to clear.
2212:             * @return <tt>this & ~(1&lt;&lt;n)</tt>
2213:             * @throws ArithmeticException <tt>n</tt> is negative.
2214:             */
2215:            public BigInteger clearBit(int n) {
2216:                if (n < 0)
2217:                    throw new ArithmeticException("Negative bit address");
2218:
2219:                int intNum = n / 32;
2220:                int[] result = new int[Math.max(intLength(), (n + 1) / 32 + 1)];
2221:
2222:                for (int i = 0; i < result.length; i++)
2223:                    result[result.length - i - 1] = getInt(i);
2224:
2225:                result[result.length - intNum - 1] &= ~(1 << (n % 32));
2226:
2227:                return valueOf(result);
2228:            }
2229:
2230:            /**
2231:             * Returns a BigInteger whose value is equivalent to this BigInteger
2232:             * with the designated bit flipped.
2233:             * (Computes <tt>(this ^ (1&lt;&lt;n))</tt>.)
2234:             *
2235:             * @param  n index of bit to flip.
2236:             * @return <tt>this ^ (1&lt;&lt;n)</tt>
2237:             * @throws ArithmeticException <tt>n</tt> is negative.
2238:             */
2239:            public BigInteger flipBit(int n) {
2240:                if (n < 0)
2241:                    throw new ArithmeticException("Negative bit address");
2242:
2243:                int intNum = n / 32;
2244:                int[] result = new int[Math.max(intLength(), intNum + 2)];
2245:
2246:                for (int i = 0; i < result.length; i++)
2247:                    result[result.length - i - 1] = getInt(i);
2248:
2249:                result[result.length - intNum - 1] ^= (1 << (n % 32));
2250:
2251:                return valueOf(result);
2252:            }
2253:
2254:            /**
2255:             * Returns the index of the rightmost (lowest-order) one bit in this
2256:             * BigInteger (the number of zero bits to the right of the rightmost
2257:             * one bit).  Returns -1 if this BigInteger contains no one bits.
2258:             * (Computes <tt>(this==0? -1 : log<sub>2</sub>(this &amp; -this))</tt>.)
2259:             *
2260:             * @return index of the rightmost one bit in this BigInteger.
2261:             */
2262:            public int getLowestSetBit() {
2263:                /*
2264:                 * Initialize lowestSetBit field the first time this method is
2265:                 * executed. This method depends on the atomicity of int modifies;
2266:                 * without this guarantee, it would have to be synchronized.
2267:                 */
2268:                if (lowestSetBit == -2) {
2269:                    if (signum == 0) {
2270:                        lowestSetBit = -1;
2271:                    } else {
2272:                        // Search for lowest order nonzero int
2273:                        int i, b;
2274:                        for (i = 0; (b = getInt(i)) == 0; i++)
2275:                            ;
2276:                        lowestSetBit = (i << 5) + trailingZeroCnt(b);
2277:                    }
2278:                }
2279:                return lowestSetBit;
2280:            }
2281:
2282:            // Miscellaneous Bit Operations
2283:
2284:            /**
2285:             * Returns the number of bits in the minimal two's-complement
2286:             * representation of this BigInteger, <i>excluding</i> a sign bit.
2287:             * For positive BigIntegers, this is equivalent to the number of bits in
2288:             * the ordinary binary representation.  (Computes
2289:             * <tt>(ceil(log<sub>2</sub>(this &lt; 0 ? -this : this+1)))</tt>.)
2290:             *
2291:             * @return number of bits in the minimal two's-complement
2292:             *         representation of this BigInteger, <i>excluding</i> a sign bit.
2293:             */
2294:            public int bitLength() {
2295:                /*
2296:                 * Initialize bitLength field the first time this method is executed.
2297:                 * This method depends on the atomicity of int modifies; without
2298:                 * this guarantee, it would have to be synchronized.
2299:                 */
2300:                if (bitLength == -1) {
2301:                    if (signum == 0) {
2302:                        bitLength = 0;
2303:                    } else {
2304:                        // Calculate the bit length of the magnitude
2305:                        int magBitLength = ((mag.length - 1) << 5)
2306:                                + bitLen(mag[0]);
2307:
2308:                        if (signum < 0) {
2309:                            // Check if magnitude is a power of two
2310:                            boolean pow2 = (bitCnt(mag[0]) == 1);
2311:                            for (int i = 1; i < mag.length && pow2; i++)
2312:                                pow2 = (mag[i] == 0);
2313:
2314:                            bitLength = (pow2 ? magBitLength - 1 : magBitLength);
2315:                        } else {
2316:                            bitLength = magBitLength;
2317:                        }
2318:                    }
2319:                }
2320:                return bitLength;
2321:            }
2322:
2323:            /**
2324:             * bitLen(val) is the number of bits in val.
2325:             */
2326:            static int bitLen(int w) {
2327:                // Binary search - decision tree (5 tests, rarely 6)
2328:                return (w < 1 << 15 ? (w < 1 << 7 ? (w < 1 << 3 ? (w < 1 << 1 ? (w < 1 << 0 ? (w < 0 ? 32
2329:                        : 0)
2330:                        : 1)
2331:                        : (w < 1 << 2 ? 2 : 3))
2332:                        : (w < 1 << 5 ? (w < 1 << 4 ? 4 : 5) : (w < 1 << 6 ? 6
2333:                                : 7)))
2334:                        : (w < 1 << 11 ? (w < 1 << 9 ? (w < 1 << 8 ? 8 : 9)
2335:                                : (w < 1 << 10 ? 10 : 11))
2336:                                : (w < 1 << 13 ? (w < 1 << 12 ? 12 : 13)
2337:                                        : (w < 1 << 14 ? 14 : 15))))
2338:                        : (w < 1 << 23 ? (w < 1 << 19 ? (w < 1 << 17 ? (w < 1 << 16 ? 16
2339:                                : 17)
2340:                                : (w < 1 << 18 ? 18 : 19))
2341:                                : (w < 1 << 21 ? (w < 1 << 20 ? 20 : 21)
2342:                                        : (w < 1 << 22 ? 22 : 23)))
2343:                                : (w < 1 << 27 ? (w < 1 << 25 ? (w < 1 << 24 ? 24
2344:                                        : 25)
2345:                                        : (w < 1 << 26 ? 26 : 27))
2346:                                        : (w < 1 << 29 ? (w < 1 << 28 ? 28 : 29)
2347:                                                : (w < 1 << 30 ? 30 : 31)))));
2348:            }
2349:
2350:            /*
2351:             * trailingZeroTable[i] is the number of trailing zero bits in the binary
2352:             * representaion of i.
2353:             */
2354:            final static byte trailingZeroTable[] = { -25, 0, 1, 0, 2, 0, 1, 0,
2355:                    3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0,
2356:                    2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
2357:                    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0,
2358:                    2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0,
2359:                    3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0,
2360:                    2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
2361:                    7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0,
2362:                    2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0,
2363:                    3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0,
2364:                    2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
2365:                    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0,
2366:                    2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0,
2367:                    3, 0, 1, 0, 2, 0, 1, 0 };
2368:
2369:            /**
2370:             * Returns the number of bits in the two's complement representation
2371:             * of this BigInteger that differ from its sign bit.  This method is
2372:             * useful when implementing bit-vector style sets atop BigIntegers.
2373:             *
2374:             * @return number of bits in the two's complement representation
2375:             *         of this BigInteger that differ from its sign bit.
2376:             */
2377:            public int bitCount() {
2378:                /*
2379:                 * Initialize bitCount field the first time this method is executed.
2380:                 * This method depends on the atomicity of int modifies; without
2381:                 * this guarantee, it would have to be synchronized.
2382:                 */
2383:                if (bitCount == -1) {
2384:                    // Count the bits in the magnitude
2385:                    int magBitCount = 0;
2386:                    for (int i = 0; i < mag.length; i++)
2387:                        magBitCount += bitCnt(mag[i]);
2388:
2389:                    if (signum < 0) {
2390:                        // Count the trailing zeros in the magnitude
2391:                        int magTrailingZeroCount = 0, j;
2392:                        for (j = mag.length - 1; mag[j] == 0; j--)
2393:                            magTrailingZeroCount += 32;
2394:                        magTrailingZeroCount += trailingZeroCnt(mag[j]);
2395:
2396:                        bitCount = magBitCount + magTrailingZeroCount - 1;
2397:                    } else {
2398:                        bitCount = magBitCount;
2399:                    }
2400:                }
2401:                return bitCount;
2402:            }
2403:
2404:            static int bitCnt(int val) {
2405:                val -= (0xaaaaaaaa & val) >>> 1;
2406:                val = (val & 0x33333333) + ((val >>> 2) & 0x33333333);
2407:                val = val + (val >>> 4) & 0x0f0f0f0f;
2408:                val += val >>> 8;
2409:                val += val >>> 16;
2410:                return val & 0xff;
2411:            }
2412:
2413:            static int trailingZeroCnt(int val) {
2414:                // Loop unrolled for performance
2415:                int byteVal = val & 0xff;
2416:                if (byteVal != 0)
2417:                    return trailingZeroTable[byteVal];
2418:
2419:                byteVal = (val >>> 8) & 0xff;
2420:                if (byteVal != 0)
2421:                    return trailingZeroTable[byteVal] + 8;
2422:
2423:                byteVal = (val >>> 16) & 0xff;
2424:                if (byteVal != 0)
2425:                    return trailingZeroTable[byteVal] + 16;
2426:
2427:                byteVal = (val >>> 24) & 0xff;
2428:                return trailingZeroTable[byteVal] + 24;
2429:            }
2430:
2431:            // Primality Testing
2432:
2433:            /**
2434:             * Returns <tt>true</tt> if this BigInteger is probably prime,
2435:             * <tt>false</tt> if it's definitely composite.  If
2436:             * <tt>certainty</tt> is <tt> &lt;= 0</tt>, <tt>true</tt> is
2437:             * returned.
2438:             *
2439:             * @param  certainty a measure of the uncertainty that the caller is
2440:             *	       willing to tolerate: if the call returns <tt>true</tt>
2441:             *	       the probability that this BigInteger is prime exceeds
2442:             *	       <tt>(1 - 1/2<sup>certainty</sup>)</tt>.  The execution time of
2443:             * 	       this method is proportional to the value of this parameter.
2444:             * @return <tt>true</tt> if this BigInteger is probably prime,
2445:             * 	       <tt>false</tt> if it's definitely composite.
2446:             */
2447:            public boolean isProbablePrime(int certainty) {
2448:                if (certainty <= 0)
2449:                    return true;
2450:                BigInteger w = this .abs();
2451:                if (w.equals(TWO))
2452:                    return true;
2453:                if (!w.testBit(0) || w.equals(ONE))
2454:                    return false;
2455:
2456:                return w.primeToCertainty(certainty);
2457:            }
2458:
2459:            // Comparison Operations
2460:
2461:            /**
2462:             * Compares this BigInteger with the specified BigInteger.  This method is
2463:             * provided in preference to individual methods for each of the six
2464:             * boolean comparison operators (&lt;, ==, &gt;, &gt;=, !=, &lt;=).  The
2465:             * suggested idiom for performing these comparisons is:
2466:             * <tt>(x.compareTo(y)</tt> &lt;<i>op</i>&gt; <tt>0)</tt>,
2467:             * where &lt;<i>op</i>&gt; is one of the six comparison operators.
2468:             *
2469:             * @param  val BigInteger to which this BigInteger is to be compared.
2470:             * @return -1, 0 or 1 as this BigInteger is numerically less than, equal
2471:             *         to, or greater than <tt>val</tt>.
2472:             */
2473:            public int compareTo(BigInteger val) {
2474:                return (signum == val.signum ? signum
2475:                        * intArrayCmp(mag, val.mag) : (signum > val.signum ? 1
2476:                        : -1));
2477:            }
2478:
2479:            /**
2480:             * Compares this BigInteger with the specified Object.  If the Object is a
2481:             * BigInteger, this method behaves like <tt>compareTo(BigInteger)</tt>.
2482:             * Otherwise, it throws a <tt>ClassCastException</tt> (as BigIntegers are
2483:             * comparable only to other BigIntegers).
2484:             *
2485:             * @param   o Object to which this BigInteger is to be compared.
2486:             * @return  a negative number, zero, or a positive number as this
2487:             *		BigInteger is numerically less than, equal to, or greater
2488:             *		than <tt>o</tt>, which must be a BigInteger.
2489:             * @throws  ClassCastException <tt>o</tt> is not a BigInteger.
2490:             * @see     #compareTo(java.math.BigInteger)
2491:             * @see     Comparable
2492:             * @since   1.2
2493:             */
2494:            public int compareTo(Object o) {
2495:                return compareTo((BigInteger) o);
2496:            }
2497:
2498:            /*
2499:             * Returns -1, 0 or +1 as big-endian unsigned int array arg1 is
2500:             * less than, equal to, or greater than arg2.
2501:             */
2502:            private static int intArrayCmp(int[] arg1, int[] arg2) {
2503:                if (arg1.length < arg2.length)
2504:                    return -1;
2505:                if (arg1.length > arg2.length)
2506:                    return 1;
2507:
2508:                // Argument lengths are equal; compare the values
2509:                for (int i = 0; i < arg1.length; i++) {
2510:                    long b1 = arg1[i] & LONG_MASK;
2511:                    long b2 = arg2[i] & LONG_MASK;
2512:                    if (b1 < b2)
2513:                        return -1;
2514:                    if (b1 > b2)
2515:                        return 1;
2516:                }
2517:                return 0;
2518:            }
2519:
2520:            /**
2521:             * Compares this BigInteger with the specified Object for equality.
2522:             *
2523:             * @param  x Object to which this BigInteger is to be compared.
2524:             * @return <tt>true</tt> if and only if the specified Object is a
2525:             *	       BigInteger whose value is numerically equal to this BigInteger.
2526:             */
2527:            public boolean equals(Object x) {
2528:                // This test is just an optimization, which may or may not help
2529:                if (x == this )
2530:                    return true;
2531:
2532:                if (!(x instanceof  BigInteger))
2533:                    return false;
2534:                BigInteger xInt = (BigInteger) x;
2535:
2536:                if (xInt.signum != signum || xInt.mag.length != mag.length)
2537:                    return false;
2538:
2539:                for (int i = 0; i < mag.length; i++)
2540:                    if (xInt.mag[i] != mag[i])
2541:                        return false;
2542:
2543:                return true;
2544:            }
2545:
2546:            /**
2547:             * Returns the minimum of this BigInteger and <tt>val</tt>.
2548:             *
2549:             * @param  val value with with the minimum is to be computed.
2550:             * @return the BigInteger whose value is the lesser of this BigInteger and 
2551:             *	       <tt>val</tt>.  If they are equal, either may be returned.
2552:             */
2553:            public BigInteger min(BigInteger val) {
2554:                return (compareTo(val) < 0 ? this  : val);
2555:            }
2556:
2557:            /**
2558:             * Returns the maximum of this BigInteger and <tt>val</tt>.
2559:             *
2560:             * @param  val value with with the maximum is to be computed.
2561:             * @return the BigInteger whose value is the greater of this and
2562:             *         <tt>val</tt>.  If they are equal, either may be returned.
2563:             */
2564:            public BigInteger max(BigInteger val) {
2565:                return (compareTo(val) > 0 ? this  : val);
2566:            }
2567:
2568:            // Hash Function
2569:
2570:            /**
2571:             * Returns the hash code for this BigInteger.
2572:             *
2573:             * @return hash code for this BigInteger.
2574:             */
2575:            public int hashCode() {
2576:                int hashCode = 0;
2577:
2578:                for (int i = 0; i < mag.length; i++)
2579:                    hashCode = (int) (31 * hashCode + (mag[i] & LONG_MASK));
2580:
2581:                return hashCode * signum;
2582:            }
2583:
2584:            /**
2585:             * Returns the String representation of this BigInteger in the
2586:             * given radix.  If the radix is outside the range from {@link
2587:             * Character#MIN_RADIX} to {@link Character#MAX_RADIX} inclusive,
2588:             * it will default to 10 (as is the case for
2589:             * <tt>Integer.toString</tt>).  The digit-to-character mapping
2590:             * provided by <tt>Character.forDigit</tt> is used, and a minus
2591:             * sign is prepended if appropriate.  (This representation is
2592:             * compatible with the {@link #BigInteger(String, int) (String,
2593:             * <code>int</code>)} constructor.)
2594:             *
2595:             * @param  radix  radix of the String representation.
2596:             * @return String representation of this BigInteger in the given radix.
2597:             * @see    Integer#toString
2598:             * @see    Character#forDigit
2599:             * @see    #BigInteger(java.lang.String, int)
2600:             */
2601:            public String toString(int radix) {
2602:                if (signum == 0)
2603:                    return "0";
2604:                if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
2605:                    radix = 10;
2606:
2607:                // Compute upper bound on number of digit groups and allocate space
2608:                int maxNumDigitGroups = (4 * mag.length + 6) / 7;
2609:                String digitGroup[] = new String[maxNumDigitGroups];
2610:
2611:                // Translate number to string, a digit group at a time
2612:                BigInteger tmp = this .abs();
2613:                int numGroups = 0;
2614:                while (tmp.signum != 0) {
2615:                    BigInteger d = longRadix[radix];
2616:
2617:                    MutableBigInteger q = new MutableBigInteger(), r = new MutableBigInteger(), a = new MutableBigInteger(
2618:                            tmp.mag), b = new MutableBigInteger(d.mag);
2619:                    a.divide(b, q, r);
2620:                    BigInteger q2 = new BigInteger(q, tmp.signum * d.signum);
2621:                    BigInteger r2 = new BigInteger(r, tmp.signum * d.signum);
2622:
2623:                    digitGroup[numGroups++] = Long.toString(r2.longValue(),
2624:                            radix);
2625:                    tmp = q2;
2626:                }
2627:
2628:                // Put sign (if any) and first digit group into result buffer
2629:                StringBuffer buf = new StringBuffer(numGroups
2630:                        * digitsPerLong[radix] + 1);
2631:                if (signum < 0)
2632:                    buf.append('-');
2633:                buf.append(digitGroup[numGroups - 1]);
2634:
2635:                // Append remaining digit groups padded with leading zeros
2636:                for (int i = numGroups - 2; i >= 0; i--) {
2637:                    // Prepend (any) leading zeros for this digit group
2638:                    int numLeadingZeros = digitsPerLong[radix]
2639:                            - digitGroup[i].length();
2640:                    if (numLeadingZeros != 0)
2641:                        buf.append(zeros[numLeadingZeros]);
2642:                    buf.append(digitGroup[i]);
2643:                }
2644:                return buf.toString();
2645:            }
2646:
2647:            /* zero[i] is a string of i consecutive zeros. */
2648:            private static String zeros[] = new String[64];
2649:            static {
2650:                zeros[63] = "000000000000000000000000000000000000000000000000000000000000000";
2651:                for (int i = 0; i < 63; i++)
2652:                    zeros[i] = zeros[63].substring(0, i);
2653:            }
2654:
2655:            /**
2656:             * Returns the decimal String representation of this BigInteger.
2657:             * The digit-to-character mapping provided by
2658:             * <tt>Character.forDigit</tt> is used, and a minus sign is
2659:             * prepended if appropriate.  (This representation is compatible
2660:             * with the {@link #BigInteger(String) (String)} constructor, and
2661:             * allows for String concatenation with Java's + operator.)
2662:             *
2663:             * @return decimal String representation of this BigInteger.
2664:             * @see    Character#forDigit
2665:             * @see    #BigInteger(java.lang.String)
2666:             */
2667:            public String toString() {
2668:                return toString(10);
2669:            }
2670:
2671:            /**
2672:             * Returns a byte array containing the two's-complement
2673:             * representation of this BigInteger.  The byte array will be in
2674:             * <i>big-endian</i> byte-order: the most significant byte is in
2675:             * the zeroth element.  The array will contain the minimum number
2676:             * of bytes required to represent this BigInteger, including at
2677:             * least one sign bit, which is <tt>(ceil((this.bitLength() +
2678:             * 1)/8))</tt>.  (This representation is compatible with the
2679:             * {@link #BigInteger(byte[]) (byte[])} constructor.)
2680:             *
2681:             * @return a byte array containing the two's-complement representation of
2682:             *	       this BigInteger.
2683:             * @see    #BigInteger(byte[])
2684:             */
2685:            public byte[] toByteArray() {
2686:                int byteLen = bitLength() / 8 + 1;
2687:                byte[] byteArray = new byte[byteLen];
2688:
2689:                for (int i = byteLen - 1, bytesCopied = 4, nextInt = 0, intIndex = 0; i >= 0; i--) {
2690:                    if (bytesCopied == 4) {
2691:                        nextInt = getInt(intIndex++);
2692:                        bytesCopied = 1;
2693:                    } else {
2694:                        nextInt >>>= 8;
2695:                        bytesCopied++;
2696:                    }
2697:                    byteArray[i] = (byte) nextInt;
2698:                }
2699:                return byteArray;
2700:            }
2701:
2702:            /**
2703:             * Converts this BigInteger to an <code>int</code>.  This
2704:             * conversion is analogous to a <a
2705:             * href="http://java.sun.com/docs/books/jls/second_edition/html/conversions.doc.html#25363"><i>narrowing
2706:             * primitive conversion</i></a> from <code>long</code> to
2707:             * <code>int</code> as defined in the <a
2708:             * href="http://java.sun.com/docs/books/jls/html/">Java Language
2709:             * Specification</a>: if this BigInteger is too big to fit in an
2710:             * <code>int</code>, only the low-order 32 bits are returned.
2711:             * Note that this conversion can lose information about the
2712:             * overall magnitude of the BigInteger value as well as return a
2713:             * result with the opposite sign.
2714:             *
2715:             * @return this BigInteger converted to an <code>int</code>.
2716:             */
2717:            public int intValue() {
2718:                int result = 0;
2719:                result = getInt(0);
2720:                return result;
2721:            }
2722:
2723:            /**
2724:             * Converts this BigInteger to a <code>long</code>.  This
2725:             * conversion is analogous to a <a
2726:             * href="http://java.sun.com/docs/books/jls/second_edition/html/conversions.doc.html#25363"><i>narrowing
2727:             * primitive conversion</i></a> from <code>long</code> to
2728:             * <code>int</code> as defined in the <a
2729:             * href="http://java.sun.com/docs/books/jls/html/">Java Language
2730:             * Specification</a>: if this BigInteger is too big to fit in a
2731:             * <code>long</code>, only the low-order 64 bits are returned.
2732:             * Note that this conversion can lose information about the
2733:             * overall magnitude of the BigInteger value as well as return a
2734:             * result with the opposite sign.
2735:             *
2736:             * @return this BigInteger converted to a <code>long</code>.
2737:             */
2738:            public long longValue() {
2739:                long result = 0;
2740:
2741:                for (int i = 1; i >= 0; i--)
2742:                    result = (result << 32) + (getInt(i) & LONG_MASK);
2743:                return result;
2744:            }
2745:
2746:            /**
2747:             * Converts this BigInteger to a <code>float</code>.  This
2748:             * conversion is similar to the <a
2749:             * href="http://java.sun.com/docs/books/jls/second_edition/html/conversions.doc.html#25363"><i>narrowing
2750:             * primitive conversion</i></a> from <code>double</code> to
2751:             * <code>float</code> defined in the <a
2752:             * href="http://java.sun.com/docs/books/jls/html/">Java Language
2753:             * Specification</a>: if this BigInteger has too great a magnitude
2754:             * to represent as a <code>float</code>, it will be converted to
2755:             * {@link Float#NEGATIVE_INFINITY} or {@link
2756:             * Float#POSITIVE_INFINITY} as appropriate.  Note that even when
2757:             * the return value is finite, this conversion can lose
2758:             * information about the precision of the BigInteger value.
2759:             *
2760:             * @return this BigInteger converted to a <code>float</code>.
2761:             */
2762:            public float floatValue() {
2763:                // Somewhat inefficient, but guaranteed to work.
2764:                return Float.valueOf(this .toString()).floatValue();
2765:            }
2766:
2767:            /**
2768:             * Converts this BigInteger to a <code>double</code>.  This
2769:             * conversion is similar to the <a
2770:             * href="http://java.sun.com/docs/books/jls/second_edition/html/conversions.doc.html#25363"><i>narrowing
2771:             * primitive conversion</i></a> from <code>double</code> to
2772:             * <code>float</code> defined in the <a
2773:             * href="http://java.sun.com/docs/books/jls/html/">Java Language
2774:             * Specification</a>: if this BigInteger has too great a magnitude
2775:             * to represent as a <code>double</code>, it will be converted to
2776:             * {@link Double#NEGATIVE_INFINITY} or {@link
2777:             * Double#POSITIVE_INFINITY} as appropriate.  Note that even when
2778:             * the return value is finite, this conversion can lose
2779:             * information about the precision of the BigInteger value.
2780:             *
2781:             * @return this BigInteger converted to a <code>double</code>.
2782:             */
2783:            public double doubleValue() {
2784:                // Somewhat inefficient, but guaranteed to work.
2785:                return Double.valueOf(this .toString()).doubleValue();
2786:            }
2787:
2788:            /**
2789:             * Returns a copy of the input array stripped of any leading zero bytes.
2790:             */
2791:            private static int[] stripLeadingZeroInts(int val[]) {
2792:                int byteLength = val.length;
2793:                int keep;
2794:
2795:                // Find first nonzero byte
2796:                for (keep = 0; keep < val.length && val[keep] == 0; keep++)
2797:                    ;
2798:
2799:                int result[] = new int[val.length - keep];
2800:                for (int i = 0; i < val.length - keep; i++)
2801:                    result[i] = val[keep + i];
2802:
2803:                return result;
2804:            }
2805:
2806:            /**
2807:             * Returns the input array stripped of any leading zero bytes.
2808:             * Since the source is trusted the copying may be skipped.
2809:             */
2810:            private static int[] trustedStripLeadingZeroInts(int val[]) {
2811:                int byteLength = val.length;
2812:                int keep;
2813:
2814:                // Find first nonzero byte
2815:                for (keep = 0; keep < val.length && val[keep] == 0; keep++)
2816:                    ;
2817:
2818:                // Only perform copy if necessary
2819:                if (keep > 0) {
2820:                    int result[] = new int[val.length - keep];
2821:                    for (int i = 0; i < val.length - keep; i++)
2822:                        result[i] = val[keep + i];
2823:                    return result;
2824:                }
2825:                return val;
2826:            }
2827:
2828:            /**
2829:             * Returns a copy of the input array stripped of any leading zero bytes.
2830:             */
2831:            private static int[] stripLeadingZeroBytes(byte a[]) {
2832:                int byteLength = a.length;
2833:                int keep;
2834:
2835:                // Find first nonzero byte
2836:                for (keep = 0; keep < a.length && a[keep] == 0; keep++)
2837:                    ;
2838:
2839:                // Allocate new array and copy relevant part of input array
2840:                int intLength = ((byteLength - keep) + 3) / 4;
2841:                int[] result = new int[intLength];
2842:                int b = byteLength - 1;
2843:                for (int i = intLength - 1; i >= 0; i--) {
2844:                    result[i] = a[b--] & 0xff;
2845:                    int bytesRemaining = b - keep + 1;
2846:                    int bytesToTransfer = Math.min(3, bytesRemaining);
2847:                    for (int j = 8; j <= 8 * bytesToTransfer; j += 8)
2848:                        result[i] |= ((a[b--] & 0xff) << j);
2849:                }
2850:                return result;
2851:            }
2852:
2853:            /**
2854:             * Takes an array a representing a negative 2's-complement number and
2855:             * returns the minimal (no leading zero bytes) unsigned whose value is -a.
2856:             */
2857:            private static int[] makePositive(byte a[]) {
2858:                int keep, k;
2859:                int byteLength = a.length;
2860:
2861:                // Find first non-sign (0xff) byte of input
2862:                for (keep = 0; keep < byteLength && a[keep] == -1; keep++)
2863:                    ;
2864:
2865:                /* Allocate output array.  If all non-sign bytes are 0x00, we must
2866:                 * allocate space for one extra output byte. */
2867:                for (k = keep; k < byteLength && a[k] == 0; k++)
2868:                    ;
2869:
2870:                int extraByte = (k == byteLength) ? 1 : 0;
2871:                int intLength = ((byteLength - keep + extraByte) + 3) / 4;
2872:                int result[] = new int[intLength];
2873:
2874:                /* Copy one's complement of input into into output, leaving extra
2875:                 * byte (if it exists) == 0x00 */
2876:                int b = byteLength - 1;
2877:                for (int i = intLength - 1; i >= 0; i--) {
2878:                    result[i] = a[b--] & 0xff;
2879:                    int numBytesToTransfer = Math.min(3, b - keep + 1);
2880:                    if (numBytesToTransfer < 0)
2881:                        numBytesToTransfer = 0;
2882:                    for (int j = 8; j <= 8 * numBytesToTransfer; j += 8)
2883:                        result[i] |= ((a[b--] & 0xff) << j);
2884:
2885:                    // Mask indicates which bits must be complemented
2886:                    int mask = -1 >>> (8 * (3 - numBytesToTransfer));
2887:                    result[i] = ~result[i] & mask;
2888:                }
2889:
2890:                // Add one to one's complement to generate two's complement
2891:                for (int i = result.length - 1; i >= 0; i--) {
2892:                    result[i] = (int) ((result[i] & LONG_MASK) + 1);
2893:                    if (result[i] != 0)
2894:                        break;
2895:                }
2896:
2897:                return result;
2898:            }
2899:
2900:            /**
2901:             * Takes an array a representing a negative 2's-complement number and
2902:             * returns the minimal (no leading zero ints) unsigned whose value is -a.
2903:             */
2904:            private static int[] makePositive(int a[]) {
2905:                int keep, j;
2906:
2907:                // Find first non-sign (0xffffffff) int of input
2908:                for (keep = 0; keep < a.length && a[keep] == -1; keep++)
2909:                    ;
2910:
2911:                /* Allocate output array.  If all non-sign ints are 0x00, we must
2912:                 * allocate space for one extra output int. */
2913:                for (j = keep; j < a.length && a[j] == 0; j++)
2914:                    ;
2915:                int extraInt = (j == a.length ? 1 : 0);
2916:                int result[] = new int[a.length - keep + extraInt];
2917:
2918:                /* Copy one's complement of input into into output, leaving extra
2919:                 * int (if it exists) == 0x00 */
2920:                for (int i = keep; i < a.length; i++)
2921:                    result[i - keep + extraInt] = ~a[i];
2922:
2923:                // Add one to one's complement to generate two's complement
2924:                for (int i = result.length - 1; ++result[i] == 0; i--)
2925:                    ;
2926:
2927:                return result;
2928:            }
2929:
2930:            /*
2931:             * The following two arrays are used for fast String conversions.  Both
2932:             * are indexed by radix.  The first is the number of digits of the given
2933:             * radix that can fit in a Java long without "going negative", i.e., the
2934:             * highest integer n such that radix**n < 2**63.  The second is the
2935:             * "long radix" that tears each number into "long digits", each of which
2936:             * consists of the number of digits in the corresponding element in
2937:             * digitsPerLong (longRadix[i] = i**digitPerLong[i]).  Both arrays have
2938:             * nonsense values in their 0 and 1 elements, as radixes 0 and 1 are not
2939:             * used.
2940:             */
2941:            private static int digitsPerLong[] = { 0, 0, 62, 39, 31, 27, 24,
2942:                    22, 20, 19, 18, 18, 17, 17, 16, 16, 15, 15, 15, 14, 14, 14,
2943:                    14, 13, 13, 13, 13, 13, 13, 12, 12, 12, 12, 12, 12, 12, 12 };
2944:
2945:            private static BigInteger longRadix[] = { null, null,
2946:                    valueOf(0x4000000000000000L), valueOf(0x383d9170b85ff80bL),
2947:                    valueOf(0x4000000000000000L), valueOf(0x6765c793fa10079dL),
2948:                    valueOf(0x41c21cb8e1000000L), valueOf(0x3642798750226111L),
2949:                    valueOf(0x1000000000000000L), valueOf(0x12bf307ae81ffd59L),
2950:                    valueOf(0xde0b6b3a7640000L), valueOf(0x4d28cb56c33fa539L),
2951:                    valueOf(0x1eca170c00000000L), valueOf(0x780c7372621bd74dL),
2952:                    valueOf(0x1e39a5057d810000L), valueOf(0x5b27ac993df97701L),
2953:                    valueOf(0x1000000000000000L), valueOf(0x27b95e997e21d9f1L),
2954:                    valueOf(0x5da0e1e53c5c8000L), valueOf(0xb16a458ef403f19L),
2955:                    valueOf(0x16bcc41e90000000L), valueOf(0x2d04b7fdd9c0ef49L),
2956:                    valueOf(0x5658597bcaa24000L), valueOf(0x6feb266931a75b7L),
2957:                    valueOf(0xc29e98000000000L), valueOf(0x14adf4b7320334b9L),
2958:                    valueOf(0x226ed36478bfa000L), valueOf(0x383d9170b85ff80bL),
2959:                    valueOf(0x5a3c23e39c000000L), valueOf(0x4e900abb53e6b71L),
2960:                    valueOf(0x7600ec618141000L), valueOf(0xaee5720ee830681L),
2961:                    valueOf(0x1000000000000000L), valueOf(0x172588ad4f5f0981L),
2962:                    valueOf(0x211e44f7d02c1000L), valueOf(0x2ee56725f06e5c71L),
2963:                    valueOf(0x41c21cb8e1000000L) };
2964:
2965:            /*
2966:             * These two arrays are the integer analogue of above.
2967:             */
2968:            private static int digitsPerInt[] = { 0, 0, 30, 19, 15, 13, 11, 11,
2969:                    10, 9, 9, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6,
2970:                    6, 6, 6, 6, 6, 6, 6, 6, 6, 5 };
2971:
2972:            private static int intRadix[] = { 0, 0, 0x40000000, 0x4546b3db,
2973:                    0x40000000, 0x48c27395, 0x159fd800, 0x75db9c97, 0x40000000,
2974:                    0x17179149, 0x3b9aca00, 0xcc6db61, 0x19a10000, 0x309f1021,
2975:                    0x57f6c100, 0xa2f1b6f, 0x10000000, 0x18754571, 0x247dbc80,
2976:                    0x3547667b, 0x4c4b4000, 0x6b5a6e1d, 0x6c20a40, 0x8d2d931,
2977:                    0xb640000, 0xe8d4a51, 0x1269ae40, 0x17179149, 0x1cb91000,
2978:                    0x23744899, 0x2b73a840, 0x34e63b41, 0x40000000, 0x4cfa3cc1,
2979:                    0x5c13d840, 0x6d91b519, 0x39aa400 };
2980:
2981:            /**
2982:             * These routines provide access to the two's complement representation
2983:             * of BigIntegers.
2984:             */
2985:
2986:            /**
2987:             * Returns the length of the two's complement representation in ints,
2988:             * including space for at least one sign bit.
2989:             */
2990:            private int intLength() {
2991:                return bitLength() / 32 + 1;
2992:            }
2993:
2994:            /* Returns sign bit */
2995:            private int signBit() {
2996:                return (signum < 0 ? 1 : 0);
2997:            }
2998:
2999:            /* Returns an int of sign bits */
3000:            private int signInt() {
3001:                return (int) (signum < 0 ? -1 : 0);
3002:            }
3003:
3004:            /**
3005:             * Returns the specified int of the little-endian two's complement
3006:             * representation (int 0 is the least significant).  The int number can
3007:             * be arbitrarily high (values are logically preceded by infinitely many
3008:             * sign ints).
3009:             */
3010:            private int getInt(int n) {
3011:                if (n < 0)
3012:                    return 0;
3013:                if (n >= mag.length)
3014:                    return signInt();
3015:
3016:                int magInt = mag[mag.length - n - 1];
3017:
3018:                return (int) (signum >= 0 ? magInt
3019:                        : (n <= firstNonzeroIntNum() ? -magInt : ~magInt));
3020:            }
3021:
3022:            /**
3023:             * Returns the index of the int that contains the first nonzero int in the
3024:             * little-endian binary representation of the magnitude (int 0 is the
3025:             * least significant). If the magnitude is zero, return value is undefined.
3026:             */
3027:            private int firstNonzeroIntNum() {
3028:                /*
3029:                 * Initialize firstNonzeroIntNum field the first time this method is
3030:                 * executed. This method depends on the atomicity of int modifies;
3031:                 * without this guarantee, it would have to be synchronized.
3032:                 */
3033:                if (firstNonzeroIntNum == -2) {
3034:                    // Search for the first nonzero int
3035:                    int i;
3036:                    for (i = mag.length - 1; i >= 0 && mag[i] == 0; i--)
3037:                        ;
3038:                    firstNonzeroIntNum = mag.length - i - 1;
3039:                }
3040:                return firstNonzeroIntNum;
3041:            }
3042:
3043:            /** use serialVersionUID from JDK 1.1. for interoperability */
3044:            private static final long serialVersionUID = -8287574255936472291L;
3045:
3046:            /**
3047:             * Reconstitute the <tt>BigInteger</tt> instance from a stream (that is,
3048:             * deserialize it). The magnitude is read in as an array of bytes
3049:             * for historical reasons, but it is converted to an array of ints
3050:             * and the byte array is discarded.
3051:             */
3052:            private void readObject(java.io.ObjectInputStream s)
3053:                    throws java.io.IOException, ClassNotFoundException {
3054:                /*
3055:                 * In order to maintain compatibility with previous serialized forms,
3056:                 * the magnitude of a BigInteger is serialized as an array of bytes.
3057:                 * The magnitude field is used as a temporary store for the byte array
3058:                 * that is deserialized. The cached computation fields should be
3059:                 * transient but are serialized for compatibility reasons.
3060:                 */
3061:
3062:                // Read in all fields
3063:                s.defaultReadObject();
3064:
3065:                // Validate signum
3066:                if (signum < -1 || signum > 1)
3067:                    throw new java.io.StreamCorruptedException(
3068:                            "BigInteger: Invalid signum value");
3069:                if ((magnitude.length == 0) != (signum == 0))
3070:                    throw new java.io.StreamCorruptedException(
3071:                            "BigInteger: signum-magnitude mismatch");
3072:
3073:                // Set "cached computation" fields to their initial values
3074:                bitCount = bitLength = -1;
3075:                lowestSetBit = firstNonzeroByteNum = firstNonzeroIntNum = -2;
3076:
3077:                // Calculate mag field from magnitude and discard magnitude
3078:                mag = stripLeadingZeroBytes(magnitude);
3079:                magnitude = null;
3080:            }
3081:
3082:            /**
3083:             * Ensure that magnitude (the obsolete byte array representation)
3084:             * is set prior to serializaing this BigInteger.  This provides a
3085:             * serialized form that is compatible with older (pre-1.3) versions.
3086:             */
3087:            private synchronized Object writeReplace() {
3088:                if (magnitude == null)
3089:                    magnitude = magSerializedForm();
3090:
3091:                return this ;
3092:            }
3093:
3094:            /**
3095:             * Returns the mag array as an array of bytes.
3096:             */
3097:            private byte[] magSerializedForm() {
3098:                int bitLen = (mag.length == 0 ? 0 : ((mag.length - 1) << 5)
3099:                        + bitLen(mag[0]));
3100:                int byteLen = (bitLen + 7) / 8;
3101:                byte[] result = new byte[byteLen];
3102:
3103:                for (int i = byteLen - 1, bytesCopied = 4, intIndex = mag.length - 1, nextInt = 0; i >= 0; i--) {
3104:                    if (bytesCopied == 4) {
3105:                        nextInt = mag[intIndex--];
3106:                        bytesCopied = 1;
3107:                    } else {
3108:                        nextInt >>>= 8;
3109:                        bytesCopied++;
3110:                    }
3111:                    result[i] = (byte) nextInt;
3112:                }
3113:                return result;
3114:            }
3115:        }
www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.