35 import java.io.ObjectStreamField; 36 import java.util.Arrays; 37 import java.util.Objects; 38 import java.util.Random; 39 import java.util.concurrent.ThreadLocalRandom; 40 41 import jdk.internal.math.DoubleConsts; 42 import jdk.internal.math.FloatConsts; 43 import jdk.internal.HotSpotIntrinsicCandidate; 44 45 /** 46 * Immutable arbitrary-precision integers. All operations behave as if 47 * BigIntegers were represented in two's-complement notation (like Java's 48 * primitive integer types). BigInteger provides analogues to all of Java's 49 * primitive integer operators, and all relevant methods from java.lang.Math. 50 * Additionally, BigInteger provides operations for modular arithmetic, GCD 51 * calculation, primality testing, prime generation, bit manipulation, 52 * and a few other miscellaneous operations. 53 * 54 * <p>Semantics of arithmetic operations exactly mimic those of Java's integer 55 * arithmetic operators, as defined in <i>The Java Language Specification</i>. 56 * For example, division by zero throws an {@code ArithmeticException}, and 57 * division of a negative by a positive yields a negative (or zero) remainder. 58 * All of the details in the Spec concerning overflow are ignored, as 59 * BigIntegers are made as large as necessary to accommodate the results of an 60 * operation. 61 * 62 * <p>Semantics of shift operations extend those of Java's shift operators 63 * to allow for negative shift distances. A right-shift with a negative 64 * shift distance results in a left shift, and vice-versa. The unsigned 65 * right shift operator ({@code >>>}) is omitted, as this operation makes 66 * little sense in combination with the "infinite word size" abstraction 67 * provided by this class. 68 * 69 * <p>Semantics of bitwise logical operations exactly mimic those of Java's 70 * bitwise integer operators. The binary operators ({@code and}, 71 * {@code or}, {@code xor}) implicitly perform sign extension on the shorter 72 * of the two operands prior to performing the operation. 73 * 74 * <p>Comparison operations perform signed integer comparisons, analogous to 75 * those performed by Java's relational and equality operators. 76 * 77 * <p>Modular arithmetic operations are provided to compute residues, perform 78 * exponentiation, and compute multiplicative inverses. These methods always 79 * return a non-negative result, between {@code 0} and {@code (modulus - 1)}, 80 * inclusive. 81 * 82 * <p>Bit operations operate on a single bit of the two's-complement 83 * representation of their operand. If necessary, the operand is sign- 84 * extended so that it contains the designated bit. None of the single-bit 85 * operations can produce a BigInteger with a different sign from the 86 * BigInteger being operated on, as they affect only a single bit, and the 87 * "infinite word size" abstraction provided by this class ensures that there 88 * are infinitely many "virtual sign bits" preceding each BigInteger. 89 * 90 * <p>For the sake of brevity and clarity, pseudo-code is used throughout the 91 * descriptions of BigInteger methods. The pseudo-code expression 92 * {@code (i + j)} is shorthand for "a BigInteger whose value is 93 * that of the BigInteger {@code i} plus that of the BigInteger {@code j}." 94 * The pseudo-code expression {@code (i == j)} is shorthand for 95 * "{@code true} if and only if the BigInteger {@code i} represents the same 96 * value as the BigInteger {@code j}." Other pseudo-code expressions are 97 * interpreted similarly. 98 * 99 * <p>All methods and constructors in this class throw 100 * {@code NullPointerException} when passed 101 * a null object reference for any input parameter. 102 * 103 * BigInteger must support values in the range 104 * -2<sup>{@code Integer.MAX_VALUE}</sup> (exclusive) to 105 * +2<sup>{@code Integer.MAX_VALUE}</sup> (exclusive) 106 * and may support values outside of that range. 107 * 108 * The range of probable prime values is limited and may be less than 109 * the full supported positive range of {@code BigInteger}. 110 * The range must be at least 1 to 2<sup>500000000</sup>. 111 * 112 * @implNote 113 * BigInteger constructors and operations throw {@code ArithmeticException} when 114 * the result is out of the supported range of 115 * -2<sup>{@code Integer.MAX_VALUE}</sup> (exclusive) to 116 * +2<sup>{@code Integer.MAX_VALUE}</sup> (exclusive). 117 * 118 * @see BigDecimal 119 * @jls 4.2.2 Integer Operations 120 * @author Josh Bloch 121 * @author Michael McCloskey 122 * @author Alan Eliasen 123 * @author Timothy Buktu 124 * @since 1.1 125 */ 126 127 public class BigInteger extends Number implements Comparable<BigInteger> { 128 /** 129 * The signum of this BigInteger: -1 for negative, 0 for zero, or 130 * 1 for positive. Note that the BigInteger zero <em>must</em> have 131 * a signum of 0. This is necessary to ensures that there is exactly one 132 * representation for each BigInteger value. 133 */ 134 final int signum; | 35 import java.io.ObjectStreamField; 36 import java.util.Arrays; 37 import java.util.Objects; 38 import java.util.Random; 39 import java.util.concurrent.ThreadLocalRandom; 40 41 import jdk.internal.math.DoubleConsts; 42 import jdk.internal.math.FloatConsts; 43 import jdk.internal.HotSpotIntrinsicCandidate; 44 45 /** 46 * Immutable arbitrary-precision integers. All operations behave as if 47 * BigIntegers were represented in two's-complement notation (like Java's 48 * primitive integer types). BigInteger provides analogues to all of Java's 49 * primitive integer operators, and all relevant methods from java.lang.Math. 50 * Additionally, BigInteger provides operations for modular arithmetic, GCD 51 * calculation, primality testing, prime generation, bit manipulation, 52 * and a few other miscellaneous operations. 53 * 54 * <p>Semantics of arithmetic operations exactly mimic those of Java's integer 55 * arithmetic operators, as defined in <i>The Java™ Language Specification</i>. 56 * For example, division by zero throws an {@code ArithmeticException}, and 57 * division of a negative by a positive yields a negative (or zero) remainder. 58 * 59 * <p>Semantics of shift operations extend those of Java's shift operators 60 * to allow for negative shift distances. A right-shift with a negative 61 * shift distance results in a left shift, and vice-versa. The unsigned 62 * right shift operator ({@code >>>}) is omitted, as this operation makes 63 * little sense in combination with the arbitrarily large abstraction 64 * provided by this class. 65 * 66 * <p>Semantics of bitwise logical operations exactly mimic those of Java's 67 * bitwise integer operators. The binary operators ({@code and}, 68 * {@code or}, {@code xor}) implicitly perform sign extension on the shorter 69 * of the two operands prior to performing the operation. 70 * 71 * <p>Comparison operations perform signed integer comparisons, analogous to 72 * those performed by Java's relational and equality operators. 73 * 74 * <p>Modular arithmetic operations are provided to compute residues, perform 75 * exponentiation, and compute multiplicative inverses. These methods always 76 * return a non-negative result, between {@code 0} and {@code (modulus - 1)}, 77 * inclusive. 78 * 79 * <p>Bit operations operate on a single bit of the two's-complement 80 * representation of their operand. If necessary, the operand is sign- 81 * extended so that it contains the designated bit. None of the single-bit 82 * operations can produce a BigInteger with a different sign from the 83 * BigInteger being operated on, as they affect only a single bit, and the 84 * arbitrarily large abstraction provided by this class ensures that conceptually 85 * there are infinitely many "virtual sign bits" preceding each BigInteger. 86 * 87 * <p>For the sake of brevity and clarity, pseudo-code is used throughout the 88 * descriptions of BigInteger methods. The pseudo-code expression 89 * {@code (i + j)} is shorthand for "a BigInteger whose value is 90 * that of the BigInteger {@code i} plus that of the BigInteger {@code j}." 91 * The pseudo-code expression {@code (i == j)} is shorthand for 92 * "{@code true} if and only if the BigInteger {@code i} represents the same 93 * value as the BigInteger {@code j}." Other pseudo-code expressions are 94 * interpreted similarly. 95 * 96 * <p>All methods and constructors in this class throw 97 * {@code NullPointerException} when passed 98 * a null object reference for any input parameter. 99 * 100 * BigInteger must support values in the range 101 * -2<sup>{@code Integer.MAX_VALUE}</sup> (exclusive) to 102 * +2<sup>{@code Integer.MAX_VALUE}</sup> (exclusive) 103 * and may support values outside of that range. 104 * 105 * An {@code ArithmeticException} is thrown when a BigInteger 106 * constructor or method would generate a value outside of the 107 * supported range. 108 * 109 * The range of probable prime values is limited and may be less than 110 * the full supported positive range of {@code BigInteger}. 111 * The range must be at least 1 to 2<sup>500000000</sup>. 112 * 113 * @implNote 114 * In the reference implementation, BigInteger constructors and 115 * operations throw {@code ArithmeticException} when the result is out 116 * of the supported range of 117 * -2<sup>{@code Integer.MAX_VALUE}</sup> (exclusive) to 118 * +2<sup>{@code Integer.MAX_VALUE}</sup> (exclusive). 119 * 120 * @see BigDecimal 121 * @jls 4.2.2 Integer Operations 122 * @author Josh Bloch 123 * @author Michael McCloskey 124 * @author Alan Eliasen 125 * @author Timothy Buktu 126 * @since 1.1 127 */ 128 129 public class BigInteger extends Number implements Comparable<BigInteger> { 130 /** 131 * The signum of this BigInteger: -1 for negative, 0 for zero, or 132 * 1 for positive. Note that the BigInteger zero <em>must</em> have 133 * a signum of 0. This is necessary to ensures that there is exactly one 134 * representation for each BigInteger value. 135 */ 136 final int signum; |