PyPE.pemath.factorial(...) performance

[Scott Armitage]

Currently (lp:pype 16) the implementation of PyPE.pemath.factorial(n) is equivalent in execution time to calling the Python 2.6 built-in function math.factorial. The standard Python implementation, however, employs no caching. Currently, the only form of caching performed by PyPE.pemath.factorial is a dictionary look-up of n (e.g. n!). If n! has been calculated before, simply return the value; otherwise, calculate it from scratch.

There are a couple of improvements for this. First, if n is larger than the largest previously calculated factorial, then we can simply calculate n*(n-1)*...*(n_max+1) and multiply it by the known value n_max!. This works well if the desired factorials are monotonically increasing, that is, if every call to PyPE.pemath.factorial is for a larger number than all previous calls. However, where this method does not help, is if n is less than the largest previously calculated factorial.

It may be possible to implement an efficient algorithm that looks up the largest previously calculated factorial that is LESS THAN n, and then we need only calculate down to this value.

Examples
---------------

We have the following factorials cached:

0!-------------1000!-----------------2000!

Ex 1: We wish to calculate 3000!. For the first case above, we need only calculate 3000*2999*...*2001, and then multiply it by the known value of 2000!. For the latter case, the same would apply.

Ex 2: We wish to calculate 1800!. For the first case above, we are not larger than 2000, and thus we must calculate 1800! from scratch. For the second case, we would need some way to find out that 1000! is the largest pre-calculated factorial below the one desired. Then we need simply calculate down to 1800*1799*...*1001, and then multiply it by the known value of 1000!.