PyPE.pemath.factorial(...) performance
Affects | Status | Importance | Assigned to | Milestone | |
---|---|---|---|---|---|
PyPE |
Confirmed
|
Wishlist
|
Scott Armitage |
Bug Description
Currently (lp:pype 16) the implementation of PyPE.pemath.
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)
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!-----
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!.
Related branches
Changed in pype: | |
status: | New → Confirmed |
importance: | Undecided → Wishlist |
assignee: | nobody → Scott Armitage (scott-armitage) |