[BangPypers] Implementing a fast factorial function in python

[Abhishek Mishra]

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
>