Sieve of Zakiya

[jzakiya]

On Nov 18, 5:01 am, Mark Dickinson <dicki... at gmail.com> wrote:
> On Nov 18, 7:53 am, jzakiya <jzak... at mail.com> wrote:
>
> >www.4shared.com/account/dir/7467736/97bd7b71/sharing
>
> From the introduction to the paper:
>
> "Thus began a process that culminated in my developing a new class
> of Number Theory Sieves (NTS) to generate prime numbers, and test
> primality of numbers, that use minimum memory, are simple to code,
> and are much faster than all previously known methods."
>
> That's quite a claim!  You might consider toning this down
> a little if you want to be taken seriously.  :-)
>
> How does your prime-generating algorithm stack up against
> Bernstein's primegen package?
>
> http://cr.yp.to/primegen.html
>
> Mark

Hi Mark,

Someone has done a multi-core C implementation (for AMD-X2 and Intel
quad and 8-core systems using Intel and GCC compilers) and the SoZ
prime generators are faster than the Sieve of Atkin (SoA) and Sieve of
Eratosthenes (SoE).

I think(?) he tried to run Bernstein's primegen, but its old code
written before multi-core and widely used 64-bit systems, so he wrote
his own multi-core/threaded version for his systems. The SoZs again,
are faster.

I've implemented the SoZ generators in Forth, Ruby, and Python, and
all show the same results, to be faster than the SoA and SoE in those
languages, along with C.

Now that I've corrected the Python code (I am NOT a native Python
programmer) it now beats the SoA implementation included in the code
using psyco too (for 2.4.3, I don't have it for other versions).

Run the code and see for yourself! :-)

I am writing another paper explaining some of the mathematical basis
for the SoZ, with complexity analysis, but I keep finding
"interesting" features about the underlying math, which I hope real
mathematicians will investigate and reveal what's going on here.
I want to release at least a first version before December.

But the proof is in the pudding, and the results speak for themselves.
It's an amazingly simple algorithm, so tear it apart.

Jabari