Factorial of a large number

Factorial of a non-negative number n, denoted by n!, is the product of all positive integers less than or equal to n. For Example:

5! = 5 * 4 * 3 * 2 * 1;
6! = 6 * 5 * 4 * 3 * 2 * 1;

Iterative solution

public class Factorial {
 static int fact(int n) throws Exception {
  if (n < 0)
   throw new Exception(
     "Factorial of negative number is always infinity");

  if (n == 0 || n == 1)
   return 1;
  int fact = 1;
  for (int i = 1; i <= n; i++) {
   fact = fact * i;
  }
  return fact;
 }

 public static void main(String[] args) throws Exception {
  for (int i = 0; i <= 13; i++) {
   System.out.println("Factorial of " + i + " is : " + fact(i));
  }
 }
}

Recursive Solution

public class Factorial {
 static int fact(int n) throws Exception {
  if (n < 0)
   throw new Exception(
     "Factorial of negative number is always infinity");

  if (n == 0 || n == 1)
   return 1;
  return n * fact(n - 1);
 }

 public static void main(String[] args) throws Exception {
  for (int i = 0; i <= 13; i++) {
   System.out.println("Factorial of " + i + " is : " + fact(i));
  }
 }
}

Output of both program is same

Factorial of 0 is : 1
Factorial of 1 is : 1
Factorial of 2 is : 2
Factorial of 3 is : 6
Factorial of 4 is : 24
Factorial of 5 is : 120
Factorial of 6 is : 720
Factorial of 7 is : 5040
Factorial of 8 is : 40320
Factorial of 9 is : 362880
Factorial of 10 is : 3628800
Factorial of 11 is : 39916800
Factorial of 12 is : 479001600
Factorial of 13 is : 1932053504

if you observe carefully output of the above program, Factorial of numbers greater than or equal to 13 can not be found using above program due to overflow. These factorial are too large to fit into the int variable. Even if we use long datatype, factorials greater than or equal to 21 will generate an overflow.

Factorial of arbitrary large numbers

Let's see two approaches to calculate factorial of large numbers.

1. Using BigInteger class.
2. Normal Mathematics multiplication concept.

Using BigInteger class:

BigInteger is apart of java.math package. BigInteger class is used to represent arbitrarily large numbers. Overflow doesn't occur as case with int and long. A BigInteger object is created by passing a String which contains an integer value.

import java.math.BigInteger;

public class Factorial {

 public static BigInteger fact(int n) throws Exception {
  BigInteger fact = new BigInteger("1");
  if (n < 0)
   throw new Exception(
     "Factorial of negative number is always infinity");
  if (n == 0 || n == 1)
   return fact;
  for (int i = 1; i <= n; i++) {
   fact = fact.multiply(BigInteger.valueOf(i));
  }
  return fact;
 }

 public static void main(String[] args) throws Exception {
  BigInteger factValue;
  for (int i = 0; i <= 100; i += 20) {
   factValue = fact(i);
   System.out.println("Factorial of " + i + " is : " + factValue);
   System.out.println("Length of factorialed value : "
     + String.valueOf(factValue).length());
   System.out.println("-----------------------------------------------");
  }
 }
}

BigInteger fact = new BigInteger("1");

We have created a BigInteger object named 'fact' which will hold the factorial of the number and initialized it with 1.

Multiplication of two BigIntegers is performed using the multiply function which takes a BigInteger as an argument. BigInteger is an immutable class so object on which multiply method invoked does not change integer value it is holding. The multiplication is performed and value returned by function is assigned to variable fact.

Output of above and below program:

Factorial of 0 is : 1
Length of factorial value : 1
-----------------------------------------------
Factorial of 20 is : 2432902008176640000
Length of factorial value : 19
-----------------------------------------------
Factorial of 40 is : 815915283247897734345611269596115894272000000000
Length of factorial value : 48
-----------------------------------------------
Factorial of 60 is : 8320987112741390144276341183223364380754172606361245952449277696409600000000000000
Length of factorial value : 82
-----------------------------------------------
Factorial of 80 is : 71569457046263802294811533723186532165584657342365752577109445058227039255480148842668944867280814080000000000000000000
Length of factorial value : 119
-----------------------------------------------
Factorial of 100 is : 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
Length of factorial value : 158
-----------------------------------------------

Using Normal Mathematics multiplication concept.:

We calculate factorial of a number using simple multiplication of two numbers.

public class Factorial {
 static String fact(int n) throws Exception {
  // if number is negative throw exception
  if (n < 0)
   throw new Exception(
     "Factorial of negative number is always infinity");

  // factorial of 0 and 1 is 1
  if (n == 0 || n == 1)
   return String.valueOf(1);
  /*
   * In the loop, we are calculating the factorial of number using simple
   * math multiplication logic, 35 x 34=1190;
   * in above multiplication, lets assume fact is 35 and i is 34, first ,
   * we take 1st position digit, then 10th position digit, then 100th position digit and so on..
   * first position digit in fact is 5, 5 * 34= 170, carry is 17 and
   * 0 will push into buffer, now string buffer contain "0"
   * 10th position digit in fact is 3, so 3 * 34 + 17 = 119, carry is 11 and 9 will
   * push into buffer, now buffer contain "90".
   * fact string consume here ,
   * so loop will end now carry is not zero , so w'll push carry into
   * buffer, now buffer contain "1190" So buffer contain multiplication of
   * one string and numerical value.
   */
  String fact = "1";
  StringBuffer sb = new StringBuffer();
  for (int i = 1; i <= n; i++) {
   int carry = 0;
   // reset string buffer
   sb.setLength(0);
   for (int j = fact.length() - 1; j >= 0; j--) {
    int digit = Integer.parseInt(String.valueOf(fact.charAt(j)))
      * i + carry;
    carry = digit / 10;
    int rem = digit % 10;
    // inserting unit digit of every multiplication in string buffer
    // at 0th position
    sb.insert(0, rem);
   }
   // Here we could get carry when multiplied integer number with fact
   // value, and pushing carry at 0th position in buffer
   if (carry != 0)
    sb.insert(0, carry);
   // finally result of multiplication is stored in fact variable
   fact = sb.toString();
  }
  return fact;
 }

 public static void main(String[] args) throws Exception {
  String factValue;
  for (int i = 0; i <= 100; i = i + 20) {
   factValue = fact(i);
   System.out.println("Factorial of " + i + " is : " + factValue);
   System.out.println("Length of factorialed value : "
     + factValue.length());
   System.out
     .println("-----------------------------------------------");
  }
 }
}

You can check factorial of number in C/C++ using array data structure. click here