jzakiya wrote:
> On Jun 9, 4:22 am, Michael Ulm <michael.... / isis-papyrus.com> wrote:
>> jzakiya wrote:
>>> This is to announce the release of my paper "Ultimate Prime Sieve --
>>> Sieve of Zakiiya (SoZ)" in which I show and explain the development of
>>> a class of Number Theory Sieves to generate prime numbers. I also use
>>> the number theory to then create the fastest, and deterministic,
>>> primality tester.  I used Ruby 1.9.0-1 as my development environment
>>> on a P4 2.8 Ghz laptop.
>>> You can get the pdf of my paper from here:
>>> http://www.4shared.com/dir/7467736/97bd7b71/sharing.html
>> --snip--
>>
>> Hi, just skimmed over your paper. Nice work, but you seem
>> somewhat overenthusiastic about it. Your sieve looks very
>> much like Wheel factorization to me.
>>
>> Also, your primality test is a lot slower than known methods
>> (like the AKS primality test which has been mentioned on this
>> list a few weeks ago).
>>
>> Keep your passion for Ruby and mathematics.
>>
>> Regards,
>>
>> Michael
> 
> Have you run all my coded examples?
> 
> Can you provide empirical results for other methods and their code?

Your implementation of the sieve is quite fast and for any ordinary range
it will be faster than Atkin. But understand, that eventually Atkins method
must be quicker due to its better asymptotic bound.

As an made up example, if your method takes  n  units of time to complete the
task and Atkins takes  3 * n / (log log n)  units of time for the same task,
then yours would be faster until n ~ 5300000000. So, for all practical n 
yours would be faster but Atkin would still be considered the 'faster'
algorithm asymptotically.

As for primality testing, understand, that people test primality of numbers
with 100+ digits. You don't get very far with such numbers using trial division.
I would have to dig up some of the algorithms I've lying around on my harddisk
for benchmarks, but until I find the time just look at what the simple
factor command does to the example you give in your paper (primality of the
product of the first 11 primes + 1)

time factor 200560490131
200560490131: 200560490131

real    0m0.006s
user    0m0.005s
sys     0m0.001s

i.e. the number is prime and it took this fairly old (~1 GHz Pentium) machine
5 milliseconds to figure out.

HTH,

Michael