Find factorial of large numbers in Java

Question

I tried to find the factorial of a large number e.g. 8785856 in a typical way using for-loop and double data type.

But it is displaying infinity as the result, may be because it is exceeding its limit.

So please guide me the way to find the factorial of a very large number.

My code:

class abc
{
    public static void main (String[]args)
    {
        double fact=1;
        for(int i=1;i<=8785856;i++)
        {
            fact=fact*i;
        }

        System.out.println(fact);
    }
}

Output:-

Infinity

I am new to Java but have learned some concepts of IO-handling and all.

Predikant

Why don't you use higher data type like BigInteger and also is this homework? If yes then tag as such. – Ouse

you loop variable i is int and you are trying to store a huge number in it, try making it a double too – Roots

According to my calculations, it will take around 25 megabytes of memory in order to represent this number. and even then, that would be without the overheard of the BigInteger class. – Cerumen

yeah i have used biginteger as well but the compiler fails to display the answer for such a number so is there any other way out??? – Predikant

What do you mean, "fails to display the answer"? Can you post the code that "failed to display the answer"? – Limann

no i meant that for such a no. i waited for atleast an hr or so...but nothing happened.....it is displaying the answer for 10000 quite fast but not for above this value......and also the answer it was showing for 11000 doesn.t match this value...wolframalpha.com/input/?i=11000! – Predikant

Answer 1

public static void main(String[] args) {
    BigInteger fact = BigInteger.valueOf(1);
    for (int i = 1; i <= 8785856; i++)
        fact = fact.multiply(BigInteger.valueOf(i));
    System.out.println(fact);
}

Ferroconcrete

actually i have tried this one out but i am waiting for the compiler for a long time to execute this...... – Predikant

yeah you have to. and it will take lots of jvm memory also but we have no alternate as the factorial number is too big !! – Ferroconcrete

but i waited for atleast 30-35 mins... but nothing happened.... should i wait for for time the next time i run it??? – Predikant

you can increase your jvm memory – Ferroconcrete

Answer 2

You might want to reconsider calculating this huge value. Wolfram Alpha's Approximation suggests it will most certainly not fit in your main memory to be displayed.

Smashandgrab

Unless I did the calculation wrong, it would fit into memory: log2(10^10^8) = 3.32 * 10^8 = 300M bits = 38MByte – Obey

I have to say, I was too lazy to calculate the memory usage myself. Out of curiosity, does any one know what would happen if you tried to print a 38MB chunk of memory? – Smashandgrab

Answer 3

This code should work fine :-

public class BigMath {
    public static String factorial(int n) {
        return factorial(n, 300);
    }

    private static String factorial(int n, int maxSize) {
        int res[] = new int[maxSize];
        res[0] = 1; // Initialize result
        int res_size = 1;

        // Apply simple factorial formula n! = 1 * 2 * 3 * 4... * n
        for (int x = 2; x <= n; x++) {
            res_size = multiply(x, res, res_size);
        }

        StringBuffer buff = new StringBuffer();
        for (int i = res_size - 1; i >= 0; i--) {
            buff.append(res[i]);
        }

        return buff.toString();
    }

    /**
     * This function multiplies x with the number represented by res[]. res_size
     * is size of res[] or number of digits in the number represented by res[].
     * This function uses simple school mathematics for multiplication.
     * 
     * This function may value of res_size and returns the new value of res_size.
     */
    private static int multiply(int x, int res[], int res_size) {
        int carry = 0; // Initialize carry.

        // One by one multiply n with individual digits of res[].
        for (int i = 0; i < res_size; i++) {
            int prod = res[i] * x + carry;
            res[i] = prod % 10; // Store last digit of 'prod' in res[]
            carry = prod / 10;  // Put rest in carry
        }

        // Put carry in res and increase result size.
        while (carry != 0) {
            res[res_size] = carry % 10;
            carry = carry / 10;
            res_size++;
        }

        return res_size;
    }

    /** Driver method. */
    public static void main(String[] args) {
        int n = 100;

        System.out.printf("Factorial %d = %s%n", n, factorial(n));
    }
}

Tynes

This actually is a better program, efficient, no use of BigInteger. – Caduceus

Taken from GeeksForGeeks! – Shahjahanpur

@YudhishthirSingh If you find the source link, please raise a custom flag for plagiarism. (If it's an exact copy.) – Hyetal

Answer 4

Hint: Use the BigInteger class, and be prepared to give the JVM a lot of memory. The value of 8785856! is a really big number.

Arched

yes i have used biginteger as well but the compiler fails to display the answer for such a number so is there any other way out??? – Predikant

Try increasing the heap size. – Arched

Answer 5

Use the class BigInteger. ( I am not sure if that will even work for such huge integers )

Smythe

yeah i have used biginteger as well but the compiler fails to display the answer for such a number so is there any other way out??? – Predikant

@HimanshuAggarwal You can try a nasty thing like writing your own multiply routine for integers. For example, you can have two big integers to represent one HUGE integer. Well, it will be complicated and cumbersome. e.g. if my integers are of size 4 bits, to represent a number like 18, I can use 2 integers : 1 and 8 with appropriate weightages. (1 with weightage 10^1 and 8 with 10^1). So if you can write a code to represent big integers in chunks of small ones with attached weightages, and write your own multiply routine, this can be done. – Smythe

yep...so can u explain me this in a bit more detail. – Predikant

That was 10^0 for 8, in the previous comment. For multiplication, you have to take care of all the weightages and so on. It will be slow. Very slow. And the concept is loosely based on WallaceTree. – Smythe

okay..... but this is definitely going to be cumbersome..... by the way thanx for this explanation... i'll try to implement this method as well...:-) – Predikant

Answer 6

Infinity is a special reserved value in the Double class used when you have exceed the maximum number the a double can hold.

If you want your code to work, use the BigDecimal class, but given the input number, don't expect your program to finish execution any time soon.

Stearns

yes i have used biginteger as well but the compiler fails to display the answer for such a number so is there any other way out??? – Predikant

Answer 7

The above solutions for your problem (8785856!) using BigInteger would take literally hours of CPU time if not days. Do you need the exact result or would an approximation suffice?

There is a mathematical approach called "Sterling's Approximation " which can be computed simply and fast, and the following is Gosper's improvement:

Antlia

Answer 8

 import java.util.*;
 import java.math.*;

class main
{
public static void main(String args[])
{
    Scanner sc= new Scanner(System.in);

        int i;
        int n=sc.nextInt();


      BigInteger fact = BigInteger.valueOf(1);

        for ( i = 1; i <= n; i++)
        {
            fact = fact.multiply(BigInteger.valueOf(i));
        }
        System.out.println(fact);

}
}

Vowelize

I think the answer would be better without the scanner class. – Libretto

Answer 9

Try this:

import java.math.BigInteger;

public class LargeFactorial
{
    public static void main(String[] args)
    {
        int n = 50; 
    }
    public static BigInteger factorial(int n)
    {
       BigInteger result = BigInteger.ONE;
       for (int i = 1; i <= n; i++)
           result = result.multiply(new BigInteger(i + ""));
       return result;
    }
}

Arezzo

Sorry sir if my answer is wrong. I tried to answer so that he/she can find factorial of any number. All he/she has to do is change the value of n. – Arezzo

Answer 10

    Scanner r = new Scanner(System.in);
    System.out.print("Input Number : ");
    int num = r.nextInt();
    int ans = 1;
    if (num <= 0) {
        ans = 0;
    }
    while (num > 0) {
        System.out.println(num + " x ");
        ans *= num--;
    }
    System.out.println("\b\b=" + ans);

Heterothallic

edit your answer and add short explanation to your code – Indecency

Answer 11

    public static void main (String[] args) throws java.lang.Exception
    {
        BigInteger fact= BigInteger.ONE;
        int factorialNo = 8785856 ;

        for (int i = 2; i <= factorialNo; i++) {
              fact = fact.multiply(new BigInteger(String.valueOf(i)));
        }

        System.out.println("Factorial of the given number is = " + fact);
     }

Boson

Answer 12

import java.util.Scanner;


public class factorial {
    public static void main(String[] args) {
        System.out.println("Enter the number : ");
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        factorial f=new factorial();
        int result=f.fact(n);
        System.out.println("factorial of "+n+" is "+result);
    }
    int fact(int a)
    {
        if(a==1)
            return 1;
        else
            return a*fact(a-1);
    }

}

Consequent