Path: csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail
From: srinivas devaki <mr.eightnoteight@gmail.com>
Newsgroups: comp.lang.python
Subject: Re: Trailing zeros of 100!
Date: Sun, 3 Jan 2016 07:16:43 +0530
Lines: 103
Message-ID: <mailman.189.1451785646.11925.python-list@python.org>
References: <52ccbc4b-616b-4186-8802-97aaa5b0d9af@googlegroups.com> <CAHzaPEOzP+DZDHOV7s1tDA0AUNhFdBUJKZWCJ5W9F8ec6aH-JA@mail.gmail.com> <mailman.162.1451745109.11925.python-list@python.org> <n68s1t$ke9$1@news.albasani.net> <mailman.172.1451753180.11925.python-list@python.org> <n68vgc$qi6$1@news.albasani.net> <mailman.184.1451771860.11925.python-list@python.org> <n69oev$uv8$1@news.albasani.net> <85twmvqzrv.fsf@benfinney.id.au>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
In-Reply-To: <85twmvqzrv.fsf@benfinney.id.au>
Precedence: list
Xref: csiph.com comp.lang.python:101183

let's put an end to this.

from math import log
# simple one to understand. complexity: O(n*log(n))
def countzeros_va(n):
    count =3D 0
    for x in xrange(1, n + 1):
        while x % 5 =3D=3D 0:
            count +=3D 1
            x //=3D 5
    return count

# better approach. complexity: O(log(n))
def countzeros_vb(n):
    count, c5 =3D 0, 5
    while c5 <=3D n:
        count +=3D (n // c5)
        c5 *=3D 5
    return count

# this is same as before, its just that while loops irk me
def countzeros_vc(n):
    return sum(n // (5**x) for x in range(1, int(log(n, 5) + 3)))
    # adding +3 to be sure. never trust approximations.

def run_sample_tests():
    precal =3D {3: 0, 60: 14, 100: 24, 1024: 253, 23456: 5861, 8735373: 218=
3837}
    for x in precal:
        assert precal[x] =3D=3D countzeros_va(x) =3D=3D countzeros_vb(x) =
=3D=3D
countzeros_vc(x)

if __name__ =3D=3D '__main__':
    run_sample_tests()

Although the code is deterministic, it can be further tested from
http://www.wolframalpha.com/widgets/view.jsp?id=3D54da27e6e09dc404890a57873=
5b9f7d8
http://www.spoj.com/problems/FCTRL/

On Jan 2, 2016 5:22 PM, <katye2007@gmail.com> wrote:
>
> Hi, newbie here!
> I'm trying to write a python program to find how many trailing zeros are =
in 100! (factorial of 100).
> I used factorial from the math module, but my efforts to continue failed.=
 Please help.
>
> Thank you,
> Yehuda
> --
> https://mail.python.org/mailman/listinfo/python-list

On Sun, Jan 3, 2016 at 5:50 AM, Ben Finney <ben+python@benfinney.id.au> wro=
te:
> Robin Koch <robin.koch@t-online.de> writes:
>
>> Am 02.01.2016 um 22:57 schrieb Chris Angelico:
>> >>> But did you actually test it?
>> >>
>> >> Yes, should work for n >=3D 1.
>
> By =E2=80=9Ctest it=E2=80=9D, Chris of course means test it *by implement=
ing it in a
> program and running that program in Python*.
>
>> >> Why do you ask?
>> >
>> > Your "should work" does not sound good as a response to "actually
>> > test". Normally I would expect the response to be "Yes, and it
>> > worked for me" (maybe with a log of an interactive session).
>>
>> Well, honestly, I trusted my math and didn't thought much about the
>> technical limitations.
>
> That's why it's good to actually test the hypothesis in a real computer
> program, run on the actual computer system you're going to use.
>
> Computers are physical systems, with technical compromises to the
> physical constraints under which they were built.
>
> They are not perfect implementations of our ideal mathematics, and
> testing the mathematics is no guarantee the mathematical assumptions
> will survive your program unscathed.
>
> So, a request =E2=80=9CDid you actually test it?=E2=80=9D is both a polit=
e reminder to
> do that, and an attempt to get you to do so if you didn't.
>
> If you didn't, then answering =E2=80=9Cyes=E2=80=9D is wasting everyone's=
 time.
>
> --
>  \       =E2=80=9CAs the most participatory form of mass speech yet devel=
oped, |
>   `\    the Internet deserves the highest protection from governmental |
> _o__)                   intrusion.=E2=80=9D =E2=80=94U.S. District Court =
Judge Dalzell |
> Ben Finney
>
> --
> https://mail.python.org/mailman/listinfo/python-list