Posted 16 August 2012 - 02:41 PM
Try playing around with Stirling's approximation. It won't give you an exact answer but you might be able to get the right answer by rounding up to the nearest 10th (depends how much precision you keep).
Maybe try a dynamic programming approach? What is the bounds given on n? [1, 100]? This might (probably) will use too much memory though. Make an array of size 100 and store the factorials computed.
Say you have this array (of size 5)
0! = 1
1! = 1
Are the computed base cases. Also keep the index of the last factorial that has been calculated. When the test script asks for fact(5) you already have fact(0), fact(1) then you can compute fact(2), fact(3), fact(4) and fact(5) with just 4 multiplications instead of 5 for fact(5). Then say it asks for fact(7) you only have to do two multiplications instead of 7. Might work.
Say you have these numbers to find the factorials of:
5 (3 multiplications needed)
7 (2 multiplications needed)
9 (2 multiplications needed)
3 (0 multiplications needed - just return the answer)
81 (71 multiplications needed)
76 (0 multiplications needed - would have been precomputed with fact(81))
30 (0 multiplications needed - would have been precomputed with fact(81))
85 (4 multiplications needed)
Memory space might be an issue though.
Might be even faster is to assume the worstcase - precompute and store fact(100) and all the lower answers will be computed and if asked for just have to return them. No calculations necesary.
I coded this on my computer and was able to compute fact(100) in 00:00:00.020. Then it only took 00:00:00.003 to calculate factorial(99).