693
694 private static byte[] randomBits(int numBits, Random rnd) {
695 if (numBits < 0)
696 throw new IllegalArgumentException("numBits must be non-negative");
697 int numBytes = (int)(((long)numBits+7)/8); // avoid overflow
698 byte[] randomBits = new byte[numBytes];
699
700 // Generate random bytes and mask out any excess bits
701 if (numBytes > 0) {
702 rnd.nextBytes(randomBits);
703 int excessBits = 8*numBytes - numBits;
704 randomBits[0] &= (1 << (8-excessBits)) - 1;
705 }
706 return randomBits;
707 }
708
709 /**
710 * Constructs a randomly generated positive BigInteger that is probably
711 * prime, with the specified bitLength.
712 *
713 * <p>It is recommended that the {@link #probablePrime probablePrime}
714 * method be used in preference to this constructor unless there
715 * is a compelling need to specify a certainty.
716 *
717 * @param bitLength bitLength of the returned BigInteger.
718 * @param certainty a measure of the uncertainty that the caller is
719 * willing to tolerate. The probability that the new BigInteger
720 * represents a prime number will exceed
721 * (1 - 1/2<sup>{@code certainty}</sup>). The execution time of
722 * this constructor is proportional to the value of this parameter.
723 * @param rnd source of random bits used to select candidates to be
724 * tested for primality.
725 * @throws ArithmeticException {@code bitLength < 2} or {@code bitLength} is too large.
726 * @see #bitLength()
727 */
728 public BigInteger(int bitLength, int certainty, Random rnd) {
729 BigInteger prime;
730
731 if (bitLength < 2)
732 throw new ArithmeticException("bitLength < 2");
733 prime = (bitLength < SMALL_PRIME_THRESHOLD
1140 /**
1141 * Throws an {@code ArithmeticException} if the {@code BigInteger} would be
1142 * out of the supported range.
1143 *
1144 * @throws ArithmeticException if {@code this} exceeds the supported range.
1145 */
1146 private void checkRange() {
1147 if (mag.length > MAX_MAG_LENGTH || mag.length == MAX_MAG_LENGTH && mag[0] < 0) {
1148 reportOverflow();
1149 }
1150 }
1151
1152 private static void reportOverflow() {
1153 throw new ArithmeticException("BigInteger would overflow supported range");
1154 }
1155
1156 //Static Factory Methods
1157
1158 /**
1159 * Returns a BigInteger whose value is equal to that of the
1160 * specified {@code long}. This "static factory method" is
1161 * provided in preference to a ({@code long}) constructor
1162 * because it allows for reuse of frequently used BigIntegers.
1163 *
1164 * @param val value of the BigInteger to return.
1165 * @return a BigInteger with the specified value.
1166 */
1167 public static BigInteger valueOf(long val) {
1168 // If -MAX_CONSTANT < val < MAX_CONSTANT, return stashed constant
1169 if (val == 0)
1170 return ZERO;
1171 if (val > 0 && val <= MAX_CONSTANT)
1172 return posConst[(int) val];
1173 else if (val < 0 && val >= -MAX_CONSTANT)
1174 return negConst[(int) -val];
1175
1176 return new BigInteger(val);
1177 }
1178
1179 /**
1180 * Constructs a BigInteger with the specified value, which may not be zero.
1181 */
1182 private BigInteger(long val) {
4017 int byteLen = bitLength()/8 + 1;
4018 byte[] byteArray = new byte[byteLen];
4019
4020 for (int i=byteLen-1, bytesCopied=4, nextInt=0, intIndex=0; i >= 0; i--) {
4021 if (bytesCopied == 4) {
4022 nextInt = getInt(intIndex++);
4023 bytesCopied = 1;
4024 } else {
4025 nextInt >>>= 8;
4026 bytesCopied++;
4027 }
4028 byteArray[i] = (byte)nextInt;
4029 }
4030 return byteArray;
4031 }
4032
4033 /**
4034 * Converts this BigInteger to an {@code int}. This
4035 * conversion is analogous to a
4036 * <i>narrowing primitive conversion</i> from {@code long} to
4037 * {@code int} as defined in section 5.1.3 of
4038 * <cite>The Java™ Language Specification</cite>:
4039 * if this BigInteger is too big to fit in an
4040 * {@code int}, only the low-order 32 bits are returned.
4041 * Note that this conversion can lose information about the
4042 * overall magnitude of the BigInteger value as well as return a
4043 * result with the opposite sign.
4044 *
4045 * @return this BigInteger converted to an {@code int}.
4046 * @see #intValueExact()
4047 */
4048 public int intValue() {
4049 int result = 0;
4050 result = getInt(0);
4051 return result;
4052 }
4053
4054 /**
4055 * Converts this BigInteger to a {@code long}. This
4056 * conversion is analogous to a
4057 * <i>narrowing primitive conversion</i> from {@code long} to
4058 * {@code int} as defined in section 5.1.3 of
4059 * <cite>The Java™ Language Specification</cite>:
4060 * if this BigInteger is too big to fit in a
4061 * {@code long}, only the low-order 64 bits are returned.
4062 * Note that this conversion can lose information about the
4063 * overall magnitude of the BigInteger value as well as return a
4064 * result with the opposite sign.
4065 *
4066 * @return this BigInteger converted to a {@code long}.
4067 * @see #longValueExact()
4068 */
4069 public long longValue() {
4070 long result = 0;
4071
4072 for (int i=1; i >= 0; i--)
4073 result = (result << 32) + (getInt(i) & LONG_MASK);
4074 return result;
4075 }
4076
4077 /**
4078 * Converts this BigInteger to a {@code float}. This
4079 * conversion is similar to the
4080 * <i>narrowing primitive conversion</i> from {@code double} to
4081 * {@code float} as defined in section 5.1.3 of
4082 * <cite>The Java™ Language Specification</cite>:
4083 * if this BigInteger has too great a magnitude
4084 * to represent as a {@code float}, it will be converted to
4085 * {@link Float#NEGATIVE_INFINITY} or {@link
4086 * Float#POSITIVE_INFINITY} as appropriate. Note that even when
4087 * the return value is finite, this conversion can lose
4088 * information about the precision of the BigInteger value.
4089 *
4090 * @return this BigInteger converted to a {@code float}.
4091 */
4092 public float floatValue() {
4093 if (signum == 0) {
4094 return 0.0f;
4095 }
4096
4097 int exponent = ((mag.length - 1) << 5) + bitLengthForInt(mag[0]) - 1;
4098
4099 // exponent == floor(log2(abs(this)))
4100 if (exponent < Long.SIZE - 1) {
4101 return longValue();
4102 } else if (exponent > Float.MAX_EXPONENT) {
4103 return signum > 0 ? Float.POSITIVE_INFINITY : Float.NEGATIVE_INFINITY;
4104 }
4105
4106 /*
4107 * We need the top SIGNIFICAND_WIDTH bits, including the "implicit"
4108 * one bit. To make rounding easier, we pick out the top
4109 * SIGNIFICAND_WIDTH + 1 bits, so we have one to help us round up or
4110 * down. twiceSignifFloor will contain the top SIGNIFICAND_WIDTH + 1
4145 && ((signifFloor & 1) != 0 || abs().getLowestSetBit() < shift);
4146 int signifRounded = increment ? signifFloor + 1 : signifFloor;
4147 int bits = ((exponent + FloatConsts.EXP_BIAS))
4148 << (FloatConsts.SIGNIFICAND_WIDTH - 1);
4149 bits += signifRounded;
4150 /*
4151 * If signifRounded == 2^24, we'd need to set all of the significand
4152 * bits to zero and add 1 to the exponent. This is exactly the behavior
4153 * we get from just adding signifRounded to bits directly. If the
4154 * exponent is Float.MAX_EXPONENT, we round up (correctly) to
4155 * Float.POSITIVE_INFINITY.
4156 */
4157 bits |= signum & FloatConsts.SIGN_BIT_MASK;
4158 return Float.intBitsToFloat(bits);
4159 }
4160
4161 /**
4162 * Converts this BigInteger to a {@code double}. This
4163 * conversion is similar to the
4164 * <i>narrowing primitive conversion</i> from {@code double} to
4165 * {@code float} as defined in section 5.1.3 of
4166 * <cite>The Java™ Language Specification</cite>:
4167 * if this BigInteger has too great a magnitude
4168 * to represent as a {@code double}, it will be converted to
4169 * {@link Double#NEGATIVE_INFINITY} or {@link
4170 * Double#POSITIVE_INFINITY} as appropriate. Note that even when
4171 * the return value is finite, this conversion can lose
4172 * information about the precision of the BigInteger value.
4173 *
4174 * @return this BigInteger converted to a {@code double}.
4175 */
4176 public double doubleValue() {
4177 if (signum == 0) {
4178 return 0.0;
4179 }
4180
4181 int exponent = ((mag.length - 1) << 5) + bitLengthForInt(mag[0]) - 1;
4182
4183 // exponent == floor(log2(abs(this))Double)
4184 if (exponent < Long.SIZE - 1) {
4185 return longValue();
4186 } else if (exponent > Double.MAX_EXPONENT) {
4187 return signum > 0 ? Double.POSITIVE_INFINITY : Double.NEGATIVE_INFINITY;
4188 }
4189
4190 /*
4191 * We need the top SIGNIFICAND_WIDTH bits, including the "implicit"
4192 * one bit. To make rounding easier, we pick out the top
4193 * SIGNIFICAND_WIDTH + 1 bits, so we have one to help us round up or
4194 * down. twiceSignifFloor will contain the top SIGNIFICAND_WIDTH + 1
|
693
694 private static byte[] randomBits(int numBits, Random rnd) {
695 if (numBits < 0)
696 throw new IllegalArgumentException("numBits must be non-negative");
697 int numBytes = (int)(((long)numBits+7)/8); // avoid overflow
698 byte[] randomBits = new byte[numBytes];
699
700 // Generate random bytes and mask out any excess bits
701 if (numBytes > 0) {
702 rnd.nextBytes(randomBits);
703 int excessBits = 8*numBytes - numBits;
704 randomBits[0] &= (1 << (8-excessBits)) - 1;
705 }
706 return randomBits;
707 }
708
709 /**
710 * Constructs a randomly generated positive BigInteger that is probably
711 * prime, with the specified bitLength.
712 *
713 * @apiNote It is recommended that the {@link #probablePrime probablePrime}
714 * method be used in preference to this constructor unless there
715 * is a compelling need to specify a certainty.
716 *
717 * @param bitLength bitLength of the returned BigInteger.
718 * @param certainty a measure of the uncertainty that the caller is
719 * willing to tolerate. The probability that the new BigInteger
720 * represents a prime number will exceed
721 * (1 - 1/2<sup>{@code certainty}</sup>). The execution time of
722 * this constructor is proportional to the value of this parameter.
723 * @param rnd source of random bits used to select candidates to be
724 * tested for primality.
725 * @throws ArithmeticException {@code bitLength < 2} or {@code bitLength} is too large.
726 * @see #bitLength()
727 */
728 public BigInteger(int bitLength, int certainty, Random rnd) {
729 BigInteger prime;
730
731 if (bitLength < 2)
732 throw new ArithmeticException("bitLength < 2");
733 prime = (bitLength < SMALL_PRIME_THRESHOLD
1140 /**
1141 * Throws an {@code ArithmeticException} if the {@code BigInteger} would be
1142 * out of the supported range.
1143 *
1144 * @throws ArithmeticException if {@code this} exceeds the supported range.
1145 */
1146 private void checkRange() {
1147 if (mag.length > MAX_MAG_LENGTH || mag.length == MAX_MAG_LENGTH && mag[0] < 0) {
1148 reportOverflow();
1149 }
1150 }
1151
1152 private static void reportOverflow() {
1153 throw new ArithmeticException("BigInteger would overflow supported range");
1154 }
1155
1156 //Static Factory Methods
1157
1158 /**
1159 * Returns a BigInteger whose value is equal to that of the
1160 * specified {@code long}.
1161 *
1162 * @apiNote This static factory method is provided in preference
1163 * to a ({@code long}) constructor because it allows for reuse of
1164 * frequently used BigIntegers.
1165 *
1166 * @param val value of the BigInteger to return.
1167 * @return a BigInteger with the specified value.
1168 */
1169 public static BigInteger valueOf(long val) {
1170 // If -MAX_CONSTANT < val < MAX_CONSTANT, return stashed constant
1171 if (val == 0)
1172 return ZERO;
1173 if (val > 0 && val <= MAX_CONSTANT)
1174 return posConst[(int) val];
1175 else if (val < 0 && val >= -MAX_CONSTANT)
1176 return negConst[(int) -val];
1177
1178 return new BigInteger(val);
1179 }
1180
1181 /**
1182 * Constructs a BigInteger with the specified value, which may not be zero.
1183 */
1184 private BigInteger(long val) {
4019 int byteLen = bitLength()/8 + 1;
4020 byte[] byteArray = new byte[byteLen];
4021
4022 for (int i=byteLen-1, bytesCopied=4, nextInt=0, intIndex=0; i >= 0; i--) {
4023 if (bytesCopied == 4) {
4024 nextInt = getInt(intIndex++);
4025 bytesCopied = 1;
4026 } else {
4027 nextInt >>>= 8;
4028 bytesCopied++;
4029 }
4030 byteArray[i] = (byte)nextInt;
4031 }
4032 return byteArray;
4033 }
4034
4035 /**
4036 * Converts this BigInteger to an {@code int}. This
4037 * conversion is analogous to a
4038 * <i>narrowing primitive conversion</i> from {@code long} to
4039 * {@code int} as defined in
4040 * <cite>The Java™ Language Specification</cite>:
4041 * if this BigInteger is too big to fit in an
4042 * {@code int}, only the low-order 32 bits are returned.
4043 * Note that this conversion can lose information about the
4044 * overall magnitude of the BigInteger value as well as return a
4045 * result with the opposite sign.
4046 *
4047 * @return this BigInteger converted to an {@code int}.
4048 * @see #intValueExact()
4049 * @jls 5.1.3 Narrowing Primitive Conversion
4050 */
4051 public int intValue() {
4052 int result = 0;
4053 result = getInt(0);
4054 return result;
4055 }
4056
4057 /**
4058 * Converts this BigInteger to a {@code long}. This
4059 * conversion is analogous to a
4060 * <i>narrowing primitive conversion</i> from {@code long} to
4061 * {@code int} as defined in
4062 * <cite>The Java™ Language Specification</cite>:
4063 * if this BigInteger is too big to fit in a
4064 * {@code long}, only the low-order 64 bits are returned.
4065 * Note that this conversion can lose information about the
4066 * overall magnitude of the BigInteger value as well as return a
4067 * result with the opposite sign.
4068 *
4069 * @return this BigInteger converted to a {@code long}.
4070 * @see #longValueExact()
4071 * @jls 5.1.3 Narrowing Primitive Conversion
4072 */
4073 public long longValue() {
4074 long result = 0;
4075
4076 for (int i=1; i >= 0; i--)
4077 result = (result << 32) + (getInt(i) & LONG_MASK);
4078 return result;
4079 }
4080
4081 /**
4082 * Converts this BigInteger to a {@code float}. This
4083 * conversion is similar to the
4084 * <i>narrowing primitive conversion</i> from {@code double} to
4085 * {@code float} as defined in
4086 * <cite>The Java™ Language Specification</cite>:
4087 * if this BigInteger has too great a magnitude
4088 * to represent as a {@code float}, it will be converted to
4089 * {@link Float#NEGATIVE_INFINITY} or {@link
4090 * Float#POSITIVE_INFINITY} as appropriate. Note that even when
4091 * the return value is finite, this conversion can lose
4092 * information about the precision of the BigInteger value.
4093 *
4094 * @return this BigInteger converted to a {@code float}.
4095 * @jls 5.1.3 Narrowing Primitive Conversion
4096 */
4097 public float floatValue() {
4098 if (signum == 0) {
4099 return 0.0f;
4100 }
4101
4102 int exponent = ((mag.length - 1) << 5) + bitLengthForInt(mag[0]) - 1;
4103
4104 // exponent == floor(log2(abs(this)))
4105 if (exponent < Long.SIZE - 1) {
4106 return longValue();
4107 } else if (exponent > Float.MAX_EXPONENT) {
4108 return signum > 0 ? Float.POSITIVE_INFINITY : Float.NEGATIVE_INFINITY;
4109 }
4110
4111 /*
4112 * We need the top SIGNIFICAND_WIDTH bits, including the "implicit"
4113 * one bit. To make rounding easier, we pick out the top
4114 * SIGNIFICAND_WIDTH + 1 bits, so we have one to help us round up or
4115 * down. twiceSignifFloor will contain the top SIGNIFICAND_WIDTH + 1
4150 && ((signifFloor & 1) != 0 || abs().getLowestSetBit() < shift);
4151 int signifRounded = increment ? signifFloor + 1 : signifFloor;
4152 int bits = ((exponent + FloatConsts.EXP_BIAS))
4153 << (FloatConsts.SIGNIFICAND_WIDTH - 1);
4154 bits += signifRounded;
4155 /*
4156 * If signifRounded == 2^24, we'd need to set all of the significand
4157 * bits to zero and add 1 to the exponent. This is exactly the behavior
4158 * we get from just adding signifRounded to bits directly. If the
4159 * exponent is Float.MAX_EXPONENT, we round up (correctly) to
4160 * Float.POSITIVE_INFINITY.
4161 */
4162 bits |= signum & FloatConsts.SIGN_BIT_MASK;
4163 return Float.intBitsToFloat(bits);
4164 }
4165
4166 /**
4167 * Converts this BigInteger to a {@code double}. This
4168 * conversion is similar to the
4169 * <i>narrowing primitive conversion</i> from {@code double} to
4170 * {@code float} as defined in
4171 * <cite>The Java™ Language Specification</cite>:
4172 * if this BigInteger has too great a magnitude
4173 * to represent as a {@code double}, it will be converted to
4174 * {@link Double#NEGATIVE_INFINITY} or {@link
4175 * Double#POSITIVE_INFINITY} as appropriate. Note that even when
4176 * the return value is finite, this conversion can lose
4177 * information about the precision of the BigInteger value.
4178 *
4179 * @return this BigInteger converted to a {@code double}.
4180 * @jls 5.1.3 Narrowing Primitive Conversion
4181 */
4182 public double doubleValue() {
4183 if (signum == 0) {
4184 return 0.0;
4185 }
4186
4187 int exponent = ((mag.length - 1) << 5) + bitLengthForInt(mag[0]) - 1;
4188
4189 // exponent == floor(log2(abs(this))Double)
4190 if (exponent < Long.SIZE - 1) {
4191 return longValue();
4192 } else if (exponent > Double.MAX_EXPONENT) {
4193 return signum > 0 ? Double.POSITIVE_INFINITY : Double.NEGATIVE_INFINITY;
4194 }
4195
4196 /*
4197 * We need the top SIGNIFICAND_WIDTH bits, including the "implicit"
4198 * one bit. To make rounding easier, we pick out the top
4199 * SIGNIFICAND_WIDTH + 1 bits, so we have one to help us round up or
4200 * down. twiceSignifFloor will contain the top SIGNIFICAND_WIDTH + 1
|