From: jzakiya Date: 2008-06-11T05:49:50+09:00 Subject: Re: Ultimate Prime Sieve -- Sieve of Zakiya (SoZ) On Jun 10, 2:31 am, Michael Ulm wrote: > jzakiya wrote: > > On Jun 9, 4:22 am, Michael Ulm 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 ------------------ >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. Hi Michael, Help me out here. By what basis do say "that eventually Atkins method must be quicker"? The test I've run in Ruby and Python with my different versions show they pull away from the SoA as N gets bigger. Why to you think the math I do is asymptotically bounded? Did you read that I took the SoA generator functions and implemented them with my methodology and beat the SoA by over a factor of 2. I'm limited to 1GB on my laptop, so I haven't been able to do Ns into the billions (yet) but people with 2-4 GB of memory should be able to test my routines up to those sizes of N. I'm really hoping that some people will ACTUALLY rigorously test my versions against the SoA, which is why I released my findings. But all my tests show my methodology, in its various specific implementations, is 'better' in many aspects, and not just speed. My method is shorter and easier to code (in any language), easier to understand, extensible to accommodate better generator functions, and inherently able to be done in parallel. In fact, my method SCREAMS to be done in parallel, which I emphasized repeatedly in my paper. If you have the capacity, please SHOW ME some benchmarks that prove the SoA is better than the various SoA versions beyond some point. Yeh, the primality tester I showed in my paper just fell out of the number theory I used to do the prime generators. I realized then it wasn't the best numerical method to test REALLY BIG numbers, but it was just so cool to demonstrate the conceptual brevity of reversing the process to generate primes to test numbers for being prime. I realized early that it was only practical for "normal" numbers, but for most people that's sufficient, and it's practical to do because it's short and easy to code and understand. I'm still thinking about ways to make numerically useful tests for large numbers using this number theory, so stay tuned. Jabari