Implement `math.factorial(n)` to calculate very large factorials with speed

[kmr-srbh]

Overview

• The current implementation of math.factorial() is naive.
• Returns 0 for large factorials due to integer overflow.

Solution

The industry standard for calculating factorial of a large number is complicated. It deals with Prime Number generation and Swing Numbers. These methods require BigInt for storing the large calculated value.

One fast method for going about calculating the calculation is to use an array to store the digits of the number as strings, in reverse, and do digit by digit multiplication. This method is used for implementing the algorithm.

I support the implementation of the Swing Number algorithms if one can understand and implement it correctly. The funny thing is that a Python implementation is available online.

Improvement

• Works for large factorials
• Works for very large factorials
• Accurate

Integration tests have not been added due to the prerequisite below.

Prerequisite

1. While the function is complete, it depends on #2554 for getting merged. Currently it just prints the output to stdout and returns 0.
2. As it currently stands, the implementation for handling values larger than 2^63 - 1 is handled by the BigInt module we have. It is broken and returns pointers to the number instead. A vector<char> is required for storing and working with very large values.

Note: The long assignment of digits is because LPython currently does not support list assignment like: my_list[0:4] = [1, 2, 3]. The assignments can be improved through the introduction of the above list assignment.

[kmr-srbh]

I think the errors are okay for now because the factorial function returns only 0. This will be addressed.

[kmr-srbh]

@certik On further thought, I realized that to handle values large as shown above, we need to introduce a new data type BigInt where we store the number as digits in base 2 ^ 32 in a vector. The vector<string> method is not that fast. What is your take on this? If not going through BigInt, what else can we do? Please guide me.

If yes, please guide me on how can one go about creating a new data type?

[kmr-srbh]

Closing this as not planned for now.