[Tutor] Need help speeding up algorithm.

[Terry Carroll]

On Tue, 25 Sep 2007, Ian Witham wrote:

> As I was using a list comprehension I wasn't sure how to make the
> calculations stop when the result of integer division == 0.

I don't see how to do that, either.  Someone on this list (sorry, I forget 
who) once suggested that the list comprehension should support a "while" 
predicate, similar to the "if" filter.  Such a predicate would not just 
filter the generated list, but actually stop its computation.

I think that would be a great idea, and this is a good use case why.  
Absent that capability, your only alternatives that I see are either 1) 
use the if-filter to filter out the list entries beyond those needed; or 
2) force the programmer to work backwards to figure out when that 
while-condition would be hit, and bake that into something like a range 
(as you did).

The downside of #1 is the computational expense: you generate a lot of
potential list enties, just to throw them away.  The downside of #2 is
that it's programmer-intensive, wasting programmer time, and prone ro
errors, as you discovered.

Now that you've solved your code, here's the function I came up with.  As 
I said, it resists implimentation as a list comprehension:

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

But what I like about is is that the only math is integer division and 
addition (and all the addition is simple incrementation).  No use of 
logarithms, not even any multiplication (which is just perverse, when you 
think about the fact that it's analyzing factorials, which are pure 
multiplication).