Blog

# Efficient Factorial Algorithm

## Factorial -

In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers
less than or equal to n. For example,

$$5! = 5 \ast 4 \ast 3 \ast 2 \ast 1 = 120$$

### Recursive Approach:

Based on the recurrence relation

$$n! = \begin{cases} 1 & \text{if n = 0},\ (n-1)! \ast n & \text{if n > 0} \end{cases}$$

The Recursive approach is not the best approach. It will give RuntimeError: maximum recursion depth exceeded.
For large number as python doesn’t have optimized tail recursion, but it have been written for pedagogical purposes, to illustrate the effect of several fundamental algorithmic optimizations in the n factorial of a very large number.

### Successive Multiplicative Approach.

This function uses the approach successive multiplication like
$$8! = 8 \ast 7 \ast 6 \ast 5 \ast 4 \ast 3 \ast 2 \ast 1$$

The profiled result for this function :

Now If we see the result from line_profiler we will see that most %time was spent in multiplication step of the above code i.e result *= x which is almost 98%.

### Reduce the number of successive multiplication

As the multiplication is very costly especially for a large number , we can use the pattern and reduces the number of multiplication by half. Lets group the above 8! example $8! = 8 \ast 7 \ast 6 \ast 5 \ast 4 \ast 3 \ast 2 \ast 1$- together: $8! = (8 \ast 1) \ast (7 \ast 2) \ast (6 \ast 3) \ast (5 \ast 4)$ which can be written as $$8! = 8 \ast (8 + 6 = 14) \ast (14 + 4 = 18) \ast (18 + 2).$$
so first factor is the number we are taking. second factor is the first factor plus first factor minus two from the factor and then in next we multiply the result with added result. Odd number also follows the same pattern till even just handle the case of one odd.
Code to do the same:

The profiled result for this function :

It is not optimised very much, but are at least not obscenely slow. It’s shows some improvement in the mid range but didn’t improved much with scaling. In this function too most of the %time is spent on multiplication:
Java Code for the same:

### Using prime decomposition

to reduce the total number of multiplication Since there are $$\frac {number} {\ln number}$$ prime number smaller than number so we can further reduce the total number of multiplication

You can see the detailed profiled result of all the discussed algorithms prepared here, in case if you want to see.