From: jzakiya <jzakiya@...>
Date: 2008-11-25T07:35:49+09:00
Subject: Re: Sieve of Zakiya

On Nov 24, 3:35 pm, Lloyd Linklater <ll...@2live4.com> wrote:
> jzakiya wrote:
> > I've uploaded optimized upgraded versions of my SoZ prime generators,
> > with included benchmarks against the Sieve of Atkin (SoA) and Sieve of
> > Eratosthenes (SoE).  Available here:
>
> >http://www.4shared.com/dir/7467736/97bd7b71/sharing.html
>
> I looked at the code in there and it seemed awfully complex and
> difficult to follow.  I thought that the sieve was a simple algorithm.
> While I am at work and not able to hammer out the wrinkles, if you
> consider this as psuedo code, it should give you an idea of what I am
> thinking.  Wouldn't this be more straightforward?
>
> class findPrimes
>   def initialize(max_prime)
>     max_prime += 1 # for a 1 based array
>     @isa_prime = Array.new
>     max_prime.times  { |index| @isa_prime[index] = true }
>     @isa_prime[0] = false # never considered a prime number
>     @isa_prime[1] = false # never considered a prime number
>
>     flag_non_primes(2) # get all even numbers
>
>     # check only odd numbers.  If you find a prime one,
>     # flag its multiples
>     3.step(max_prime, 2) { |i| flag_non_primes(i) unless @isa_prime[i] =
> false }
>   end
>   def isa_prime
>     @isa_prime
>   end
>
>   #  You only need to start with the square of the number as everything
>   #  between is a multiple of something else.
>   #
>   #  You can skip every other multiple as it will be even.
>   def flag_non_primes(starting)
>     (starting * starting).step(max_prime, starting * 2) { |i|
> isa_prime[i] = false }
>   end
> end
>
> primes = findPrimes.new(10_000_001)
> --
> Posted viahttp://www.ruby-forum.com/.

Chuck,

Thanks for those times for JRuby 1.1.5.
They are comparable, though a bit slower, than I get on my PCLinuxOS
based Intel P4, 2.8 Ghz laptop with Ruby 1.9.0-1 and Ruby 1.9.1-
preview1 (which is a bit slower than 1.9.0-1). But I'm glad to see it
not only ran, but ran well with JRuby.

Hopefully Rubinius will be able to run it sometime soon too.

Lloyd,

Check out my Sieve of Zakiya paper I have on my 4shared site. It
explains what I'm doing.  All my SoZ generators have the same form,
they just get bigger and have more 'stuff' to take care of.

Look at the code to the generalized version: sozPn.

This is the compact version that can perform the generalized algorithm
for any prime generator from P3 thru P11. It will take as input the
prime numbers 3,5,7,11 or the modulus values 6, 110, and all the
multiples of 30 upto 210 (30, 60, 90, 120, 150, 180, 210).

To run bigger prime/modulus values you need to compute a different
class of, what I describe as, modulus complement pair (mcp) values,
which I show in my paper.  I actually can do sozPn(13) by feeding in
the mcp values for it, but I need more memory to do higher than this.

The method is really very simple and straightforward though.
I'm hoping to finish up another paper detailing the mathematical and
algorithmic features of the prime generators and algorithm before
December. When I do I'll make an announcement.

Jabari