[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