If you are calling factorial() many times, it is worth to cache the computed factorials.
Python, 29 lines
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
_FAC_TABLE = [1, 1] def factorial(n): if n < len(_FAC_TABLE): return _FAC_TABLE[n] last = len(_FAC_TABLE) - 1 total = _FAC_TABLE[last] for i in range(last + 1, n + 1): total *= i _FAC_TABLE.append(total) return total def main(): from timeit import Timer print("factorial: %.5f s" % Timer("factorial(500)", "from __main__ import factorial") .timeit(1000)) import math if hasattr(math, "factorial"): print("math.factorial: %.5f s" % Timer("factorial(500)", "from math import factorial") .timeit(1000)) if __name__ == "__main__": main()
My timeit results:
factorial: 0.00206 s math.factorial: 0.35708 s
When computing factorial(n), any factorial(i) for i < n will be also precomputed. And factorial(n) will be reused when computing factorial(n + 1) and higher.
All you're testing is how fast python can do the first calculation and then return an element in a list 999 times.
By that same logic instead of the complicated process you're using you may as well combine both ideas to make the far simpler:
You are right that the test does not measure all usages. Your mfactorial() has a disadvantage. It does not store the computed factorial(1) .. factorial(n-1).
For what it's worth, Python 3.2 will include a much faster factorial function than earlier versions of Python (see Issue8692).
To compute factorials faster for large arguments, use Stirling's Approximation (http://en.wikipedia.org/wiki/Stirling%27s_approximation):
As N grows, the negative powers of N improve the approximation.
This approximation is so good that:
When a term hits float's limit of precision, you can omit it from the approximation.
This program shows the accuracy of Stirling's Approximation:
David Lambert this method seems pretty accurate ,...but when i give value to N greater than 170 i get an overflowError
Can you suggest a way to get rid of this error :) ?
Thanks in advance :-)
i understand it's a really big number for the Computer... to represent it ... so i assume we can keep it in it's "log" representation.... for "mathematistic" manipulations and "stuff" ...