BigInteger Class In Java

1. Introduction

Java provides four primitive types dedicated to integer manipulation. Depending on the range of the number you manipulate, you may use byte, short, int, or long. Long is the largest primitive type for integers, with a range of [$-2^{64}$, $2^{64} – 1$]. Some computing programs (cryptographic algorithms for example) require the manipulation of numbers that fall out of the range of the long type. For this kind of program, BigInteger is the designated class from the Java language. In this article, you’ll learn how to create and manipulate BigIntegers in your Java applications.

2. What is a BigInteger?

According to its Javadoc, a BigInteger represents an immutable, arbitrary-precision integer.

Immutable: Each operation on a BigInteger returns a new object
Arbitrary precision: BigInteger can manipulate very large numbers: $-2^{Integer.MAX_VALUE}$ (exclusive) to $+2^{Integer.MAX_VALUE}$ (exclusive).

In its internal representation, the BigInteger class uses an array of integers to store the digits of the magnitude, and an integer to store the sign of the number. All operations on BigIntegers behave as if they were represented in two’s-complement notation.

There are three main ways of creating a BigInteger: using constructors, using the static factory methods BigInteger#valueOf(), and using the BigInteger class constant values.

3. BigInteger Constructors

BigInteger offers multiple constructors with different parameter types: byte[], String, etc. Some of the constructors allow you to generate random BigIntegers based on the bit length. In this section, we will provide some of the most used constructors.

3.1. Creating BigIntegers from Strings

3.1.1. BigInteger(String val)

This constructor allows BigInteger creation from a string. The string must be a valid representation of a biginteger in the decimal system, else a NumberFormatException will be raised. From a practical point of view, the input value might come from a text file or an external API.

        BigInteger bigInteger1 = new BigInteger("123456789");

3.1.2. BigInteger(String val, int radix)

You can also construct a BigInteger from a string in a different numeral system than 10. For that, there is another constructor that takes an extra parameter radix.

        BigInteger bigIntegerBase2 = new BigInteger("10000",2);//10000 in base 2, i.e. 16

3.2. Creating Random BigIntegers

Java proposes two constructors to generate random BigIntegers.

3.2.1. BigInteger(int bitLength, int certainty, Random rnd)

This constructor generates a random biginteger that is probably prime with the given bit length.

        BigInteger probablyPrimeNumber = new BigInteger(5,1,new Random());//certainty=1 -> probably prime number
    BigInteger probablyCompositeNumber = new BigInteger(5,0,new Random());//certainty=0 -> probably composite number

3.2.2. BigInteger(int numBits, Random rnd)

Use this if you need to build randomly generated bigintegers, uniformly distributed over the range 0 to ($2^{numBits} – 1$), inclusive.

    BigInteger uniformlyDistributedBigInteger = new BigInteger(5,new Random());//any number from 0 to 31

4. BigInteger Static Factory Methods

4.1. Creating BigIntegers from Long Values

This method creates a BigInteger from a long value. The method enables caching for frequently used values.

        BigInteger bigInteger = BigInteger.valueOf(123456789L);

4.2. probablePrime(int bitLength, Random rnd)

You can also generate a BigInteger with a given bit length. The method will return a BigInteger which is probably a prime number.

        BigInteger probablyPrimeNumber = BigInteger.probablePrime(5,new Random());//17 or 19 or 23 or 29 or 31

According to the Javadoc, the probability that the generated number is composite (not prime) cannot exceed $2^{-200}$. Therefore, this is the most efficient way to obtain a large prime number in your Java code.

5. BigInteger Constants

BigInteger provides some constants for commonly used values: ZERO, ONE, TEN, etc.

        BigInteger zero = BigInteger.ZERO;
        BigInteger one = BigInteger.ONE;
        BigInteger ten = BigInteger.TEN;

All these constants, except ZERO, internally call the valueOf() method.

6. Operations on BigIntegers

6.1. Arithmetic Operations

6.1.1. Basic Arithmetic Operations

BigInteger provides methods to perform all the basic arithmetic operations: add, subtract, divide, and multiply. You can also use the BigInteger class to perform some advanced arithmetic operations like obtaining the greatest common divisor(gcd) of two numbers.

        BigInteger val1 = BigInteger.valueOf(5);
        BigInteger val2 = BigInteger.TWO;

        BigInteger val3 = val1.add(val2); // 7;
        BigInteger val4 = val1.subtract(val2); // 3
        BigInteger val5 = val1.multiply(val2); // 10
        BigInteger val6 = val1.divide(val2); // 2 --> integer division
        BigInteger gcd = val1.gcd(val2); // 1

6.1.2. Comparing BigIntegers

Using BigInteger#compareTo()

BigInteger implements the Comparable interface and provides a compareTo() method to compare two BigInteger objects.

        BigInteger val1 = BigInteger.valueOf(5);
        BigInteger val2 = BigInteger.TWO;

        int value = val1.compareTo(val2);//1 because 5 > 2

Using BigInteger#equals()

BigInteger overrides the Object#equals() method and provides a convenient way of comparing two BigIntegers for equality.

        BigInteger val3 = BigInteger.TEN;
        BigInteger val4 = BigInteger.valueOf(10);

        boolean result = val3.equals(val4);//true

Info: This method checks for numeric equality, not reference(object) equality.

6.2. Bit Manipulation

BigInteger also provides some methods to perform bit-level operations: and, or, shift left, shift right, etc.

        BigInteger val1 = BigInteger.valueOf(8);
        BigInteger val2 = val1.shiftLeft(1);// 16
        BigInteger val3 = val1.shiftRight(1);// 4

7. Common Use Cases for BigIntegers

For most programs manipulating integers, the int and long data types are enough as they’ll provide better performance. However, in some specific situations, BigInteger is the recommended type. Here are common situations:

Cryptography: Cryptographic algorithms such as RSA encryption, often work with very large numbers.
Financial Applications: BigInteger is very useful for financial models involving the manipulation of very large sums(compound interest, large portfolios).
Mathematical Research: Some mathematical topics require the manipulation of very large integral numbers: factorial calculation, combinatorics, number theory, etc.

8. Conclusion

In this tutorial, you learned about the BigInteger class, which is the recommended Java class for high-performance computations involving very large integers.
You can find the complete code of this article here in GitHub.

Noel Kamphoa