[Tutor] Need help speeding up algorithm.

[Ian Witham]

On 9/26/07, Terry Carroll <carroll at tjc.com> wrote:
>
> On Tue, 25 Sep 2007, Ian Witham wrote:
>
> def numfaczeroes(n):
>     """
>     return the count of trailing zeroes from n!
>     e.g., 10! = 3628800; count of trailing zeros = 2
>     """
>     exponent = 1
>     fivecount = 0
>     while (n//(5**exponent)) > 0:
>         fivecount += n//(5**exponent)
>         exponent += 1
>     return fivecount
>

I've come up with a couple of improvements to your function

First I moved the (n//(5**exponent)) out of the while definition as it was
being evaluated twice for each iteration:

def numfaczeroes(n):
    """
    return the count of trailing zeroes from n!
    e.g., 10! = 3628800; count of trailing zeros = 2
    """
    exponent = 1
    fivecount = 0
    count = (n//(5**exponent))

    while count > 0:
        fivecount += count
        exponent += 1
        count = (n//(5**exponent))
    return fivecount

This shaved about 10% off the run time.

Then I got rid of the (n//(5**exponent)) altogether:

def numfaczeroes(n):
    """
    return the count of trailing zeroes from n!
    e.g., 10! = 3628800; count of trailing zeros = 2
    """

    fivecount = 0
    count = n//5

    while count > 0:
        fivecount += count
        count /= 5
    return fivecount

This shaved a further 40% off the run time!

In practice, the Sphere Judge still takes 3 seconds to execute. So perhaps
there is another bottleneck in my program -- maybe the input/output?

Interestingly, print runs faster than sys.stout.write, but input() is far
slower than sys.stdin.readline

import sys

for test in range(int(sys.stdin.readline())):

    n = int(sys.stdin.readline())

    fivecount = 0
    count = n/5

    while count > 0:
        fivecount += count
        count /= 5

    print fivecount
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.python.org/pipermail/tutor/attachments/20070926/de1c3016/attachment.htm