Ultimate Prime Sieve -- Sieve Of Zakiya (SoZ)

[jzakiya]

On Jun 18, 7:58 pm, George Sakkis <george.sak... at gmail.com> wrote:
> On Jun 13, 1:12 pm, jzakiya <jzak... at gmail.com> wrote:
>
> > The paper presents benchmarks with Ruby 1.9.0-1 (YARV).  I would love
> > to see my variousprimegenerators benchmarked with optimized
> > implementations in other languages.  I'm hoping Python gurus will do
> > better than I, though the methodology is very very simple, since all I
> > do is additions, multiplications, and array reads/writes.
>
> After playing a little with it, I managed to get a 32-47% improvement
> on average for the pure Python version, and a 230-650% improvement
> with an extra "import psyco; psyco.full()" (pasted athttp://codepad.org/C2nQ8syr)
> The changes are:
>
> - Replaced range() with xrange()
> - Replaced x**2 with x*x
> - Replaced (a,b) = (c,d) with a=c; b=d
> - Replaced generator expressions with list comprehensions. This was
> the big one for letting psyco do its magic.
>
> I also tried adding type declarations and running it through Cython
> but the improvement was much less impressive than Psyco. I'm not a
> Pyrex/Cython expert though so I may have missed something obvious.
>
> George

George,

I took your code and included more efficient/optimized versions of
SoZ versions P3, P5, P7, and P11.

I ran the code on my PCLinuxOS, Intel P4, Python 2.4.3 system and
noted this. The SoZ code run much faster than the SoA in pure Python.
When psyco is used the SoA is significantly faster than the
pure Python version. The SoZ versions are faster too, but now
they are slower than the SoA. You can download the code from


http://www.4shared.com/dir/7467736/97bd7b71/sharing.html

It would be interesting to see how this code runs in newer versions
of Python (Psyco).

FYI, someone else coded P7 in C on a QuadCore Intel 9650 3.67GHz
overclocked cpu, using multiple threads, and got it to be faster
than the SoA, SoE, Here's some of his results (times in seconds).

Case      nPrime7x     nPrime7x     nPrime7x         nPrime7x
             Atkin     Zakiya      Eratosthenes     Zakiya (8 core
2.5ghz)

100 billion 52.58         44.27         50.56

200 b      110.14         92.38        108.99         88.01

300 b      169.81        140.92        167.47

400 b      232.34        190.84        228.08        177.72

500 b      297.44        241.84        291.28

600 b      364.84        293.92        355.27        273.04

700 b      434.33        346.97        420.41

800 b      506.67        400.97        486.72        373.29

900 b      579.58        456.53        555.09

1 trillion 654.03        513.11        624.00        479.22


Jabari