Sieve of Zakiya

[jzakiya]

Update: 2008/11/03

Architecture & coding improvements. Renamed generators.

I am 90% finished writing up a mathematical analysis of my method.
In the process I found an architectural optimization to the sieve
process which is incorporated in the new code. Complexity analysis
showing other interesting stuff for each generator.

When I finish I will post paper here with the code:

http://www.4shared.com/account/dir/7...bd7b71/sharing

Jabari

[jzakiya]

On Nov 4, 4:12*pm, jzakiya <[e-mail]:

Update: 2008/11/03

Architecture & coding improvements. Renamed generators.

I am 90% finished writing up a mathematical analysis of my method.
In the process I found an architectural optimization to the sieve
process which is incorporated in the new code. Complexity analysis
showing other interesting stuff for each generator.

When I finish I will post paper here with the code:

http://www.4shared.com/account/dir/7...bd7b71/sharing

Jabari

Another update to SoZ code.

Fixed coding "oversight" which caused the SoZ code running under psyco
to be slower than SoA, though SoZ was faster than SoA without psyco.
Now SoZ is consistently faster by an appreciable amount either way.

Some other coding enhancements to optimize algorithmic performance.

Enjoy! :-)

Jabari

[Mark Dickinson]

On Nov 18, 7:53*am, jzakiya <[e-mail]:

http://www.4shared.com/account/dir/7...bd7b71/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

[jzakiya]

On Nov 18, 5:01*am, Mark Dickinson <[e-mail]:

On Nov 18, 7:53*am, jzakiya <[e-mail]:

http://www.4shared.com/account/dir/7...bd7b71/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

[Mark Dickinson]

On Nov 19, 5:16*am, jzakiya <[e-mail]:
[Lots of stuff snipped]

My SoZ mathematical analysis shows why its algorithmically faster than
both the SoA & SoE, to explain its demonstrated computational
superiority. Again, hopefully professional mathematicians will become
interested in some of the features and characteristics I've found in
the method's elements, and do a better and more thorough analysis of
what's going on than I'm able to do presently.

This is getting off-topic for comp.lang.python. I suggest you
take it to sci.math.

Mark