Tuesday, September 26, 2023

How to calculate large factorial using BigInteger in Java? Example Tutorial

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 a really large integer value, something which is even bigger than the maximum value of long primitive like 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 the factorial of a larger number instead we need to use for loop for that.

Also worth noting is 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.

Also, basic knowledge of essential Java concepts and API is also very important and that's why I suggest all Java programmers join a comprehensive Java online course like The Complete Java Masterclass on Udemy to improve their Java knowledge and API skills.






Java Program to Calculate Factorial of Large Number

Here is our sample Java program to calculate factorial for large numbers, well, the 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 bounds 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 a long data type to store such huge integral values. You need to use the BigInteger class to store such big values.

BTW, If you are looking for some programming exercise to prepare coding interviews or to develop your programming logic then you should check problems from Cracking the Coding Interview: 189 Programming Questions and Solutions, one of the best books 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.

BigInteger Example in Java Calculating Factorial

That's all about how to calculate the factorial of a large number in Java. Clearly, after some point long is not enough to result of the 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 check out the following posts and some good books :
  • Top 15 Data Structure and Algorithm Interview Questions (see here)
  • 10 Free Data Structure and Algorithms courses (free courses)
  • How to print all permutations of a String in Java? (solution)
  • How to write FizzBuzz in Java 8? (answer)
  • Top 20 String coding interview questions (see here)
  • How to find the first non-repeated character from String? (solution)
  • 133 core Java interview questions of last 5 years (see here)
  • Top 30 Array Coding Interview Questions with Answers (see here)
  • How to reverse an array in place in Java? (answer)
  • Top 30 linked list coding interview questions (see here)
  • How to reverse Integer in Java? (solution)
  • Top 50 Java Programs from Coding Interviews (see here)
  • Top 5 books on Programming/Coding Interviews (list)
  • How to check if the given String is Palindrome in Java? (solution)
  • My Favorite Coding interview courses for Beginners (courses)
  • 100+ Data Structure and Algorithms Questions for Interviews (questions)
  • How to swap two integers without using a temporary variable in Java? (solution)

Thanks for reading this article so far. If you like this article then please share it with your friends and colleagues. If you have any questions or doubt then please let us know and I'll try to find an answer for you.

P. S. - If you are new to Java and looking for free online courses to learn Java from scratch then you can also check out this list of free Udemy courses to learn Java. It contains 5 free Java courses from Udemy and Coursera to teach you Java from scratch. 

 And now is your turn what is your favorite Java programming exercise? Palindrome, Prime number, Fibonacci, or Factorial? Let me know in comments. 

5 comments:

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

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

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

    ReplyDelete
  4. 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.

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

    ReplyDelete