[BangPypers] Implementing a fast factorial function in python

[Shashwat Anand]

@anand:

There is a way to calculate number of leading zeros in n!
Here i had implemented it :

>>> x = 100 # number whose factorial is to be taken out
>>> s = 0 #initial count of zeros
>>> n = 1
>>> while x / 5**n:
...     s += x / 5**n
...     n +=1
...
>>> s
24
>>> import math
>>> len(str(math.factorial(100))) - len(str(math.factorial(100)).strip('0'))
24
>>>


On Mon, Sep 14, 2009 at 7:13 PM, Shashwat Anand <anand.shashwat at gmail.com>wrote:

> 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/e477e806/attachment.htm>