Optimization of Factorial Function

This is a solution to the CodeHhef problem FCTRL2 where we are supposed to find the factorial of numbers up to 100. I have tried several techniques but I am always exceeding their time limit (1 second). Please help me optimize this code to make it execute faster.

    import java.math.BigInteger;
import java.io.*;
class Abc{
public static void main(String[] args) throws IOException
{
BigInteger fact=new BigInteger("1");
// BigInteger inc=new BigInteger("1");
int n=Integer.parseInt(str);

for(int i=0;i<n;i++)
BigInteger number=new BigInteger(st);

for(BigInteger bi = BigInteger.valueOf(1);bi.compareTo(number)>=0;bi = bi.add(BigInteger.ONE))
{
fact=fact.multiply(bi);
}
System.out.println(fact);
}
}
}

• What are n and st? you should only need one loop, not two. Jan 14 '16 at 18:29
• Why not calculate all the factorials up to 100 once, stored in an array and look the value up as required? Jan 14 '16 at 18:36
• bi.compareTo(number)>=0 looks like the wrong loop condition. Jan 14 '16 at 18:40

It is unclear what n and st are in your code and you are mixing things together which makes fixing your code harder.

I therefore suggest refactoring your code:

• extract the factorial calculation in its own method, without all the string conversion and input reading stuff:

private static BigInteger factorial(int n) {
BigInteger fact = new BigInteger("1");
for (int i = 1; i <= n; i++) {
fact = fact.multiply(BigInteger.valueOf(i));
}
return fact;
}


Once you have done that, you can start optimising the factorial method, for example by caching the results as you calculate them.

Try something like this. The call factorial(1000); (one thousand, not: one hundred!) needs far less than a second on my rather low level laptop:

package factorials;

import java.math.BigInteger;
import java.nio.*;

public class Factorials
{
public static BigInteger factorial(int i)
{
BigInteger result = BigInteger.ONE;
BigInteger factor = BigInteger.ONE;

while (i > 1)
{
result = result.multiply(factor);
i--;
}
return result;
}

public static void main(String[] args)
{
System.out.format("%s\n", factorial(1000));
}
}


• Mixing I/O code with the factorial calculation
• You used BigIntegers to do the loop logic
• You did not have an intermediate factor that you could increment on each loop

Actually, you had an intermediate factor, but you used it for the loop logic, so that was a little weird and probably a lot slower.

Ok, now I am getting nitpicky, but you used three different ways to initialize a BigInteger to one: BigInteger.ONE, BigInteger("1") and BigInteger.valueOf(1). The former is an already existing value that only has to be referenced. The others each require the construction of a new value, and the string one even the parsing of a string. If there is a constant like ONE, use that.

You can first take all the inputs, store it in an array and sort it in $nlogn$ time using a built-in algorithm or merge sort.

After this, you first calculate the factorial of $i^{th}$ element, store it in a variable and find the factorial of $(i+1)$ not using this variable.

long fact=factorial(array[0]);
int k;
print(fact);
k=array[0]+1;
for(int i=1;i<n;++i)
{
while(k<=array[i])
{
fact*=k;
k++;
}
print(fact);
}