Re: [Tutor] primes - sieve of odds

2005-03-26 Thread John Miller 
On Mar 24, 2005, at 6:01 AM, C Smith [EMAIL PROTECTED] wrote:
What follows is an attempt based on the previous tutor-evolved sieve
that extends the range in which to find the next prime by a factor of
2 over the last known prime. A similar algorithm is on ASPN (I
bellieve), under
Space-efficient version of sieve of Eratosthenes.
D. Eppstein, May 2004
Oh, please...ignore what I suggested and look at Eppstein's code. It's
a thing of beauty and just keeps chugging out primes well past what the
inefficient version that I suggested could do with the same memory.
It's a tortoise and hare race as the memory gets chewed up by the
esieve approach.
The ASPN version of Eppstein's program is an older one than the one at
the following site:
http://www.ics.uci.edu/~eppstein/PADS/Eratosthenes.py
How does one actually use this module? For example:
 import eratosthenes
 eratosthenes.primes()
generator object at 0x640d0
 eratosthenes.primes().next()
2
 eratosthenes.primes().next()
2
 eratosthenes.primes().next()
2
How does one get beyond the first prime?
Thanks,
John
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] primes - sieve of odds

2005-03-26 Thread Sean Perry 
John Miller wrote:
How does one actually use this module? For example:
  import eratosthenes
  eratosthenes.primes()
generator object at 0x640d0
  eratosthenes.primes().next()
2
  eratosthenes.primes().next()
2
  eratosthenes.primes().next()
2
How does one get beyond the first prime?
it = eratosthenes.primes()
it.next()
it.next()
or
# 'it' is shorthand for iterator
def primesToN(n):
it = eratosthenes.primes()
return [ x for x in it if x = n ]
You were running into problems because the primes() function returns a 
new generator. The values are in the generator not the function primes().
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] primes - sieve of odds

2005-03-23 Thread C Smith 
On Wednesday, Mar 23, 2005, at 04:00 America/Chicago, 
[EMAIL PROTECTED] wrote:

Now it would be fine to have an *equally fast*
infinite prime number generator.
Has anybody any suggestions?
I think when you add the condition of it being an infinite generator, 
you are changing the rules and can't end up with something as fast.  
What makes the sieve so fast is that we are generating all the primes 
in a given range using a very simple strike out method.  In the 
infinite generator scenario, you will get all the primes up to n with 
the sieve and can yield those back, but at some point you will have to 
stop and get the next one. To get the next one you will have to pick 
a range in which a next prime is likely to be found. The previous 
primes can be used to clear out this range.

What follows is an attempt based on the previous tutor-evolved sieve 
that extends the range in which to find the next prime by a factor of 2 
over the last known prime. A similar algorithm is on ASPN (I bellieve), 
under

Space-efficient version of sieve of Eratosthenes.
D. Eppstein, May 2004
It's slower than the sieve but about twice as fast as Eppstein's up to 
1,000,000.  I'll leave it to someone else to see when it finally blows 
up :-) The output of primes was checked through 1,000,000 against 
Eppstein's generator without error.

/c
###
def esieve():
'''extended sieve generator that returns primes on each call. When the 
end of the
existing list is reached, more primes are sought in the range that 
extends to
twice the last known prime. The known primes are used to clear out this 
extended
range using the Sieve of Eratosthenes.'''

# get started with primes less than 100; you need at least [2, 3]
primes=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
i=0
while 1:
yield primes[i]
i+=1
if i==len(primes): #extend range
minn=primes[-1]+2 #this is an odd number
maxx=2*minn+1 #there should be a prime in this range; +1 
makes it odd
sqrt=int(maxx**.5) #don't use primes bigger than this
length = (maxx-minn)//2 #this is used for computing the 
crossing out None values
nums=range(minn,maxx+1,2) #here is the range in which a 
primes will be found
for p in primes:
if psqrt:break
j=minn%p #find out where the striking out should start
if j0:
j=(p-j) #if evens were present, this is where to 
start, but...
if (minn+j)%2==0:j+=p #if it lands on an even, go 
to the next one
j//=2 #and now account for the fact that evens 
aren't present
nums[j::p]=[None]*(1+(length-j)//p) #cross out 
multiples of p
x=filter(None,nums) #clean up the range
assert len(x)0 #there should be a prime in here, but check 
anyway
primes.extend(x) #add these to the existing primes and 
continue yielding
###

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

Re: [Tutor] primes - sieve of odds

2005-03-22 Thread C Smith 
Hi Gregor,
I had done the same thing.  I also noted that assigning (or inserting) 
an element into a list is faster than creating a new list: 
l.insert(0,2) is faster than l = [2]+l.

###
def sieve (maximum):
 if maximum  2: return []
 limit = int(maximum**0.5)
 nums = range(1,maximum+1,2)
 nums[0] = None
 for p in nums:
 if p:
 if p  limit: break
 nums[(p*p)//2::p] = [False]*(1+(maximum//p- p)//2)
 nums[0] = 2
 return filter(None, nums)
###
/c
Hi Sean!
Thanks for your measurements.
In the meantime I did another amendment,
leaving out the even numbers from the sieve.
It goes like this:
def sieve(maximum):
 nums = range(3, maximum+1, 2)
 for p in nums:
 if p:
 if p*p  maximum: break
 start = (p*p-2)//2
 nums[start::p] = [False]*(1+((maximum-3)//2-start)//p)
 return [2] + filter(None, nums)
Perhaps not very elegant. But approximately twice as fast as
the former version.

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

Re: [Tutor] primes (generator)

2005-03-20 Thread Gregor Lingl 
Karl Pflästerer schrieb:
On 19 Mrz 2005, [EMAIL PROTECTED] wrote:
[Code]
Maybe sombody likes...

I did it ... :
def sieve (max):
max = max + 1
border = round(max**0.5)
nums = range(0, max)
nums[0] = nums[1] = None
for p in nums:
if p:
if p = border: break 
for i in xrange(p+p, max, p):
nums[i] = None
return filter(None, nums)

Hi Karl!
The following variation of your sieve, using
extended slice assignment  seems to
be sgnificantly faster. Try it out, if you like.
def sieve (maximum):
limit = int(maximum**0.5)
nums = range(maximum+1)
nums[0] = nums[1] = None
for p in nums:
if p:
if p  limit: break
nums[p*p:maximum+1:p] = [False]*(1-p+maximum//p)
return filter(None, nums)
Regards
Gregor


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

Re: [Tutor] primes (generator)

2005-03-20 Thread Sean Perry 
Gregor Lingl wrote:
The following variation of your sieve, using
extended slice assignment  seems to
be sgnificantly faster. Try it out, if you like.
Here are the numbers:
Primes 1 - 1,000,000 timing:
   extendedSliceSieve: 0.708388 seconds
   listPrimes: 0.998758 seconds
karlSieve: 1.703553 seconds
primeConciseOptimized: 5.133922 seconds
 setSieve: 7.564576 seconds
 primeConcise: 1644.683214 seconds -- 27 minutes 24 seconds
if __name__ == '__main__':
# setup timers as a list of tuples (name, timeit instance)
results = []
longest = 0
for t in timers:
result = t[1].timeit(1)
longest = max(longest, len(t[0]))
results.append((t[0], result))
results.sort(lambda x, y: cmp(x[1], y[1]))
print Primes 1 - 1,000,000 timing:
format_str = %%%ds: %%f seconds % longest
for i in results:
print format_str % i
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] primes - sieve of odds

2005-03-20 Thread Gregor Lingl 
Hi Sean!
Thanks for your measurements.
In the meantime I did another amendment,
leaving out the even numbers from the sieve.
It goes like this:
def sieve(maximum):
nums = range(3, maximum+1, 2)
for p in nums:
if p:
if p*p  maximum: break
start = (p*p-2)//2
nums[start::p] = [False]*(1+((maximum-3)//2-start)//p)
return [2] + filter(None, nums)
Perhaps not very elegant. But approximately twice as fast as
the former version.
Best wishes,
Gregor
Sean Perry schrieb:
Gregor Lingl wrote:
The following variation of your sieve, using
extended slice assignment  seems to
be sgnificantly faster. Try it out, if you like.
Here are the numbers:
Primes 1 - 1,000,000 timing:
   extendedSliceSieve: 0.708388 seconds
   listPrimes: 0.998758 seconds
karlSieve: 1.703553 seconds
primeConciseOptimized: 5.133922 seconds
 setSieve: 7.564576 seconds
 primeConcise: 1644.683214 seconds -- 27 minutes 24 seconds
if __name__ == '__main__':
# setup timers as a list of tuples (name, timeit instance)
results = []
longest = 0
for t in timers:
result = t[1].timeit(1)
longest = max(longest, len(t[0]))
results.append((t[0], result))
results.sort(lambda x, y: cmp(x[1], y[1]))
print Primes 1 - 1,000,000 timing:
format_str = %%%ds: %%f seconds % longest
for i in results:
print format_str % i
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

--
Gregor Lingl
Reisnerstrasse 3/19
A-1030 Wien
Telefon: +43 1 713 33 98
Mobil:   +43 664 140 35 27
Autor von Python für Kids
Website: python4kids.net
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] primes (generator)

2005-03-19 Thread Karl Pflästerer 
On 19 Mrz 2005, [EMAIL PROTECTED] wrote:

[Code]
 Maybe sombody likes to compare these algorithms to the
 ones mentioned before in this thread. I would be
 interested in the results.

I did it and on my machine here (a slow one) the following straight
forward version is the fastest one.

It's no iterator and since all the numbers are stored in a list you need
place proportional the number of entries but it's fast and it works
nearly the same way the original sieve of Erasthosthens algorithm works.

Here it is no error to modify the list which gets iterated over.

def sieve (max):
max = max + 1
border = round(max**0.5)
nums = range(0, max)
nums[0] = nums[1] = None
for p in nums:
if p:
if p = border: break 
for i in xrange(p+p, max, p):
nums[i] = None
return filter(None, nums)



   Karl
-- 
Please do *not* send copies of replies to me.
I read the list
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] primes

2005-03-18 Thread Max Noel 
On Mar 18, 2005, at 02:15, Kent Johnson wrote:
Max Noel wrote:
#!/usr/bin/env python
import math
import timeit
def primeConcise(limit):
return [2] + [x for x in xrange(3, limit, 2) if not [y for y in 
[2] + range(3,x,2) if x%y==0]]
def primeConciseOptimized(limit):
return [2] + [x for x in xrange(3, limit, 2) if not [y for y in 
[2] + range(3,int(math.sqrt(x)), 2) if x%y==0]]
Hmm, I didn't know that 9 and 15 were prime...
When I'm doing timings like this I usually check the output. You can 
write a *very* fast algorithm if correctness does not count :-)
	Damn. Got bitten again by the fact that range/xrange return start = n 
 end and not start = n = end. Python lacks Ruby's range objects ( 
(start..end) or (start...end) depending on what you want).
	In the (pythonized) words of E. Dijkstra, if it doesn't have to work, 
pass is a good solution.
	I blame sleep deprivation. -.-

Note I don't bother testing for divisibility by 2 since the candidates 
are all odd. This allows using xrange() instead of range() for a 
significant improvement.

My times:
listPrimes 0.143752069048
primeConciseOptimized 0.586845814203
primeConciseOptimized2 0.391731351331
Kent
	Mmh... Good one. Didn't think of it.
	What can I say... I love stupid optimization challenges. Now I wonder 
if someone is going to dare come up and kick our asses with a version 
that does this with a C module... :D

-- Max
maxnoel_fr at yahoo dot fr -- ICQ #85274019
Look at you hacker... A pathetic creature of meat and bone, panting 
and sweating as you run through my corridors... How can you challenge a 
perfect, immortal machine?

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

Re: [Tutor] primes

2005-03-18 Thread Pierre Barbier de Reuille 
Gregor Lingl a écrit :
Hi!
Who knows a more concise or equally concise but more efficient
expression, which returns the same result as
[x for x in range(2,100) if not [y for y in range(2,x) if x%y==0]]
Gregor
P.S.: ... or a more beautiful one ;-)
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor
The fastest know way for your problem is the Eratosten sieve ...
Here's an implementation :
from sets import Set
from math import sqrt
def sieve( max ):
  max_val = int( sqrt( max ) )
  s = Set(xrange( 4, max, 2 ))
  for i in xrange( 3, max_val, 2 ):
s.update( xrange( 2*i, max, i ) )
  return [ i for i in xrange( 2, max ) if i not in s ]
I compared with the implementations of Gregor (optimized) and Max and 
here is the result :

listPrimes(10)= 0.637619972229 (Max implementation)
primeConciseOptimized(10) = 2.9141831398   (Gregor optimized)
sieve(10) = 0.49525809288  (Eratosten sieve)
You'll just notice that Eratosten sieve is O(n) space consumption when 
others are less (I don't remember the density of prime numbers :o) ) 
were n is the maximum number you're looking for.

Pierre
--
Pierre Barbier de Reuille
INRA - UMR Cirad/Inra/Cnrs/Univ.MontpellierII AMAP
Botanique et Bio-informatique de l'Architecture des Plantes
TA40/PSII, Boulevard de la Lironde
34398 MONTPELLIER CEDEX 5, France
tel   : (33) 4 67 61 65 77fax   : (33) 4 67 61 56 68
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] primes (generator)

2005-03-18 Thread Gregor Lingl 
Hi all of you!
Many thanks for your remarks, ideas and experiments.
When I posted my input yesterday:
[x for x in range(2,100) if not [y for y in range(2,x) if x%y==0]]
my intention was indeed to find a shortest a program, disregarding
efficiency. Thus range instead of xrange etc.
(About one year ago I was involved in a coding contest at Linux-Tag
in Karlsruhe, where the goal was to achive a certain output with a
shortest program ;-) Strange. I used Python, but I didn't win :-(  )
Clearly there are several criteria concerning the quality of programs
as e. g. conciseness, clarity, efficiency, beauty(!) etc. which may not
be achieved optimally all together ...
I definitely intend to sum up your contibutions (for me) later, but for
now (because of lack of time) I'll only present one more idea,
induced by Danny's (unfortunately buggy - because of recursion overflow) 
contribution:

Thought it would be nice to use Python's new generator-expressions
instead of itertool module. First idea:
##
# infinite prime generator
# induced by ideas of Danny Yoo,
# which themselves were induced by material of SICP
import math
def prime(n):
return [x for x in range(2,1+int(math.sqrt(n))) if n%x==0]==[]
def infrange(n):
while True:
yield n
n+=1
primes = (p for p in infrange(2) if prime(p))
###  The generator primes works like this:
 primes.next()
2
 primes.next()
3
 primes.next()
5
 [primes.next() for i in range(10)]
[7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
 [primes.next() for i in range(100)]
[43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 
113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 
193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 
271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 
359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 
443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 
541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617]

 ### You may also use it this way:
 for p in primes:
	if p  1000: break
	print p,

	
619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 
743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 
863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997

With a fresh generator
[primes.next() for p in xrange(1)]
produces (on my machine) a list of the first 1 primes (upto 104729)
within 4.68 secs.
Now for a bit of optimization: instead of building a list of
all divisors use a loop and get out as soon as possible:
So I replace prime by:
def prime(n):
for d in range(2,1+int(math.sqrt(n))):
if n%d == 0: return  False
return True
This makes the generator nearly 4 times as fast. I get my list in
1.33 secs.
Lets optimize a bit more: test only 2 and odd numbers:
def infrange(n):
yield 2
n=3
while True:
yield n
n+=2
and do a similar thing for searching for divisors:
def prime(n):
if n==2: return True
for d in [2]+ range(3,1+int(math.sqrt(n)),2):
if n%d == 0: return  False
return True
Now the first 1  primes get computed in 0.67 secs.
Again double speed. Together seven times as fast as
first version. But IMO at the cost of clarity
and conciseness.
Maybe you have amendments (of course a matter of taste)
to this code. I'd be interested in them ..
Maybe sombody likes to compare these algorithms to the
ones mentioned before in this thread. I would be
interested in the results.
Regards,
Gregor

Danny Yoo schrieb:
On Thu, 17 Mar 2005, Gregor Lingl wrote:

Hi!
Who knows a more concise or equally concise but more efficient
expression, which returns the same result as
...
##
from itertools import ifilter, count
def notDivisibleBy(n):
... def f(x):
... return x % n != 0
... return f
...
def sieve(iterable):
... nextPrime = iterable.next()
... yield nextPrime
... restOfPrimes = sieve(ifilter(notDivisibleBy(nextPrime), iterable))
... for prime in restOfPrimes:
... yield prime
...
primes = sieve(count(2))
primes.next()
2
primes.next()
...
primes.next()
23
##
The neat thing about this code is that it produces an infinite iterator of
prime numbers.  The original code in Scheme is itself quite concise and
quite nice.  It is described here:
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html#call_footnote_Temp_455
Best of wishes to you!

--
Gregor Lingl
Reisnerstrasse 3/19
A-1030 Wien
Telefon: +43 1 713 33 98
Mobil:   +43 664 140 35 27
Autor von Python für Kids
Website: python4kids.net
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] primes (Cautious remark on Python and Scheme)

2005-03-18 Thread Gregor Lingl 
Hi Danny!
Preliminary remark: I know that beautiful and beauty
are concepts very seldom applied to computer programs or
programming languages. I suppose mainly because they are
to a large extent a matter of taste ...
Nevertheless: regardeless of the fact that I'm not a very
skilled scheme-programmer, for me Scheme is the most beautiful
programming language I know, mainly because of the clear
and simple concepts which are purely realized. (I do *not* want
to discuss here questions like functional versus object-oriented
languages etc...)
However - Python - for me - is a programming language for
the pragmatic lover. Do you consider this expression as
self explanatory? Lover -- because it makes so much fun
to use it. Pragmatic -- because it is a language for the
real world ;-)
im*h*o the primes - examples we are just discussing shows,
that going *the Python way* may well be more successful
or rewarding than trying to translate, traduce, ...er ..
adapt Scheme-concepts quasi trying to show that Python is
at least as good as Scheme. This is not the question. (I
suppose that this also was not your goal?) A deeper
question perhaps would be to what degree the content of
cs texts depends on the choice of the mainly used language
therein.
On the contrary - we may learn from this example that Python
is a *very* good language in its own right - with carefully chosen
concepts and syntax and a very slow, serious and publicly
controlled development process resulting in a more and more
easily and efficiently usable language.
Finally I'd like to stress that your contribution for me
was very valuable and constructive - as are most of your
innumerable contributions to the discussions on this list.
Thanks an regards,
Gregor
post scriptum: as always when writing not only about technical
facts but about opinions and values in English, I'm a bit axious
if I was able to express correctly what I wanted to say. Hmmm.
Hope that I didn't create any misunderstandings 
Danny Yoo schrieb:
On Thu, 17 Mar 2005, Gregor Lingl wrote:

Hi!
Who knows a more concise or equally concise but more efficient
expression, which returns the same result as
[x for x in range(2,100) if not [y for y in range(2,x) if x%y==0]]

Hi Gregor,
Here is one that's traduced... er... adapted from material from the
classic textbook Structure and Interpretation of Computer Programs:
##
from itertools import ifilter, count
def notDivisibleBy(n):
... def f(x):
... return x % n != 0
... return f
...
def sieve(iterable):
... nextPrime = iterable.next()
... yield nextPrime
... restOfPrimes = sieve(ifilter(notDivisibleBy(nextPrime), iterable))
... for prime in restOfPrimes:
... yield prime
...
primes = sieve(count(2))
primes.next()
2
primes.next()
3
primes.next()
5
primes.next()
7
primes.next()
11
primes.next()
13
primes.next()
17
primes.next()
19
primes.next()
23
##
The neat thing about this code is that it produces an infinite iterator of
prime numbers.  The original code in Scheme is itself quite concise and
quite nice.  It is described here:
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html#call_footnote_Temp_455
Best of wishes to you!

--
Gregor Lingl
Reisnerstrasse 3/19
A-1030 Wien
Telefon: +43 1 713 33 98
Mobil:   +43 664 140 35 27
Autor von Python für Kids
Website: python4kids.net
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] primes (Cautious remark on Python and Scheme)

2005-03-18 Thread Gregor Lingl 

Concerning my previous posting - perhaps it
would suffice to summarize:
While Python is a language for the pragmatic lover,
Scheme is much more fundamentalistic.
(thought-) *PROVOKING*?
Gregor
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

[OT] Re: [Tutor] primes (Cautious remark on Python and Scheme)

2005-03-18 Thread Brian van den Broek 
Gregor Lingl said unto the world upon 2005-03-18 19:57:
Hi Danny!
Preliminary remark: I know that beautiful and beauty
are concepts very seldom applied to computer programs or
programming languages. I suppose mainly because they are
to a large extent a matter of taste ...
Hi Gregor and all,
Though I've not had the time to follow the details of the thread 
closely, it's stored for future perusal -- I'm really glad you started 
it, Gregor.

But, your comment above caught my eye. import this to see that beauty 
is embraced by the zen :-)

It's been a long day, so I don't feel I am saying this well, but:
When not trying to learn Python, I'm a (grad student) philosopher of 
logic and mathematics. I've thought some about beauty in proof, and 
hope to think seriously about it one day. Beauty in maths is like what 
the judge said about pornography -- I can't define it, but I know it 
when I see it. I've never met a philosopher or a mathematician who 
could give a compelling (and robust) account of what makes for beauty, 
but there is widespread convergence of judgements about which proofs 
are beautiful and which ugly. (This even though taste does enter into 
it, too.)

I think the same is true of (at least academic) computer science. The 
comp sci people I know at my uni all work in automated-theorem 
proving, and I know they use their perceptions of beauty as a design 
guide. And, with my much more limited experience with programming, my 
judgements that this code is ugly have been pretty reliable in 
identifying the problematic parts. If it is beautiful, it might be 
right. If it is ugly, it is likely wrong seems a safe claim.

Anyway, all this is to say that I think that what you know above is 
wrong :-)

SNIP
post scriptum: as always when writing not only about technical
facts but about opinions and values in English, I'm a bit axious
if I was able to express correctly what I wanted to say. Hmmm.
Hope that I didn't create any misunderstandings 
Ich kann Deutsch, aber nur ein bischen. I think I'd be a very happy 
fellow if my German were half as good as your English :-)

Best to all,
Brian vdB
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

[Tutor] primes

2005-03-17 Thread Gregor Lingl 
Hi!
Who knows a more concise or equally concise but more efficient
expression, which returns the same result as
[x for x in range(2,100) if not [y for y in range(2,x) if x%y==0]]
Gregor
P.S.: ... or a more beautiful one ;-)
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] primes

2005-03-17 Thread Max Noel 
On Mar 17, 2005, at 22:28, Gregor Lingl wrote:
Hi!
Who knows a more concise or equally concise but more efficient
expression, which returns the same result as
[x for x in range(2,100) if not [y for y in range(2,x) if x%y==0]]
Gregor
P.S.: ... or a more beautiful one ;-)
	Hmm... I don't have beautiful or concise, but I can offer fast. 
Here goes:

#!/usr/bin/env python
import math
def isPrime(x, primeList):
limit = math.sqrt(x)
for i in primeList:
if x % i == 0:
return False
if i = limit:
break
return True
def listPrimes(upperLimit):
listOfPrimes = []
for i in range(2, upperLimit):
if isPrime(i, listOfPrimes):
listOfPrimes.append(i)
return listOfPrimes
if __name__ == '__main__':
import sys
num = int(sys.argv[-1])
print listPrimes(num)

	That's the fastest way I can think of -- but I can't prove it, as I 
don't know how to use the timeit module.

-- Max
maxnoel_fr at yahoo dot fr -- ICQ #85274019
Look at you hacker... A pathetic creature of meat and bone, panting 
and sweating as you run through my corridors... How can you challenge a 
perfect, immortal machine?

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

Re: [Tutor] primes

2005-03-17 Thread jfouhy 
Quoting Gregor Lingl [EMAIL PROTECTED]:

 [x for x in range(2,100) if not [y for y in range(2,x) if x%y==0]]

Heh.  That's quite neat.

I can only offer one suggestion --- if you replace range with xrange, you get a
small speed improvement.

eg: On my system, it took 415 seconds to generate a list of primes  50,000
using range, but only 386 seconds if I use the same code, but with xrange 
instead.

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

Re: [Tutor] primes

2005-03-17 Thread Danny Yoo 


On Thu, 17 Mar 2005, Gregor Lingl wrote:

 Hi!
 Who knows a more concise or equally concise but more efficient
 expression, which returns the same result as

 [x for x in range(2,100) if not [y for y in range(2,x) if x%y==0]]


Hi Gregor,

Here is one that's traduced... er... adapted from material from the
classic textbook Structure and Interpretation of Computer Programs:

##
 from itertools import ifilter, count

 def notDivisibleBy(n):
... def f(x):
... return x % n != 0
... return f
...
 def sieve(iterable):
... nextPrime = iterable.next()
... yield nextPrime
... restOfPrimes = sieve(ifilter(notDivisibleBy(nextPrime), iterable))
... for prime in restOfPrimes:
... yield prime
...

 primes = sieve(count(2))
 primes.next()
2
 primes.next()
3
 primes.next()
5
 primes.next()
7
 primes.next()
11
 primes.next()
13
 primes.next()
17
 primes.next()
19
 primes.next()
23
##

The neat thing about this code is that it produces an infinite iterator of
prime numbers.  The original code in Scheme is itself quite concise and
quite nice.  It is described here:

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html#call_footnote_Temp_455


Best of wishes to you!

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

Re: [Tutor] primes

2005-03-17 Thread Max Noel 
On Mar 17, 2005, at 23:54, Danny Yoo wrote:
Hi Gregor,
Here is one that's traduced... er... adapted from material from the
classic textbook Structure and Interpretation of Computer Programs:
SNIP
Ooh, nifty.
	Okay, I decided to learn how to use the timeit module, so I used it to 
compare my algorithm (which, I just noticed, is a Python implementation 
of the Sieve of Erastothenes) to the one Gregor originally posted 
(albeit slightly optimized -- the only even prime number is 2, so 
there's no need to test them), and a further optimized version of it 
(stops looping at sqrt(x)).
	While I was at it, I optimized my algorithm further (in both memory 
usage and speed): it uses xrange and doesn't bother testing even 
numbers.

	Now, I did expect my algorithm to be the fastest. What I didn't 
expect, though, was for the differences to be *that* massive. Letting 
all three functions loose on finding all the prime numbers from 2 to 
5, I got the following results (test machine: G4 867 running Python 
2.3 on OS X 10.3.8):

listPrimes: 0.508284091949 seconds  # my algorithm
primeConciseOptimized: 2.18135714531 seconds# Gregor's, optimized
primeConcise: 399.251116991 seconds # Gregor's, (partially 
optimized)
	As I suspected, when increasing the range, so do the differences. 
listPrimes finds all prime numbers from 2 to 20 in 2.55 seconds, 
primeConciseOptimized in 15.81. At that point I had dropped 
primeConcise, as it being O(n^3) as far as I can tell, it would have 
taken ages to run. However, I thought the difference between listPrimes 
and primeConciseOptimized would increase faster than that. So 
primeConciseOptimized seems like the best compromise between speed and 
conciseness.

Here's the (final?) version of the script I used:
#!/usr/bin/env python
import math
import timeit
def primeConcise(limit):
return [2] + [x for x in xrange(3, limit, 2) if not [y for y in [2] 
+ range(3,x,2) if x%y==0]]

def primeConciseOptimized(limit):
return [2] + [x for x in xrange(3, limit, 2) if not [y for y in [2] 
+ range(3,int(math.sqrt(x)), 2) if x%y==0]]

def isPrime(x, primeList):
limit = int(math.sqrt(x))
for i in primeList:
if x % i == 0:
return False
if i = limit:
break
return True
def listPrimes(upperLimit):
listOfPrimes = [2]
for i in xrange(3, upperLimit, 2):
if isPrime(i, listOfPrimes):
listOfPrimes.append(i)
return listOfPrimes
if __name__ == '__main__':
t1 = timeit.Timer('listPrimes(5)', 'from __main__ import 
listPrimes')
t2 = timeit.Timer('primeConciseOptimized(5)', 'from __main__ 
import primeConciseOptimized')
t3 = timeit.Timer('primeConcise(5)', 'from __main__ import 
primeConcise')
print t1.timeit(1)
print t2.timeit(1)
print t3.timeit(1)


-- Max
maxnoel_fr at yahoo dot fr -- ICQ #85274019
Look at you hacker... A pathetic creature of meat and bone, panting 
and sweating as you run through my corridors... How can you challenge a 
perfect, immortal machine?

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

Re: [Tutor] primes

2005-03-17 Thread Kent Johnson 
Max Noel wrote:
#!/usr/bin/env python
import math
import timeit
def primeConcise(limit):
return [2] + [x for x in xrange(3, limit, 2) if not [y for y in [2] 
+ range(3,x,2) if x%y==0]]

def primeConciseOptimized(limit):
return [2] + [x for x in xrange(3, limit, 2) if not [y for y in [2] 
+ range(3,int(math.sqrt(x)), 2) if x%y==0]]
Hmm, I didn't know that 9 and 15 were prime...
When I'm doing timings like this I usually check the output. You can write a *very* fast algorithm 
if correctness does not count :-)

Here is a version that gives correct results at least up to limit=50:
def primeConciseOptimized(limit):
return [2] + [x for x in xrange(3, limit, 2) if not [y for y in [2] + 
range(3,int(math.sqrt(x))+1, 2) if x%y==0]]

One reason your listPrimes() function is faster is that it short-circuits the test - as soon as a 
divisor is found for a candidate, no further testing is done. primeConciseOptimized() always tests 
all the candidate divisors.

In the spirit of useless optimizations of bad algorithms ;) I used itertools to make a 
short-circuiting version of primeConciseOptimized():

import itertools
def no(seq, pred=bool):
'''Returns True if pred(x) is False for every element in the iterable
   From the itertools recipes. '''
for elem in itertools.ifilter(pred, seq):
return False
return True
def primeConciseOptimized2(limit):
return [2] + [x for x in xrange(3, limit, 2) if no(xrange(3,int(math.sqrt(x))+1, 2), lambda y: 
x%y==0)]

Note I don't bother testing for divisibility by 2 since the candidates are all odd. This allows 
using xrange() instead of range() for a significant improvement.

My times:
listPrimes 0.143752069048
primeConciseOptimized 0.586845814203
primeConciseOptimized2 0.391731351331
Kent
def isPrime(x, primeList):
limit = int(math.sqrt(x))
for i in primeList:
if x % i == 0:
return False
if i = limit:
break
return True
def listPrimes(upperLimit):
listOfPrimes = [2]
for i in xrange(3, upperLimit, 2):
if isPrime(i, listOfPrimes):
listOfPrimes.append(i)
return listOfPrimes
if __name__ == '__main__':
t1 = timeit.Timer('listPrimes(5)', 'from __main__ import 
listPrimes')
t2 = timeit.Timer('primeConciseOptimized(5)', 'from __main__ 
import primeConciseOptimized')
t3 = timeit.Timer('primeConcise(5)', 'from __main__ import 
primeConcise')
print t1.timeit(1)
print t2.timeit(1)
print t3.timeit(1)


-- Max
maxnoel_fr at yahoo dot fr -- ICQ #85274019
Look at you hacker... A pathetic creature of meat and bone, panting and 
sweating as you run through my corridors... How can you challenge a 
perfect, immortal machine?

___
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] primes

2005-03-17 Thread C Smith 
On Thursday, Mar 17, 2005, at 17:49 America/Chicago, 
[EMAIL PROTECTED] wrote:

On my system, it took 415 seconds to generate a list of primes  50,000
using range, but only 386 seconds if I use the same code, but with 
xrange instead.


If you only calculate y up to sqrt(x) you will see a dramatic time 
reduction:

###
import math
big=5
[x for x in xrange(2,big) if not [y for y in 
range(2,int(math.sqrt(x)+1)) if x%y==0]]
###

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

Re: [Tutor] primes

2005-03-17 Thread Sean Perry 
Danny Yoo wrote:
Here is one that's traduced... er... adapted from material from the
classic textbook Structure and Interpretation of Computer Programs:
##
from itertools import ifilter, count
def notDivisibleBy(n):
... def f(x):
... return x % n != 0
... return f
...
def sieve(iterable):
... nextPrime = iterable.next()
... yield nextPrime
... restOfPrimes = sieve(ifilter(notDivisibleBy(nextPrime), iterable))
... for prime in restOfPrimes:
... yield prime
...
primes = sieve(count(2))
primes.next()

which is cool, until you try to use it (-:
It dies at 999 primes due to an overloaded stack. Bummer. It is such a 
nifty implementation.

I modified this version to follow it better.
from itertools import ifilter, count
def notDivisibleBy(n):
def f(x):
return x % n != 0
return f
def sieve(iterable):
nextPrime = iterable.next()
print 'x', nextPrime
yield nextPrime
restOfPrimes = sieve(ifilter(notDivisibleBy(nextPrime), iterable))
for prime in restOfPrimes:
print 'p', prime
yield prime
primes = sieve(count(2))
current = primes.next()
count = 1
while current = 20:
print 'Prime:', current
current = primes.next()
count += 1
The output is (note this is each prime  20):
x 2
Prime: 2
x 3
p 3
Prime: 3
x 5
p 5
p 5
Prime: 5
x 7
p 7
p 7
p 7
Prime: 7
x 11
p 11
p 11
p 11
p 11
Prime: 11
x 13
p 13
p 13
p 13
p 13
p 13
Prime: 13
x 17
p 17
p 17
p 17
p 17
p 17
p 17
Prime: 17
x 19
p 19
p 19
p 19
p 19
p 19
p 19
p 19
Prime: 19
x 23
p 23
p 23
p 23
p 23
p 23
p 23
p 23
p 23
Not exactly efficient.
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor