Calculating the factorial of a number efficiently

Question

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(uptoValue)));
        }
        System.out.println(answer);
    }
} 

Which gave me a total sum of running time of 1.6362 sec against various inputs.

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

Answer 1

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.

Answer 2

All of the new BigInteger(String.valueOf(…)) calls should be replaced by BigInteger.valueOf(…). Also, new BigInteger("1") is just BigInteger.ONE.

Your second method is faster because it's halving the number of BigInteger multiplications by doing some of them using int multiplication. The int multiplication should be done using long to store the result, to prevent overflow.

Answer 3

One of many ways is dividing n by 2 repeatedly.

$$n! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot \ldots \cdot n$$

We define \$\mathrm{factodd}(n)\$ as the product of odd numbers 1∙3∙5∙…∙n:

$$\begin{align} n! &= \mathrm{factodd}(n) \cdot 2^{\frac{n}{2}}\left(1 \cdot 2 \cdot 3 \cdot 4 \cdot \ldots \cdot \frac{n}{2}\right) \\ &= \mathrm{factodd}(n) \cdot 2^{\frac{n}{2}}\left(\mathrm{factodd}\left(\frac{n}{2}\right) \cdot 2^{\frac{n}{4}} \cdot \left(1 \cdot 2 \cdot \ldots \cdot \frac{n}{4}\right)\right) \\ &\ \vdots \\ &= \mathrm{factodd}(n) \cdot 2^{\frac{n}{2}}\left(\mathrm{factodd}\left(\frac{n}{2}\right) \cdot 2^{\frac{n}{4}}\left(\mathrm{factodd}\left(\frac{n}{4}\right) \cdot 2^{\frac{n}{8}}\left(\mathrm{factodd}\left(\frac{n}{8}\right) \cdot \ldots \right)\right)\right) \\ &= 2^{\frac{n}{2}+\frac{n}{4}+...+\frac{n}{2^k}} \cdot \mathrm{factodd}(n) \cdot \mathrm{factodd}\left(\frac{n}{2}\right) \cdot \mathrm{factodd}\left(\frac{n}{2^2}\right) \cdot \mathrm{factodd}\left(\frac{n}{2^3}\right) \cdot \ldots \cdot \mathrm{factodd}\left(\frac{n}{2^k}\right) \end{align}$$

where \$k\$ is the nearest biggest exponent of 2 which satisfies \$\dfrac{n}{2^k}=1\$, means \$k=log_{2}{n}\$

Notice that you don't have to calculate factodd(k) each time — just multiply the square of the factorial of common first n/2 numbers of factodd(n) * factodd(n/2) by (n/2+1)∙(n/2+3)…n and so on.

The overall expression should look somewhat like:

$$2^{n(1-{\frac{1}{2}}^{log_{2}{n}})} \cdot 3^{log_{2}{\frac{n}{3}}+1} \cdot 5^{log_{2}{\frac{n}{5}}+1} \cdot 7^{log_{2}{\frac{n}{7}}+1} \ldots$$

---

A more naïve way (but not recommended) is to extract all \$2^k \cdot 5^{k'}\$ factors and multiply them separately.

Example:

1∙2∙3∙4∙5∙6∙…∙100,

M={2,5,2*2,2*5,5*5,2*2*2,2*2*5,2*5*5,2*2*5*5}

Multiplication of all these numbers isn't required, because we can instead calculate how many couples of (2,5) are there and then append as much zeroes to the remaining product.

---

Just by combining first and second methods together I came up with a conclusion:

$$\begin{align} n! &= 2^{n-1}*5^{log_{2}{\frac{n}{5}}+1} \cdot 3^{log_{2}{\frac{n}{3}}+1} \cdot 7^{log_{2}{\frac{n}{7}}+1} \ldots \ldots \\ &= 10^{log_{2}{\frac{n}{5}}+1} \cdot 2^{n-log_{2}{\frac{n}{5}}-2} \cdot 3^{log_{2}{\frac{n}{3}}+1} \cdot 7^{log_{2}{\frac{n}{7}}+1} \ldots \ldots \end{align}$$

This is equal to: \$ \cdot 2^{n-log_{2}{\frac{n}{5}}-2} \cdot 3^{log_{2}{\frac{n}{3}}+1} \cdot 7^{log_{2}{\frac{n}{7}}+1} \ldots \ldots x^{log_{2}{\frac{n}{x}}+1}\$ after \$ log_{2}{\frac{n}{5}}+1 \$ trailing zeroes with \$x\$ the last odd factor of \$n!\$

---

Hardcore way:

I named it so because of its deep arborescent structure, and it takes huge memory amount, but it gives out the least calculation of multiplying prime factors by their exponents.

First, we must build a very-ramified tree starting from the first prime number 2 until n.

• Arcs are \$prime^e\$ of \$x^e\$ step where \$x\$ is the actual prime, and \$e\$ is next stage. We build the tree of prime \$x=2\$ first, and we stop when \$e\$ exceeds \$n\$.

• Lines are:

  Red lines are of step=4 where prime number \$x=2\$ is always of exponent \$e= 1\$

  Generally we define all points where exponent of actual prime is constant: \$2^e(2k+1)\$ (e=2 green line), where \$k\$ is the actual step looked forward, and \$e\$ is constant exponent.

  After this we highlight next prime \$x=3\$, and we do same process of tree-expanding of \$3^e(3k+1)\$ (e=1 yellow line) and \$3^e(3k+2)\$ (e=1 blue line) after all arcs of \$3^k\$ are developed.

  • Once we come across an arc-node, we add the actual \$k\$ to the prime exponent at the level of the root of the tree. In general we have \$prime^{1+2+..+k}=prime^{\frac{k(k+1)}{2}}\$.
  • Once we come across a line we just add the actual constant to all exponents of tree-roots which are linked to the actual number pointed by same lines, as a whole we have \$prime^{e+e+e+e} = prime^{e(k+1)}\$ where \$e\$ is the line attributed exponent.

The overall expression would look like:

• Arcs: \$ 2^{\sum {log_2{n}}}*3^{\sum log_3{n}}*...*x^{\sum log_x{n}} \$ where \$x\$ is the last biggest prime factor of \$n\$

• Lines:

  • Red lines: \$2^{(n-2)/4}\$
  • Green lines \$2^{(n-4)/8}\$

  (x=2): \$2^{(n-2^e)/2^{e+1}}\$

In general: \$ x^{(n-x^e.l)/x^{e+1}} \$ while \$(n-lx^e)>0 \ and \ e>0 \ and \ l<x \$

So it is:

$$n! = \prod x^{\frac{(1+log_x{n})log_x{n}}{2}} * \prod \sum_{l=1} \sum_{e=1} x^{(n-x^e.l)/x^{e+1}}$$

With the biggest \$e\$ and \$l\$ which gives \$(n-lx^e)>0 \ \ and \ l<x \$ and all \$x\$ prime factors of n (correct me if I was wrong).

The memory issue can be reduced if we use prime generating polynomials but it seems you can't generate up to first 1681 primes using Euler polynomial. So it remains risky to engage in that with factorials bigger than 1681!

Answer 4

A non-mathematical way to speed up your code, at the cost of increasing its complexity and memory usage, is to precompute likely inputs.

If you are likely to get inputs that are, say 100 or smaller, just compute the result for 0 through 100 once and put the results in an array; then if you are asked for one of those, you already have the result without calculating it. (Remember, it's not going to change from run to run; you can compute them once, print out the results, and then use that to put literals into your source code.)

Or, suppose the maximum value you are likely to get as an input is 1000. Compute the factorials of 1, 2, 4, 8, 16, 32, ... 1024 and put those in an array. When you are asked for the factorial of 600, say, you already have the factorial of 512 computed, so you've cut down the number of multiplications by around 80% right there.

Or, you can do memoization. Suppose you are asked for the factorial of 600 first. Make a map from inputs to outputs and compute the factorial of every number from 1 through 600 and put it in the map. Then the second time you are called, if the caller wants a value less than 600, you've already got it in the map, and if they want a value greater than 600, you can at least start with 600, and put more things in your map as you go.