1025 * BigInteger will reference the input array if feasible).
1026 */
1027 private static BigInteger valueOf(int val[]) {
1028 return (val[0]>0 ? new BigInteger(val, 1) : new BigInteger(val));
1029 }
1030
1031 // Constants
1032
1033 /**
1034 * Initialize static constant array when class is loaded.
1035 */
1036 private final static int MAX_CONSTANT = 16;
1037 private static BigInteger posConst[] = new BigInteger[MAX_CONSTANT+1];
1038 private static BigInteger negConst[] = new BigInteger[MAX_CONSTANT+1];
1039
1040 /**
1041 * The cache of powers of each radix. This allows us to not have to
1042 * recalculate powers of radix^(2^n) more than once. This speeds
1043 * Schoenhage recursive base conversion significantly.
1044 */
1045 private static ArrayList<BigInteger>[] powerCache;
1046
1047 /** The cache of logarithms of radices for base conversion. */
1048 private static final double[] logCache;
1049
1050 /** The natural log of 2. This is used in computing cache indices. */
1051 private static final double LOG_TWO = Math.log(2.0);
1052
1053 static {
1054 for (int i = 1; i <= MAX_CONSTANT; i++) {
1055 int[] magnitude = new int[1];
1056 magnitude[0] = i;
1057 posConst[i] = new BigInteger(magnitude, 1);
1058 negConst[i] = new BigInteger(magnitude, -1);
1059 }
1060
1061 /*
1062 * Initialize the cache of radix^(2^x) values used for base conversion
1063 * with just the very first value. Additional values will be created
1064 * on demand.
1065 */
1066 powerCache = (ArrayList<BigInteger>[])
1067 new ArrayList[Character.MAX_RADIX+1];
1068 logCache = new double[Character.MAX_RADIX+1];
1069
1070 for (int i=Character.MIN_RADIX; i<=Character.MAX_RADIX; i++)
1071 {
1072 powerCache[i] = new ArrayList<BigInteger>(1);
1073 powerCache[i].add(BigInteger.valueOf(i));
1074 logCache[i] = Math.log(i);
1075 }
1076 }
1077
1078 /**
1079 * The BigInteger constant zero.
1080 *
1081 * @since 1.2
1082 */
1083 public static final BigInteger ZERO = new BigInteger(new int[0], 0);
1084
1085 /**
1086 * The BigInteger constant one.
1087 *
1088 * @since 1.2
1089 */
1090 public static final BigInteger ONE = valueOf(1);
1091
1092 /**
1093 * The BigInteger constant two. (Not exported.)
3437 // cache index that contains the best value to divide u.
3438 n = (int) Math.round(Math.log(b * LOG_TWO / logCache[radix]) / LOG_TWO - 1.0);
3439 BigInteger v = getRadixConversionCache(radix, n);
3440 BigInteger[] results;
3441 results = u.divideAndRemainder(v);
3442
3443 int expectedDigits = 1 << n;
3444
3445 // Now recursively build the two halves of each number.
3446 toString(results[0], sb, radix, digits-expectedDigits);
3447 toString(results[1], sb, radix, expectedDigits);
3448 }
3449
3450 /**
3451 * Returns the value radix^(2^exponent) from the cache.
3452 * If this value doesn't already exist in the cache, it is added.
3453 * <p/>
3454 * This could be changed to a more complicated caching method using
3455 * <code>Future</code>.
3456 */
3457 private static synchronized BigInteger getRadixConversionCache(int radix,
3458 int exponent) {
3459 BigInteger retVal = null;
3460 ArrayList<BigInteger> cacheLine = powerCache[radix];
3461 int oldSize = cacheLine.size();
3462 if (exponent >= oldSize) {
3463 cacheLine.ensureCapacity(exponent+1);
3464 for (int i=oldSize; i<=exponent; i++) {
3465 retVal = cacheLine.get(i-1).square();
3466 cacheLine.add(i, retVal);
3467 }
3468 }
3469 else
3470 retVal = cacheLine.get(exponent);
3471
3472 return retVal;
3473 }
3474
3475 /* zero[i] is a string of i consecutive zeros. */
3476 private static String zeros[] = new String[64];
3477 static {
3478 zeros[63] =
3479 "000000000000000000000000000000000000000000000000000000000000000";
3480 for (int i=0; i<63; i++)
3481 zeros[i] = zeros[63].substring(0, i);
3482 }
3483
3484 /**
3485 * Returns the decimal String representation of this BigInteger.
3486 * The digit-to-character mapping provided by
3487 * {@code Character.forDigit} is used, and a minus sign is
3488 * prepended if appropriate. (This representation is compatible
3489 * with the {@link #BigInteger(String) (String)} constructor, and
3490 * allows for String concatenation with Java's + operator.)
3491 *
3492 * @return decimal String representation of this BigInteger.
|
1025 * BigInteger will reference the input array if feasible).
1026 */
1027 private static BigInteger valueOf(int val[]) {
1028 return (val[0]>0 ? new BigInteger(val, 1) : new BigInteger(val));
1029 }
1030
1031 // Constants
1032
1033 /**
1034 * Initialize static constant array when class is loaded.
1035 */
1036 private final static int MAX_CONSTANT = 16;
1037 private static BigInteger posConst[] = new BigInteger[MAX_CONSTANT+1];
1038 private static BigInteger negConst[] = new BigInteger[MAX_CONSTANT+1];
1039
1040 /**
1041 * The cache of powers of each radix. This allows us to not have to
1042 * recalculate powers of radix^(2^n) more than once. This speeds
1043 * Schoenhage recursive base conversion significantly.
1044 */
1045 private static volatile BigInteger[][] powerCache;
1046
1047 /** The cache of logarithms of radices for base conversion. */
1048 private static final double[] logCache;
1049
1050 /** The natural log of 2. This is used in computing cache indices. */
1051 private static final double LOG_TWO = Math.log(2.0);
1052
1053 static {
1054 for (int i = 1; i <= MAX_CONSTANT; i++) {
1055 int[] magnitude = new int[1];
1056 magnitude[0] = i;
1057 posConst[i] = new BigInteger(magnitude, 1);
1058 negConst[i] = new BigInteger(magnitude, -1);
1059 }
1060
1061 /*
1062 * Initialize the cache of radix^(2^x) values used for base conversion
1063 * with just the very first value. Additional values will be created
1064 * on demand.
1065 */
1066 powerCache = new BigInteger[Character.MAX_RADIX+1][];
1067 logCache = new double[Character.MAX_RADIX+1];
1068
1069 for (int i=Character.MIN_RADIX; i<=Character.MAX_RADIX; i++)
1070 {
1071 powerCache[i] = new BigInteger[] { 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.)
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 BigInteger getRadixConversionCache(int radix, int exponent) {
3456 BigInteger[] cacheLine = powerCache[radix]; // volatile read
3457 if (exponent < cacheLine.length) {
3458 return cacheLine[exponent];
3459 }
3460
3461 int oldLength = cacheLine.length;
3462 cacheLine = Arrays.copyOf(cacheLine, exponent + 1);
3463 for (int i = oldLength; i <= exponent; i++) {
3464 cacheLine[i] = cacheLine[i - 1].pow(2);
3465 }
3466
3467 BigInteger[][] pc = powerCache; // volatile read again
3468 if (exponent >= pc[radix].length) {
3469 pc = pc.clone();
3470 pc[radix] = cacheLine;
3471 powerCache = pc; // volatile write, publish
3472 }
3473 return cacheLine[exponent];
3474 }
3475
3476 /* zero[i] is a string of i consecutive zeros. */
3477 private static String zeros[] = new String[64];
3478 static {
3479 zeros[63] =
3480 "000000000000000000000000000000000000000000000000000000000000000";
3481 for (int i=0; i<63; i++)
3482 zeros[i] = zeros[63].substring(0, i);
3483 }
3484
3485 /**
3486 * Returns the decimal String representation of this BigInteger.
3487 * The digit-to-character mapping provided by
3488 * {@code Character.forDigit} is used, and a minus sign is
3489 * prepended if appropriate. (This representation is compatible
3490 * with the {@link #BigInteger(String) (String)} constructor, and
3491 * allows for String concatenation with Java's + operator.)
3492 *
3493 * @return decimal String representation of this BigInteger.
|