16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 /*
27 * Portions Copyright (c) 1995 Colin Plumb. All rights reserved.
28 */
29
30 package java.math;
31
32 import java.io.IOException;
33 import java.io.ObjectInputStream;
34 import java.io.ObjectOutputStream;
35 import java.io.ObjectStreamField;
36 import java.util.Arrays;
37 import java.util.Random;
38
39 /**
40 * Immutable arbitrary-precision integers. All operations behave as if
41 * BigIntegers were represented in two's-complement notation (like Java's
42 * primitive integer types). BigInteger provides analogues to all of Java's
43 * primitive integer operators, and all relevant methods from java.lang.Math.
44 * Additionally, BigInteger provides operations for modular arithmetic, GCD
45 * calculation, primality testing, prime generation, bit manipulation,
46 * and a few other miscellaneous operations.
47 *
48 * <p>Semantics of arithmetic operations exactly mimic those of Java's integer
49 * arithmetic operators, as defined in <i>The Java Language Specification</i>.
50 * For example, division by zero throws an {@code ArithmeticException}, and
51 * division of a negative by a positive yields a negative (or zero) remainder.
52 * All of the details in the Spec concerning overflow are ignored, as
53 * BigIntegers are made as large as necessary to accommodate the results of an
54 * operation.
55 *
194 * multiplication will be used.
195 */
196 private static final int TOOM_COOK_THRESHOLD = 75;
197
198 /**
199 * The threshold value for using Karatsuba squaring. If the number
200 * of ints in the number are larger than this value,
201 * Karatsuba squaring will be used. This value is found
202 * experimentally to work well.
203 */
204 private static final int KARATSUBA_SQUARE_THRESHOLD = 90;
205
206 /**
207 * The threshold value for using Toom-Cook squaring. If the number
208 * of ints in the number are larger than this value,
209 * Toom-Cook squaring will be used. This value is found
210 * experimentally to work well.
211 */
212 private static final int TOOM_COOK_SQUARE_THRESHOLD = 140;
213
214 //Constructors
215
216 /**
217 * Translates a byte array containing the two's-complement binary
218 * representation of a BigInteger into a BigInteger. The input array is
219 * assumed to be in <i>big-endian</i> byte-order: the most significant
220 * byte is in the zeroth element.
221 *
222 * @param val big-endian two's-complement binary representation of
223 * BigInteger.
224 * @throws NumberFormatException {@code val} is zero bytes long.
225 */
226 public BigInteger(byte[] val) {
227 if (val.length == 0)
228 throw new NumberFormatException("Zero length BigInteger");
229
230 if (val[0] < 0) {
231 mag = makePositive(val);
232 signum = -1;
233 } else {
1007 }
1008
1009 /**
1010 * Returns a BigInteger with the given two's complement representation.
1011 * Assumes that the input array will not be modified (the returned
1012 * BigInteger will reference the input array if feasible).
1013 */
1014 private static BigInteger valueOf(int val[]) {
1015 return (val[0]>0 ? new BigInteger(val, 1) : new BigInteger(val));
1016 }
1017
1018 // Constants
1019
1020 /**
1021 * Initialize static constant array when class is loaded.
1022 */
1023 private final static int MAX_CONSTANT = 16;
1024 private static BigInteger posConst[] = new BigInteger[MAX_CONSTANT+1];
1025 private static BigInteger negConst[] = new BigInteger[MAX_CONSTANT+1];
1026
1027 static {
1028 for (int i = 1; i <= MAX_CONSTANT; i++) {
1029 int[] magnitude = new int[1];
1030 magnitude[0] = i;
1031 posConst[i] = new BigInteger(magnitude, 1);
1032 negConst[i] = new BigInteger(magnitude, -1);
1033 }
1034 }
1035
1036 /**
1037 * The BigInteger constant zero.
1038 *
1039 * @since 1.2
1040 */
1041 public static final BigInteger ZERO = new BigInteger(new int[0], 0);
1042
1043 /**
1044 * The BigInteger constant one.
1045 *
1046 * @since 1.2
1047 */
1048 public static final BigInteger ONE = valueOf(1);
1049
1050 /**
1051 * The BigInteger constant two. (Not exported.)
1052 */
1053 private static final BigInteger TWO = valueOf(2);
3280 * Character#MIN_RADIX} to {@link Character#MAX_RADIX} inclusive,
3281 * it will default to 10 (as is the case for
3282 * {@code Integer.toString}). The digit-to-character mapping
3283 * provided by {@code Character.forDigit} is used, and a minus
3284 * sign is prepended if appropriate. (This representation is
3285 * compatible with the {@link #BigInteger(String, int) (String,
3286 * int)} constructor.)
3287 *
3288 * @param radix radix of the String representation.
3289 * @return String representation of this BigInteger in the given radix.
3290 * @see Integer#toString
3291 * @see Character#forDigit
3292 * @see #BigInteger(java.lang.String, int)
3293 */
3294 public String toString(int radix) {
3295 if (signum == 0)
3296 return "0";
3297 if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
3298 radix = 10;
3299
3300 // Compute upper bound on number of digit groups and allocate space
3301 int maxNumDigitGroups = (4*mag.length + 6)/7;
3302 String digitGroup[] = new String[maxNumDigitGroups];
3303
3304 // Translate number to string, a digit group at a time
3305 BigInteger tmp = this.abs();
3306 int numGroups = 0;
3307 while (tmp.signum != 0) {
3308 BigInteger d = longRadix[radix];
3309
3310 MutableBigInteger q = new MutableBigInteger(),
3311 a = new MutableBigInteger(tmp.mag),
3312 b = new MutableBigInteger(d.mag);
3313 MutableBigInteger r = a.divide(b, q);
3314 BigInteger q2 = q.toBigInteger(tmp.signum * d.signum);
3315 BigInteger r2 = r.toBigInteger(tmp.signum * d.signum);
3316
3317 digitGroup[numGroups++] = Long.toString(r2.longValue(), radix);
3318 tmp = q2;
3319 }
3320
3321 // Put sign (if any) and first digit group into result buffer
3322 StringBuilder buf = new StringBuilder(numGroups*digitsPerLong[radix]+1);
3323 if (signum<0)
3324 buf.append('-');
3325 buf.append(digitGroup[numGroups-1]);
3326
3327 // Append remaining digit groups padded with leading zeros
3328 for (int i=numGroups-2; i>=0; i--) {
3329 // Prepend (any) leading zeros for this digit group
3330 int numLeadingZeros = digitsPerLong[radix]-digitGroup[i].length();
3331 if (numLeadingZeros != 0)
3332 buf.append(zeros[numLeadingZeros]);
3333 buf.append(digitGroup[i]);
3334 }
3335 return buf.toString();
3336 }
3337
3338
3339 /* zero[i] is a string of i consecutive zeros. */
3340 private static String zeros[] = new String[64];
3341 static {
3342 zeros[63] =
3343 "000000000000000000000000000000000000000000000000000000000000000";
3344 for (int i=0; i<63; i++)
3345 zeros[i] = zeros[63].substring(0, i);
3346 }
3347
3348 /**
3349 * Returns the decimal String representation of this BigInteger.
3350 * The digit-to-character mapping provided by
3351 * {@code Character.forDigit} is used, and a minus sign is
3352 * prepended if appropriate. (This representation is compatible
3353 * with the {@link #BigInteger(String) (String)} constructor, and
3354 * allows for String concatenation with Java's + operator.)
3355 *
3356 * @return decimal String representation of this BigInteger.
3357 * @see Character#forDigit
|
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 /*
27 * Portions Copyright (c) 1995 Colin Plumb. All rights reserved.
28 */
29
30 package java.math;
31
32 import java.io.IOException;
33 import java.io.ObjectInputStream;
34 import java.io.ObjectOutputStream;
35 import java.io.ObjectStreamField;
36 import java.util.ArrayList;
37 import java.util.Arrays;
38 import java.util.Random;
39
40 /**
41 * Immutable arbitrary-precision integers. All operations behave as if
42 * BigIntegers were represented in two's-complement notation (like Java's
43 * primitive integer types). BigInteger provides analogues to all of Java's
44 * primitive integer operators, and all relevant methods from java.lang.Math.
45 * Additionally, BigInteger provides operations for modular arithmetic, GCD
46 * calculation, primality testing, prime generation, bit manipulation,
47 * and a few other miscellaneous operations.
48 *
49 * <p>Semantics of arithmetic operations exactly mimic those of Java's integer
50 * arithmetic operators, as defined in <i>The Java Language Specification</i>.
51 * For example, division by zero throws an {@code ArithmeticException}, and
52 * division of a negative by a positive yields a negative (or zero) remainder.
53 * All of the details in the Spec concerning overflow are ignored, as
54 * BigIntegers are made as large as necessary to accommodate the results of an
55 * operation.
56 *
195 * multiplication will be used.
196 */
197 private static final int TOOM_COOK_THRESHOLD = 75;
198
199 /**
200 * The threshold value for using Karatsuba squaring. If the number
201 * of ints in the number are larger than this value,
202 * Karatsuba squaring will be used. This value is found
203 * experimentally to work well.
204 */
205 private static final int KARATSUBA_SQUARE_THRESHOLD = 90;
206
207 /**
208 * The threshold value for using Toom-Cook squaring. If the number
209 * of ints in the number are larger than this value,
210 * Toom-Cook squaring will be used. This value is found
211 * experimentally to work well.
212 */
213 private static final int TOOM_COOK_SQUARE_THRESHOLD = 140;
214
215 /**
216 * The threshold value for using Schoenhage recursive base conversion. If
217 * the number of ints in the number are larger than this value,
218 * the Schoenhage algorithm will be used. In practice, it appears that the
219 * Schoenhage routine is faster for any threshold down to 2, and is
220 * relatively flat for thresholds between 2-25, so this choice may be
221 * varied within this range for very small effect.
222 */
223 private static final int SCHOENHAGE_BASE_CONVERSION_THRESHOLD = 8;
224
225 //Constructors
226
227 /**
228 * Translates a byte array containing the two's-complement binary
229 * representation of a BigInteger into a BigInteger. The input array is
230 * assumed to be in <i>big-endian</i> byte-order: the most significant
231 * byte is in the zeroth element.
232 *
233 * @param val big-endian two's-complement binary representation of
234 * BigInteger.
235 * @throws NumberFormatException {@code val} is zero bytes long.
236 */
237 public BigInteger(byte[] val) {
238 if (val.length == 0)
239 throw new NumberFormatException("Zero length BigInteger");
240
241 if (val[0] < 0) {
242 mag = makePositive(val);
243 signum = -1;
244 } else {
1018 }
1019
1020 /**
1021 * Returns a BigInteger with the given two's complement representation.
1022 * Assumes that the input array will not be modified (the returned
1023 * BigInteger will reference the input array if feasible).
1024 */
1025 private static BigInteger valueOf(int val[]) {
1026 return (val[0]>0 ? new BigInteger(val, 1) : new BigInteger(val));
1027 }
1028
1029 // Constants
1030
1031 /**
1032 * Initialize static constant array when class is loaded.
1033 */
1034 private final static int MAX_CONSTANT = 16;
1035 private static BigInteger posConst[] = new BigInteger[MAX_CONSTANT+1];
1036 private static BigInteger negConst[] = new BigInteger[MAX_CONSTANT+1];
1037
1038 /**
1039 * The cache of powers of each radix. This allows us to not have to
1040 * recalculate powers of radix^(2^n) more than once. This speeds
1041 * Schoenhage recursive base conversion significantly.
1042 */
1043 private static ArrayList<BigInteger>[] powerCache;
1044
1045 /** The cache of logarithms of radices for base conversion. */
1046 private static final double[] logCache;
1047
1048 /** The natural log of 2. This is used in computing cache indices. */
1049 private static final double LOG_TWO = Math.log(2.0);
1050
1051 static {
1052 for (int i = 1; i <= MAX_CONSTANT; i++) {
1053 int[] magnitude = new int[1];
1054 magnitude[0] = i;
1055 posConst[i] = new BigInteger(magnitude, 1);
1056 negConst[i] = new BigInteger(magnitude, -1);
1057 }
1058
1059 /*
1060 * Initialize the cache of radix^(2^x) values used for base conversion
1061 * with just the very first value. Additional values will be created
1062 * on demand.
1063 */
1064 powerCache = (ArrayList<BigInteger>[])
1065 new ArrayList[Character.MAX_RADIX+1];
1066 logCache = new double[Character.MAX_RADIX+1];
1067
1068 for (int i=Character.MIN_RADIX; i<=Character.MAX_RADIX; i++)
1069 {
1070 powerCache[i] = new ArrayList<BigInteger>(1);
1071 powerCache[i].add(BigInteger.valueOf(i));
1072 logCache[i] = Math.log(i);
1073 }
1074 }
1075
1076 /**
1077 * The BigInteger constant zero.
1078 *
1079 * @since 1.2
1080 */
1081 public static final BigInteger ZERO = new BigInteger(new int[0], 0);
1082
1083 /**
1084 * The BigInteger constant one.
1085 *
1086 * @since 1.2
1087 */
1088 public static final BigInteger ONE = valueOf(1);
1089
1090 /**
1091 * The BigInteger constant two. (Not exported.)
1092 */
1093 private static final BigInteger TWO = valueOf(2);
3320 * Character#MIN_RADIX} to {@link Character#MAX_RADIX} inclusive,
3321 * it will default to 10 (as is the case for
3322 * {@code Integer.toString}). The digit-to-character mapping
3323 * provided by {@code Character.forDigit} is used, and a minus
3324 * sign is prepended if appropriate. (This representation is
3325 * compatible with the {@link #BigInteger(String, int) (String,
3326 * int)} constructor.)
3327 *
3328 * @param radix radix of the String representation.
3329 * @return String representation of this BigInteger in the given radix.
3330 * @see Integer#toString
3331 * @see Character#forDigit
3332 * @see #BigInteger(java.lang.String, int)
3333 */
3334 public String toString(int radix) {
3335 if (signum == 0)
3336 return "0";
3337 if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
3338 radix = 10;
3339
3340 // If it's small enough, use smallToString.
3341 if (mag.length <= SCHOENHAGE_BASE_CONVERSION_THRESHOLD)
3342 return smallToString(radix);
3343
3344 // Otherwise use recursive toString, which requires positive arguments.
3345 // The results will be concatenated into this StringBuilder
3346 StringBuilder sb = new StringBuilder();
3347 if (signum < 0) {
3348 toString(this.negate(), sb, radix, 0);
3349 sb.insert(0, '-');
3350 }
3351 else
3352 toString(this, sb, radix, 0);
3353
3354 return sb.toString();
3355 }
3356
3357 /** This method is used to perform toString when arguments are small. */
3358 private String smallToString(int radix) {
3359 if (signum == 0)
3360 return "0";
3361
3362 // Compute upper bound on number of digit groups and allocate space
3363 int maxNumDigitGroups = (4*mag.length + 6)/7;
3364 String digitGroup[] = new String[maxNumDigitGroups];
3365
3366 // Translate number to string, a digit group at a time
3367 BigInteger tmp = this.abs();
3368 int numGroups = 0;
3369 while (tmp.signum != 0) {
3370 BigInteger d = longRadix[radix];
3371
3372 MutableBigInteger q = new MutableBigInteger(),
3373 a = new MutableBigInteger(tmp.mag),
3374 b = new MutableBigInteger(d.mag);
3375 MutableBigInteger r = a.divide(b, q);
3376 BigInteger q2 = q.toBigInteger(tmp.signum * d.signum);
3377 BigInteger r2 = r.toBigInteger(tmp.signum * d.signum);
3378
3379 digitGroup[numGroups++] = Long.toString(r2.longValue(), radix);
3380 tmp = q2;
3381 }
3382
3383 // Put sign (if any) and first digit group into result buffer
3384 StringBuilder buf = new StringBuilder(numGroups*digitsPerLong[radix]+1);
3385 if (signum<0)
3386 buf.append('-');
3387 buf.append(digitGroup[numGroups-1]);
3388
3389 // Append remaining digit groups padded with leading zeros
3390 for (int i=numGroups-2; i>=0; i--) {
3391 // Prepend (any) leading zeros for this digit group
3392 int numLeadingZeros = digitsPerLong[radix]-digitGroup[i].length();
3393 if (numLeadingZeros != 0)
3394 buf.append(zeros[numLeadingZeros]);
3395 buf.append(digitGroup[i]);
3396 }
3397 return buf.toString();
3398 }
3399
3400 /**
3401 * Converts the specified BigInteger to a string and appends to
3402 * <code>sb</code>. This implements the recursive Schoenhage algorithm
3403 * for base conversions.
3404 * <p/>
3405 * See Knuth, Donald, _The Art of Computer Programming_, Vol. 2,
3406 * Answers to Exercises (4.4) Question 14.
3407 *
3408 * @param u The number to convert to a string.
3409 * @param sb The StringBuilder that will be appended to in place.
3410 * @param radix The base to convert to.
3411 * @param digits The minimum number of digits to pad to.
3412 */
3413 private static void toString(BigInteger u, StringBuilder sb, int radix,
3414 int digits) {
3415 /* If we're smaller than a certain threshold, use the smallToString
3416 method, padding with leading zeroes when necessary. */
3417 if (u.mag.length <= SCHOENHAGE_BASE_CONVERSION_THRESHOLD) {
3418 String s = u.smallToString(radix);
3419
3420 // Pad with internal zeros if necessary.
3421 // Don't pad if we're at the beginning of the string.
3422 if ((s.length() < digits) && (sb.length() > 0))
3423 for (int i=s.length(); i<digits; i++) // May be a faster way to
3424 sb.append('0'); // do this?
3425
3426 sb.append(s);
3427 return;
3428 }
3429
3430 int b, n;
3431 b = u.bitLength();
3432
3433 // Calculate a value for n in the equation radix^(2^n) = u
3434 // and subtract 1 from that value. This is used to find the
3435 // cache index that contains the best value to divide u.
3436 n = (int) Math.round(Math.log(b * LOG_TWO / logCache[radix]) / LOG_TWO - 1.0);
3437 BigInteger v = getRadixConversionCache(radix, n);
3438 BigInteger[] results;
3439 results = u.divideAndRemainder(v);
3440
3441 int expectedDigits = 1 << n;
3442
3443 // Now recursively build the two halves of each number.
3444 toString(results[0], sb, radix, digits-expectedDigits);
3445 toString(results[1], sb, radix, expectedDigits);
3446 }
3447
3448 /**
3449 * Returns the value radix^(2^exponent) from the cache.
3450 * If this value doesn't already exist in the cache, it is added.
3451 * <p/>
3452 * This could be changed to a more complicated caching method using
3453 * <code>Future</code>.
3454 */
3455 private static synchronized BigInteger getRadixConversionCache(int radix,
3456 int exponent) {
3457 BigInteger retVal = null;
3458 ArrayList<BigInteger> cacheLine = powerCache[radix];
3459 int oldSize = cacheLine.size();
3460 if (exponent >= oldSize) {
3461 cacheLine.ensureCapacity(exponent+1);
3462 for (int i=oldSize; i<=exponent; i++) {
3463 retVal = cacheLine.get(i-1).square();
3464 cacheLine.add(i, retVal);
3465 }
3466 }
3467 else
3468 retVal = cacheLine.get(exponent);
3469
3470 return retVal;
3471 }
3472
3473 /* zero[i] is a string of i consecutive zeros. */
3474 private static String zeros[] = new String[64];
3475 static {
3476 zeros[63] =
3477 "000000000000000000000000000000000000000000000000000000000000000";
3478 for (int i=0; i<63; i++)
3479 zeros[i] = zeros[63].substring(0, i);
3480 }
3481
3482 /**
3483 * Returns the decimal String representation of this BigInteger.
3484 * The digit-to-character mapping provided by
3485 * {@code Character.forDigit} is used, and a minus sign is
3486 * prepended if appropriate. (This representation is compatible
3487 * with the {@link #BigInteger(String) (String)} constructor, and
3488 * allows for String concatenation with Java's + operator.)
3489 *
3490 * @return decimal String representation of this BigInteger.
3491 * @see Character#forDigit
|