[BangPypers] Implementing a fast factorial function in python
Amit Saha
lists.amitsaha at gmail.com
Mon Sep 14 18:36:36 CEST 2009
Shashwat Anand wrote:
> How do we calculate last 5-digits of 10**12 ignoring trailing zeros. The
> code i wrote works good until 10**8 and after that take ages.
> The source of problem is Project Euler :
> http://projecteuler.net/index.php?section=problems&id=160
You might consider using the Stirling's Approximation
(http://en.wikipedia.org/wiki/Stirling%27s_approximation) to calculate
the factorial of a large N. You will still have to figure out a good way
to find the trailing zeros, ofcourse.
HTH
-Amit
>
> The code is pasted here : http://paste.pocoo.org/show/139745/
>
> 1 '''
>
>
> 2 For any N, let f(N) be the last five digits before the trailing zeroes
> in N!.
> 3 For example,
> 4
> 5 9! = 362880 so f(9)=36288
> 6 10! = 3628800 so f(10)=36288
> 7 20! = 2432902008176640000 so f(20)=17664
> 8
> 9 Find f(1,000,000,000,000)
> 10 '''
> 11 def f(n):
> 12 fac = 1
> 13 i = 1
> 14 #for i in range(1, n+1):
> 15 while i < n + 1:
> 16 fac = int(str(fac * i).strip('0')) % 100000
> 17 i += 1
> 18 return fac
> 19
> 20 print f(1000000000000)
>
> PS. hope posting algorithmic doubts will not be considered spamming :)
>
>
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> BangPypers mailing list
> BangPypers at python.org
> http://mail.python.org/mailman/listinfo/bangpypers
--
Journal: http://amitksaha.wordpress.com
µ-blog: http://twitter.com/amitsaha
IRC: cornucopic on #scheme, #lisp, #math, #linux
More information about the BangPypers
mailing list