Calculating the factorial of a number efficiently

I was trying to calculate the factorial of a large number in a short time:

class TestClass {
    public static void main(String args[] ) throws Exception {
        BufferedReader keyboard=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(keyboard.readLine());
        while(n!=0){
            int uptoValue=Integer.parseInt(keyboard.readLine());
            calculateFactorial(uptoValue);
            n--;
        }
    }
    private static void calculateFactorial(int uptoValue) {
        // TODO Auto-generated method stub
        BigInteger answer=new BigInteger("1");
        for(int i=1;i<=uptoValue;i++){
            answer=answer.multiply(new BigInteger(String.valueOf(i)));
        }
        System.out.println(answer);
    }
}

Which gave me total sum of running time of 1.7618 against various inputs.

Now I tried to solve it using pattern decomposition to avoid the number of loops, and wrote the following code:

```
class TestClass {
public static void main(String args[] ) throws Exception {
BufferedReader keyboard=new BufferedReader(new InputStreamReader(System.in));
int n=Integer.parseInt(keyboard.readLine());
while(n!=0){
int uptoValue=Integer.parseInt(keyboard.readLine());
calculateFactorial(uptoValue);
n--;
}
}
private static void calculateFactorial(int uptoValue) {
// TODO Auto-generated method stub
BigInteger answer=new BigInteger("1");
boolean oddUptoValue=false;
int tempUptoValue=0;
if(uptoValue%2!=0){
tempUptoValue=uptoValue-1;
oddUptoValue=true;
}else{
tempUptoValue=uptoValue;
}
for(int i=1;i<=tempUptoValue/2;i++){
int temp=(tempUptoValue-i+1)*i;
answer=answer.multiply(new BigInteger(String.valueOf(temp)));
}
if(oddUptoValue){
answer=answer.multiply(new BigInteger(String.valueOf(upto

How can I improve the runtime? What are more efficient algorithms to calculate the factorials of a large number?

If you really want to know it, then study BigIntegerMath.factorial from Guava. There are too many tricks there to be described here.

Review

// TODO Auto-generated method stub

Are you sure you need it?

boolean oddUptoValue=false;
    int tempUptoValue=0;
    if(uptoValue%2!=0){
        tempUptoValue=uptoValue-1;
        oddUptoValue=true;
    }else{
        tempUptoValue=uptoValue;
    }

Too complicated. What about

boolean oddUptoValue = uptoValue % 2 != 0;

and leaving oddUptoValue alone, as the division by two rounds down anyway.

int temp=(tempUptoValue-i+1)*i;

This can overflow, use

long product = (tempUptoValue - i + 1L) * i;

Note the name, the formatting (spacing), and the use of 1L which enforces a cast to long of both multiplicands.

answer=answer.multiply(new BigInteger(String.valueOf(temp)));

This should be

answer = answer.multiply(BigInteger.valueOf(product));

Optimizations

Despite avoiding the conversion via string being much faster, my above changes won't help with speed. The vast majority of the time for big inputs get spend in the BigInteger multiplication.

The simplest trick is getting rid of powers of two. Use Integer.numberofTrailingZeros for removing them from each multiplicand, compute the product and finally shift it left. This way the numbers you deal with get smaller and all operations get faster.

Regrouping the operands is the second trick. For four about equally big numbers, computing

(a * b) * (c * d)

instead of

((a * b) * c) *d

gives you a nice speedup. You can regroup your operands to make use of this.

StackExchange Code Review Q#90911, answer score: 13