## 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} $$

1 | def calculate_factorial_recursive(number): |

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.

### First Improvement :

### 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 $$

1 | def calculate_factorial_multi(number): |

The profiled result for this function :

1 | for n = 1000 -- Total time: 0.001115 s |

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%.

### Second Improvement :

### 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:

1 | def calculate_factorial_multi_half(number): |

The profiled result for this function :

1 | For n = 1000 -- Total time: 0.00115 s |

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:

1 | private static void calculateFactorial(int uptoValue) { |

### Further Improvement :

### 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

1 | def calculate_factorial_prime_decompose(number): |

1 | The profiled result for this function : |

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

Github Link