How to calculate Large Factorials using BigInteger in Java?

Factorial of numbers greater than or equal to 13 cannot be found using primitive int data type as shown in our earlier factorial solution due to overflow. These factorials are too large to fit in an int variable, whose maximum value is just 2147483647 (2^31 -1). Even if we use the long data type, factorials greater than or equal to 21 will generate an overflow. To find factorial of anything above 21, you need to use the BigInteger class from java.math package. As name suggests, BigInteger class is designed to hold really large integer value, something which is even bigger than maximum value of long primitive e.g. 2^63 -1 or 9223372036854775807L. You also need to change the way we calculate factorial for smaller number. You can not use recursion to calculate factorial of a larger number instead we need to use for loop for that.


Also worth noting that, similar to java.lang.String and other wrapper classes BigInteger is also Immutable in Java, which means its important to store result back into same variable, otherwise result of calculation will be lost. BigInteger stores numbers as 2's complement number like int primitive and support operation supported by int variables and all relevant methods from java.lang.Math class. Additionally it also provide support for modular arithmetic, bit manipulation, primality testing, prime generation, GCD calculation and other miscellaneous operations. BTW, If you are looking for some programming exercise to prepare coding interview or to developer your programming logic then you should check problems from Cracking the Coding Interview: 150 Programming Questions and Solutions, one of the best book for preparing coding interviews.

Java Program to Calculate Factorial of Large Number

Here is our sample Java program to calculate factorial for large numbers, well given number is not exactly large but the factorial value is definitely large. For example, factorial of 45 is 119622220865480194561963161495657715064383733760000000000, which is clearly out of bound for even a long data type. Since theoretically BigInteger has no limit it can hold these values as shown in following example. You will also notice that instead of recursion, we have used iteration to calculate factorial in Java.

import java.math.BigInteger;

/**
 * Write a Java program to calculate factorial of large numbers using
 * BigInteger.
 *
 * @author WINDOWS 8
 *
 */
public class LargeFactorialDemo {

    public static void main(String args[]) {

        System.out.printf("Factorial of 32 is %s %n", factorial(32));
        System.out.printf("Factorial of 0 is %s %n", factorial(0));
        System.out.printf("Factorial of 1 is %s %n", factorial(1));
        System.out.printf("Factorial of 5 is %s %n", factorial(5));
        System.out.printf("Factorial of 41 is %s %n", factorial(41));
        System.out.printf("Factorial of 45 is %s %n", factorial(45));

    }

    /*
     * Java method to calculate factorial of a large number
     * @return BigInteger factorial of given number
     */
    public static BigInteger factorial(int number) {
        BigInteger factorial = BigInteger.ONE;

        for (int i = number; i > 0; i--) {
            factorial = factorial.multiply(BigInteger.valueOf(i));
        }

        return factorial;
    }

}

Output
Factorial of 32 is 263130836933693530167218012160000000
Factorial of 0 is 1
Factorial of 1 is 1
Factorial of 5 is 120
Factorial of 41 is 33452526613163807108170062053440751665152000000000
Factorial of 45 is 119622220865480194561963161495657715064383733760000000000

You can see that how large factorial of 45 is, clearly its not possible to use long data type to store such huge integral values. You need to use BigInteger class to store such big values.

Important things about BigInteger class in Java

BigInteger class in Java is designed to deal with really large numbers in Java, but to do that its very important that you make yourself familiar with class. Here are some key points about java.math.BigInteger class :

1. The BigInteger class is used to represent arbitrarily large numbers. Overflow doesn't occur as is the case with int and long primitive.

2. The BigInteger class is immutable which means that the object on which the multiply function was invoked doesn't change the integer it is holding. The multiplication is performed and a new BigInteger is returned which needs to be stored in the variable fact.

3. BigInteger provides operations similar to int primitive type in Java, additionally it provide support for prime generation, bit manipulation, GCD calculations etc.

4. You can create BigInteger object by giving number as String or byte array using constructor, or you can convert a long value to BigInteger using valueOf() method as shown below :

BigInteger bigIntegerFromLong = BigInteger.valueOf(292909333L); 
BigInteger bigIntegerFromString = new BigInteger("338948938948");

Remember BigInteger can help you to deal with really large numbers in Java.

That's all about how to calculate factorial of a large number in Java. Clearly after some point long is not enough to result of factorial and you need something bigger than long but not double, BigInteger is the class to represent large integral values. In theory, BigInteger has no limit and it can represent any integral value till infinity.

If you are looking for some handy Java programming exercise then don't forget to checkout following posts and some good books :

• How to swap two integers without using temporary variable in Java? (solution)
• How to print all permutations of a String in Java? (solution)
• How to reverse array in place in Java? (answer)
• How to check if given String is Palindrome in Java? (solution)
• How to write FizzBuzz in Java 8? (answer)
• How to reverse Integer in Java? (solution)
• How to find first non repeated character from String? (solution)
• Questions from Coding Puzzles: Thinking in code By codingtmd? (see here)
• Questions from Programming Interviews Exposed: Secrets to Landing Your Next Job? (see here)