# 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 the factorial of anything above 21, you need to use the BigInteger class from java.math package. As the name suggests, BigInteger class is designed to hold really large integer value, something which is even bigger than the maximum value of long primitive e.g. 2^63 -1 or 9223372036854775807L. You also need to change the way we calculate factorial for a 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 it's important to store the result back into the same variable, otherwise, the result of the 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 provides support for modular arithmetic, bit manipulation, primality testing, prime generation, GCD calculation and other miscellaneous operations.

### 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, the 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 the 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 it's not possible to use long data type to store such huge integral values. You need to use BigInteger class to store such big values.

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: 189 Programming Questions and Solutions, one of the best book for preparing coding interviews.

### 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 it's very important that you make yourself familiar with the 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 provides support for the 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.

Further Learning
Algorithms and Data Structures - Part 1 and 2
Java Fundamentals, Part 1 and 2
Cracking the Coding Interview - 189 Questions and Solutions

If you are looking for some handy Java programming exercise then don't forget to check out following posts and some good books :
• How to swap two integers without using a temporary variable in Java? (solution)
• How to print all permutations of a String in Java? (solution)
• How to reverse an 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)

Anshdeep singh said...

There is a error in the code...In the for loop, the condition should be i>0

Anonymous said...

there's a typo in for-llop, it should be: i > 0

Javin Paul said...

Hello @Ansdeep and @Annonymous, yes that was a typo, corrected now. Thanks for pointing it.

Neha said...

what plugin are you using to format your code in your blog? as far as I know there is no built in mechanism in Google Blog to format code.

Javin Paul said...

@Neha, I use online syntax highlighters and then use the HTML directly in blogger.