Re: [Tutor] Need help speeding up algorithm.

[Ian Witham]

On 9/25/07, Terry Carroll <[EMAIL PROTECTED]> wrote:
>
> On Tue, 25 Sep 2007, Ian Witham wrote:
>
> > I am attempting to do this  project
> for
> > the Sphere Online Judge.
>
> (Summary of the problem: for a given integer N, determine the number of
> trailing zeroes in N!  For example, for N=10, N! = 3628800, so the number
> of trailing zeroes is 2.)
>
> > for d in testnums:
> > maxer = int(d ** .2) + 1
> > g = sum(d / (5 ** x) for x in xrange(1, maxer))
> > sys.stdout.write('%d\n' % g)
> >
> > 
> >
> > Any ideas on how to speed this up?
>
> I think you're on the right track, but it can actually be much less
> computationally intensive.
>
> The track I think you're on is that each trailing zero means that the
> factorial, if factored out, had both a 2 and 5 among its factors (because
> 2x5 is 10, and the only way of getting 10).  Furthermore, because there
> are so many 2s, it's really about counting the number of times 5 is
> multiplied in.
>
> For example, in 10!, you have two occurances of 5: at 5 itself, and at 10
> (2x5).  For 30!, you'd have fives at 5, 10, 15, 20, 25, and 30, which at
> first glance is 6; but since the 25 is actually 5x5, it counts for two,
> for a total of 7.  And, sure enough 20! is
> 26525285981219105863630848000, with 7 trailing zeoes.
>
> So, an approach might be:
>
> 1. Integer-divide N by 5.  That gives the number of times it's divisible
> by 5.
> 2. Integer-divide N by 5*5, i.e., 25; That gives the number of times it's
> also divisible by 25.
> 3. Integer-divide N by 5*5*5, i.e, 125.  That gives the number of times
> it's also divided by 125
> 4. through whatever: keep doing this.  You can stop when the result of the
> integer division is zero.


The problem with my program was the "through whatever".
As I was using a list comprehension I wasn't sure how to make the
calculations stop when the result of integer division == 0.
My method was to work out the maximum exponent of 5 that I would fit within
the test number. (This is the value I called "maxer")

However... my math was off.
int(d ** (1 / 5.0) != int(math.log(d, 5))

Once I fixed this, the program ran fast enough to be accepted.

Thanks for the advice,

Ian.
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] Need help speeding up algorithm.

[Terry Carroll]

On Tue, 25 Sep 2007, Ian Witham wrote:

> I am attempting to do this  project for
> the Sphere Online Judge.

(Summary of the problem: for a given integer N, determine the number of 
trailing zeroes in N!  For example, for N=10, N! = 3628800, so the number 
of trailing zeroes is 2.)

> for d in testnums:
> maxer = int(d ** .2) + 1
> g = sum(d / (5 ** x) for x in xrange(1, maxer))
> sys.stdout.write('%d\n' % g)
> 
> 
> 
> Any ideas on how to speed this up?

I think you're on the right track, but it can actually be much less 
computationally intensive.

The track I think you're on is that each trailing zero means that the 
factorial, if factored out, had both a 2 and 5 among its factors (because 
2x5 is 10, and the only way of getting 10).  Furthermore, because there 
are so many 2s, it's really about counting the number of times 5 is 
multiplied in.

For example, in 10!, you have two occurances of 5: at 5 itself, and at 10 
(2x5).  For 30!, you'd have fives at 5, 10, 15, 20, 25, and 30, which at 
first glance is 6; but since the 25 is actually 5x5, it counts for two, 
for a total of 7.  And, sure enough 20! is 
26525285981219105863630848000, with 7 trailing zeoes.

So, an approach might be:

1. Integer-divide N by 5.  That gives the number of times it's divisible 
by 5.
2. Integer-divide N by 5*5, i.e., 25; That gives the number of times it's 
also divisible by 25.
3. Integer-divide N by 5*5*5, i.e, 125.  That gives the number of times 
it's also divided by 125
4. through whatever: keep doing this.  You can stop when the result of the 
integer division is zero.

If you add up all the counts you got in the previous steps, you now have a 
number that tells you, if you were to have actually calculated N!, and 
then factored it, the number of times 5 would have been a factor.  And 
since for each one of these there's at least one 2, you happen to also 
have the count of how many times N! was multipled by 2*5, or 10, which is 
also the number of trailing zeroes.

I just tried this approach out, using the values given at that web page, 
and it works both quickly and accurately:

if __name__ == "__main__":
sampleinput = [3, 60, 100, 1024, 23456, 8735373]
sampleoutput = [0, 14, 24, 253, 5861, 2183837]
actualoutput = []
for n in sampleinput:
actualoutput.append(numfaczeroes(n))
assert actualoutput == sampleoutput
print actualoutput

C:\test\FCTRL>fctrl.py
[0, 14, 24, 253, 5861, 2183837]

I'll leave the coding of the numfaczeroes function as an exercise.


___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] python problem

[Michael Langford]

Look here. Do this: http://en.wikipedia.org/wiki/Binary_search

-- 
Michael Langford
Phone: 404-386-0495
Consulting: http://www.TierOneDesign.com/
Entertaining: http://www.ThisIsYourCruiseDirectorSpeaking.com

On 9/25/07, Chris <[EMAIL PROTECTED]> wrote:
>
>  
>
> ***I have this GUESSING GAME code found below:*
>
> -
>
> import random
>
> number = random.randint(1, 101)
>
> print "I've thought of a number between 1 and 100."
>
> print "Try and guess it!"
>
> print
>
> guess = input( "What's your guess? ")
>
> while guess != number:
>
> if guess > number:
>
> print "Your guess is too high."
>
> else: #elif guess < number:
>
> print "Your guess is too low."
>
> guess = input( "What's your next guess? " )
>
>
>
> print "Congratulations! You guessed the number."
>
> 
>
> ***What do I have to do to the code so that the
> Guessing Game that tries to guess a number the user has thought
> of. (Make sure it can tell if the user tries to cheat, e.g. by changing
> the number during the game??*
>
> *I hope you can help!*
>
> *Chris*
>
> No virus found in this outgoing message.
> Checked by AVG Free Edition.
> Version: 7.5.487 / Virus Database: 269.13.25/1018 - Release Date:
> 9/19/2007 3:59 PM
>
>
> ___
> Tutor maillist  -  Tutor@python.org
> http://mail.python.org/mailman/listinfo/tutor
>
>
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

[Tutor] python problem

[Chris]

I have this GUESSING GAME code found below:

-

import random

number = random.randint(1, 101)
print "I've thought of a number between 1 and 100."
print "Try and guess it!"
print

guess = input( "What's your guess? ")

while guess != number:
if guess > number:
print "Your guess is too high."
else: #elif guess < number:
print "Your guess is too low."
guess = input( "What's your next guess? " )

print "Congratulations! You guessed the number."



What do I have to do to the code so that the Guessing Game that tries to
guess a number the user has thought of. (Make sure it can tell if the user
tries to cheat, e.g. by changing the number during the game??

I hope you can help!

Chris

No virus found in this outgoing message.
Checked by AVG Free Edition. 
Version: 7.5.487 / Virus Database: 269.13.25/1018 - Release Date: 9/19/2007
3:59 PM
 
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] largest and smallest numbers

[Kent Johnson]

Christopher Spears wrote:

> How can I find the largest float and complex numbers?

I don't know how to do this in standard Python. Here are some answers 
that use Numeric and numpy:
http://groups.google.com/group/comp.lang.python/msg/fa7a761411ced62b
http://www.thescripts.com/forum/post2028282-8.html

Here is the numpy solution on my machine:
In [1]: from numpy import *
In [2]: print finfo(float32)
Machine parameters for 
-
precision=  6   resolution=  1.000e-06
machep=   -23   eps=   1.1920929e-07
negep =   -24   epsneg=5.9604645e-08
minexp=  -126   tiny=  1.1754944e-38
maxexp=   128   max=   3.4028235e+38
nexp  = 8   min=   -max
-

Kent
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] largest and smallest numbers

[Terry Carroll]

On Mon, 24 Sep 2007, Christopher Spears wrote:

> How can I find the largest float and complex numbers?

That's an interesting question..

I just tried this:

x = 2.0
while True:
x = x*2
print x
if repr(x) == "1.#INF": break

to just keep doubling X until Python began representing it as infinity.  
My output:

4.0
8.0
16.0
32.0
64.0
128.0
 . . .
137438953472.0
274877906944.0
549755813888.0
1.09951162778e+012
2.1990232e+012
4.3980465111e+012
 . . .
2.24711641858e+307
4.49423283716e+307
8.98846567431e+307
1.#INF

So I'd say, the answer is somewhere between 8.98846567431e+307 and double 
that.

On complex numbers, I'm not so sure.  My math is rusty. Is there a concept
of "greater than" or "largest" in complex numbers on different axis?  
Which is larger, 4+2i or 2+4i?

>>> complex(4,2)
(4+2j)
>>> complex(2,4)
(2+4j)
>>> complex(4,2) > complex(2,4)
Traceback (most recent call last):
  File "", line 1, in 
TypeError: no ordering relation is defined for complex numbers

___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

[Tutor] Need help speeding up algorithm.

[Ian Witham]

Hello,

I am attempting to do this  project for
the Sphere Online Judge.

I think my program is getting the right answer, however it exceeds the 6s
time limit on the judge machine.

Here is my code:


import sys

testnums = []
tests = int(sys.stdin.readline())

for count in xrange(tests):
testnums.append(int(sys.stdin.readline()))

for d in testnums:
maxer = int(d ** .2) + 1
g = sum(d / (5 ** x) for x in xrange(1, maxer))
sys.stdout.write('%d\n' % g)



Any ideas on how to speed this up?

Also, if anyone is familiar with the Online Judge system, am I correct in
gathering all of the input first and then providing the output? Or should I
be providing output after each input?


Any help appreciated,

Ian.
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] quick question

[Terry Carroll]

On Mon, 24 Sep 2007, max baseman wrote:

> for example how hard would it be to write a program that take's a  
> input of a in out table and finds the rule
> 
> ex:
> 
>   in  out
>   10  23
>   5   13
>   1   5
>   0   3
> 
> the rule is in*2+3

This is called linear regression.  A search for "Python Linear Regression"
should help you out.  Some sample code is at
http://www.answermysearches.com/how-to-do-a-simple-linear-regression-in-python/124/


___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

[Tutor] largest and smallest numbers

[Christopher Spears]

One of the exercises from Core Python Programmng (2nd
Edition) asks me to determine the largest and smallest
integers, float, and complex numbers my system can
handle.  Using python.org and Google, I have
discovered my system's largest and smallest ingtegers:

>>> import sys
>>> sys.maxint
2147483647
>>> -sys.maxint - 1
-2147483648

How can I find the largest float and complex numbers?
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

[Tutor] quick question

[max baseman]

hello just a quickie today :)

how is python with patters or finding a rule for something ie: in out  
tables
for example how hard would it be to write a program that take's a  
input of a in out table and finds the rule

ex:

in  out
10  23
5   13
1   5
0   3

the rule is in*2+3

if possible do you know any tutorials that would help


thanks 
   
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] pythons xf86misc documentation ?

[Noufal Ibrahim]

dave selby wrote:
> Can anyone tell me where the documentation for pythons xf86misc module
> is, ie what methods are avalible ?

I've not used this module you mention myself but if it's got docstrings 
and inline documentation, you can get help by importing the module and 
then doing a

help(xf86misc)

at the python interpreter prompt.

You can also run a local pydoc server if you prefer clickable HTML 
documentation.

Peace.
-- 
~noufal
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] Capturing ctrl-c

[Jason Massey]

Interesting.

As Michael suggested this works, mostly:

from time import sleep

def loop():
x = 0
while 1:
print "x:",x
x += 1
sleep(0.5)

if __name__ == "__main__":
while 1:
try:
loop()
except KeyboardInterrupt:
print "Nope, not going to stop."


Ctrl-C is ignored.  But on Win XP, at least, Ctrl-Break still exits the
program.

On 9/22/07, Michael Langford <[EMAIL PROTECTED]> wrote:
>
> When I do real applications with exception based languages, I almost
> always wrap the main function with a try/except block to allow me to
> gracefully shut down.
>
> In the case of python, this means 1> Use the main method 2> wrap its
> execution in a try catch:
>
> import mymodule
>
> def do_stuff():
> pass
>
> def graceful_cleanup()
> pass
>
> if "__main__" == __name__:
>try:
>  do_stuff()
>except:
>  graceful_cleanup()
>
> --Michael
>
> --
> Michael Langford
> Phone: 404-386-0495
> Consulting: http://www.TierOneDesign.com/
> Entertaining: http://www.ThisIsYourCruiseDirectorSpeaking.com
>
> On 9/22/07, James <[EMAIL PROTECTED]> wrote:
> >
> > Hi.  :)
> >
> > I'm whipping up a program in Python and am having to deal with a user
> > potentially hitting ctrl-c at any point in the program.  I'd like my
> > Python program to wrap up cleanly when it receives this signal.
> >
> > I did some Googling and read that Python throws a KeyboardInterrupt
> > error.  What's the best way to run a specific "cleanup" function at
> > *any* time the interrupt is received, regardless of where the program
> > is in execution?
> >
> > Most of the stuff I've read involves try-except blocks.  This makes
> > sense to me if I want to protect a specific function or area of the
> > code from being interrupted by ctrl-c, but I'm not sure what kind of
> > structure my program must have to catch the exception at any point
> > during execution.
> >
> > Thoughts/ideas appreciated.  :)
> >
> > Thanks!
> > .james
> > ___
> > Tutor maillist  -   Tutor@python.org
> > http://mail.python.org/mailman/listinfo/tutor
> >
>
>
> ___
> Tutor maillist  -  Tutor@python.org
> http://mail.python.org/mailman/listinfo/tutor
>
>
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] python problem - help!!

[Kent Johnson]

Chris wrote:
> I need your help!
> 
>  
> 
> I have this problem that I can’t seem to figure out.  Can you help?  The 
> problem is listed below, and below it is my code that I have so far.

This looks like a homework problem. We can help you understand Python 
but we won't give you the answer.

> if random.randint(1,8) >= 5:
> 
> 'Team A' = team
> 
> else:
> 
> 'Team B' = team

Your assignment statements are backwards here, it should be
team = 'Team A' etc.

Kent
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] tutor_request

[Luke Paireepinart]

oops, forgot to send this to tutor as well.
And I'm the one always complaining about direct e-mails :)
Luke Paireepinart wrote:

bedilu woldemariam wrote:

help!

here, take this:






Hope that helped,
-Luke




--- Begin Message ---

bedilu woldemariam wrote:

help!

here, take this:






Hope that helped,
-Luke

--- End Message ---
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

[Tutor] tutor_request

[bedilu woldemariam]

help!
   
-
Luggage? GPS? Comic books? 
Check out fitting  gifts for grads at Yahoo! Search.___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] [Fwd: Re: python problem - help!!]

[bhaaluu]

> print 'testvar: %.2f' % testvar
> Output:
> testvar: 10.0123

Should be:
print 'testvar: %.4f' % testvar
Output:
testvar: 10.0123

-- 
bhaaluu at gmail dot com


On 9/24/07, bhaaluu <[EMAIL PROTECTED]> wrote:
> Greetings,
>
> I ran the code sample you sent and found a couple of errors
> that wouldn't let the code run.
>
> The first error has to do with variable assignment.
> When you assign a variable, it is usually on the left and
> what you want to assign to it is on the right. See Lines 25,29.
>
> The second error has to do with the first error in a way.
> See Line 41.  '%d' is a placeholder for an integer.  '%2d' ?
> '%s' is a placeholder for a string.
> What "type" is the variable 'team'?
> (Hint: print type(team))
>
> '%.2f' is a placeholder for a float displaying
> two places to the right of decimal point.
> Example:
> testvar = 10.012345
> print 'testvar: %.2f' % testvar
> Output:
> testvar: 10.01
> print 'testvar: %.2f' % testvar
> Output:
> testvar: 10.0123
>
> As far as the maths in your program? I can't say.
> Perhaps if you get the program running, you can figure them out?
>
> Debugging tips:
> A cheap debugger that can be used
> as you create your program can
> be as simple as the following:
>
> variable = value   # assign a variable a value
> print variable   # display the value
> print type(variable)   # display the variable 'type'
> raw_input()   # breakpoint: (Pause. Press  to Continue...)
>
> --
> bhaaluu at gmail dot com
>
> On 9/24/07, Chris <[EMAIL PROTECTED]> wrote:
> > It's not a homework problem it is a practice problem to figure out how to
> > code, to be able to do the assignments...
> >
> >
> > Chris wrote:
> > > If I sent you the problem can you build it so I know what it is suppose to
> > > look like?  I've spend too much time it, and made it worse...all I know is
> > > that it does not produce the wanted results and is missing a loop...
> > >
> > > The worse part is that I did not find anything that can help me among the
> > > hundreds of websites I visited...
> >
> > No virus found in this incoming message.
> > Checked by AVG Free Edition.
> > Version: 7.5.487 / Virus Database: 269.13.25/1018 - Release Date: 9/19/2007
> > 3:59 PM
> >
> >
> >
> > No virus found in this outgoing message.
> > Checked by AVG Free Edition.
> > Version: 7.5.487 / Virus Database: 269.13.25/1018 - Release Date: 9/19/2007
> > 3:59 PM
> >
> >
> > ___
> > Tutor maillist  -  Tutor@python.org
> > http://mail.python.org/mailman/listinfo/tutor
> >
>
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] [Fwd: Re: python problem - help!!]

[bhaaluu]

Greetings,

I ran the code sample you sent and found a couple of errors
that wouldn't let the code run.

The first error has to do with variable assignment.
When you assign a variable, it is usually on the left and
what you want to assign to it is on the right. See Lines 25,29.

The second error has to do with the first error in a way.
See Line 41.  '%d' is a placeholder for an integer.  '%2d' ?
'%s' is a placeholder for a string.
What "type" is the variable 'team'?
(Hint: print type(team))

'%.2f' is a placeholder for a float displaying
two places to the right of decimal point.
Example:
testvar = 10.012345
print 'testvar: %.2f' % testvar
Output:
testvar: 10.01
print 'testvar: %.2f' % testvar
Output:
testvar: 10.0123

As far as the maths in your program? I can't say.
Perhaps if you get the program running, you can figure them out?

Debugging tips:
A cheap debugger that can be used
as you create your program can
be as simple as the following:

variable = value   # assign a variable a value
print variable   # display the value
print type(variable)   # display the variable 'type'
raw_input()   # breakpoint: (Pause. Press  to Continue...)

-- 
bhaaluu at gmail dot com

On 9/24/07, Chris <[EMAIL PROTECTED]> wrote:
> It's not a homework problem it is a practice problem to figure out how to
> code, to be able to do the assignments...
>
>
> Chris wrote:
> > If I sent you the problem can you build it so I know what it is suppose to
> > look like?  I've spend too much time it, and made it worse...all I know is
> > that it does not produce the wanted results and is missing a loop...
> >
> > The worse part is that I did not find anything that can help me among the
> > hundreds of websites I visited...
>
> No virus found in this incoming message.
> Checked by AVG Free Edition.
> Version: 7.5.487 / Virus Database: 269.13.25/1018 - Release Date: 9/19/2007
> 3:59 PM
>
>
>
> No virus found in this outgoing message.
> Checked by AVG Free Edition.
> Version: 7.5.487 / Virus Database: 269.13.25/1018 - Release Date: 9/19/2007
> 3:59 PM
>
>
> ___
> Tutor maillist  -  Tutor@python.org
> http://mail.python.org/mailman/listinfo/tutor
>
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor