Re: Prime number generator

References	<mailman.4522.1373464867.3114.python-list@python.org> <51dd8560$0$9505$c3e8da3$5496439d@news.astraweb.com>
Date	2013-07-11 02:52 +1000
Subject	Re: Prime number generator
From	Chris Angelico <rosuav@gmail.com>
Newsgroups	comp.lang.python
Message-ID	<mailman.4538.1373475160.3114.python-list@python.org> (permalink)

Show all headers | View raw

On Thu, Jul 11, 2013 at 2:01 AM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> On Thu, 11 Jul 2013 00:00:59 +1000, Chris Angelico wrote:
>> Thirdly, is there any sort of half-sane benchmark that I
>> can compare this code to? And finally, whose wheel did I reinvent here?
>> What name would this algorithm have?
>
> I can't directly answer that question, but I can make a shameless plug
> for this:
>
> https://pypi.python.org/pypi/pyprimes
>
> If your prime generator performs better than, or worse than, all of those
> in the above module, I may have to steal it from you :-)

Ha, that's what I was hoping for. My algorithm outperforms several of
yours! Look!

Rosuav: 0.10868923284942639
awful_primes: 16.55546780386893
naive_primes1: 2.6105180965737276
naive_primes2: 1.358270674066116
trial_division: 0.06926075800136644
turner: 0.5736550315752424
croft: 0.007141969160883832
sieve: 0.01786707528470899
cookbook: 0.014790147909859996
wheel: 0.015050236831779529

Okay, so I outperform only algorithms listed as toys... :| Here's
similar figures, going to a higher cutoff (I kept it low for the sake
of awful_primes) and using only the algos designed for real use:

Rosuav: 2.1318494389650082
croft: 0.11628042111497416
sieve: 0.26868582459502566
cookbook: 0.21551174800149164
wheel: 0.4761577239565362

I didn't seriously think that this would outperform mathematically
proven and efficient algorithms, it was just a toy. But at least now I
know: It's roughly 20 times slower than a leading algo. And that's
after the bas-suggested improvement of using a heap.

But hey. If you want the code, you're welcome to it - same with anyone
else. Here's the heap version as used in the above timings. MIT
license.

def primes():
	"""Generate an infinite series of prime numbers."""
	from heapq import heappush,heappop
	i=2
	yield 2
	prime=[(2,2)] # Heap
	while True:
		smallest, prm = heappop(prime)
		heappush(prime, (smallest+prm, prm))
		if i<smallest:
			yield i
			heappush(prime, (i+i, i))
			i+=1
		if i==smallest: i+=1
# ----

Enjoy!

ChrisA

Thread

Prime number generator Chris Angelico <rosuav@gmail.com> - 2013-07-11 00:00 +1000
  Re: Prime number generator Bas <wegwerp@gmail.com> - 2013-07-10 07:35 -0700
    Re: Prime number generator Chris Angelico <rosuav@gmail.com> - 2013-07-11 01:12 +1000
      Re: Prime number generator bas <blswinkels@gmail.com> - 2013-07-10 08:47 -0700
        Re: Prime number generator Chris Angelico <rosuav@gmail.com> - 2013-07-11 02:15 +1000
        Re: Prime number generator Joshua Landau <joshua@landau.ws> - 2013-07-10 18:47 +0100
        Re: Prime number generator Ian Kelly <ian.g.kelly@gmail.com> - 2013-07-10 12:56 -0600
        Re: Prime number generator Joshua Landau <joshua@landau.ws> - 2013-07-10 20:06 +0100
      Re: Prime number generator bryanjugglercryptographer@yahoo.com - 2013-07-30 21:57 -0700
  Re: Prime number generator Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-07-10 16:01 +0000
    Re: Prime number generator Chris Angelico <rosuav@gmail.com> - 2013-07-11 02:52 +1000
  Re: Prime number generator albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-30 10:58 +0000
    Re: Prime number generator Ian Kelly <ian.g.kelly@gmail.com> - 2013-07-30 11:33 -0600

csiph-web