[BangPypers] Implementing a fast factorial function in python
Shashwat Anand
anand.shashwat at gmail.com
Mon Sep 14 17:07:55 CEST 2009
@abhishek :
Can you show me the code ?
10**12 is way too much. My code gives output within a minute for 10**8 and
fails. Ofcourse I need to apply some algo here. What do you exactly mean by
taking out rightmost 7 digits ?
On Mon, Sep 14, 2009 at 8:14 PM, Abhishek Mishra <ideamonk at gmail.com> wrote:
> I remember doing something very inaccurate a long time ago for this -
> 1. find everything in a loop
> 2. everytime you encounter some zeros, strip them
> 3. everytime after stripping it exceeds say 7 digits, take out
> rightmost 7 digits for accuracy's sake
> 4. proceed till loop ends
> 5. print out the rightmost 5 digits of what remains
>
> Highly inaccurate but helped crossing icpc prelims in 1st year because
> there were humans who checked my solution with smaller inputs :)
>
> On Mon, Sep 14, 2009 at 6:36 PM, Shashwat Anand
> <anand.shashwat at gmail.com> 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
> >
> > 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
> >
> _______________________________________________
> 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/75d10cb7/attachment-0001.htm>
More information about the BangPypers
mailing list