[BangPypers] Implementing a fast factorial function in python
Shashwat Anand
anand.shashwat at gmail.com
Mon Sep 14 15:43:04 CEST 2009
The thought which comes to my mind is Modular exponentiation :
for a ** b % r ( if a ** b very large )
I had coded it in C++ but in python the pow() have inbuilt modular-function
made.
so pow(a ,b, r) does the trick
Here for factorial :
F(n) = n * n-1 * n-2 ...* 2 * 1
Just like in earlier case where we needed to do was,
a * a * a ..(b times) % r, modulation at each step help reduce computation
since what we need is F(n) % 10**5
The key point i think is we do not need factorial but modulus 10**5 without
trailing zeros. Didn't helped though :( may be a better implementation could
help
On Mon, Sep 14, 2009 at 6:51 PM, Navin Kabra <navin.kabra at gmail.com> wrote:
>
> print f(1000000000000)
>>
>>
> This is a HUGE number. I don't think you are expected to get the answer by
> direct calculation. I would guess that you are expected to use mathematical
> reasoning to figure out the answer (and not computation)
>
>
> _______________________________________________
> BangPypers mailing list
> BangPypers at python.org
> http://mail.python.org/mailman/listinfo/bangpypers
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/bangpypers/attachments/20090914/c8c30786/attachment.htm>
More information about the BangPypers
mailing list