Ultimate Prime Sieve -- Sieve of Zakiya (SoZ)

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/9...1/sharing.html

Below is a sample of one of the prime generators, and the primality
teste:

class Integer
def primesP3a
# all prime candidates > 3 are of form 6*k+1 and 6*k+5
# initialize sieve array with only these candidate values
# where sieve contains the odd integers representatives
# convert integers to array indices/vals by i=(n-3)>>1=(n>>1)-1
n1, n2 = -1, 1; lndx= (self-1) >>1; sieve = []
while n2 < lndx
n1 +=3; n2 += 3; sieve[n1] = n1; sieve[n2] = n2
end
#now initialize sieve array with (odd) primes < 6, resize array
sieve[0] =0; sieve[1]=1; sieve=sieve[0..lndx-1]

5.step(Math.sqrt(self).to_i, 2) do |i|
next unless sieve[(i>>1) - 1]
# p5= 5*i, k = 6*i, p7 = 7*i
# p1 = (5*i-3)>>1; p2 = (7*i-3)>>1; k = (6*i)>>1
i6 = 6*i; p1 = (i6-i-3)>>1; p2 = (i6+i-3)>>1; k = i6>>1
while p1 < lndx
sieve[p1] = nil; sieve[p2] = nil; p1 += k; p2 += k
end
end
return [2] if self < 3
[2]+([nil]+sieve).compact!.map {|i| (i<<1) +3 }
end

def primz?
# number theory based deterministic primality tester
n = self.abs
return true if [2, 3, 5].include? n
return false if n == 1 || n & 1 == 0
return false if n > 5 && ( ! [1, 5].include?(n%6) || n%5 == 0)

7.step(Math.sqrt(n).to_i,2) do |i|
# p5= 5*i, k = 6*i, p7 = 7*i
p1 = 5*i; k = p1+i; p2 = k+i
return false if [(n-p1)%k , (n-p2)%k].include? 0
end
return true
end
end

Now to generate an array of the primes up to N do this in Ruby:

1000001.primesP3a

To check the primality of any integer just do: 13328237.primz?

The paper presents benchmarks with Ruby 1.9.0-1 (YARV).
I would love to see the various prime generators benchmarked
with other languages. I would also like to see at least the primality
tester make it into the standard library, since its so short,
elegant,
and good.

I've finally just finished writing this up, and now I'm releasing it
into
the wild. I didn't haven't done Forth versions yet, but people should
be able to create them from the code in my paper, and the
explanations.

Of course, questions and feedback is welcomed.

Well, may the Forth be with you. :-)

Jabari Zakiya

On Jun 7, 11:12 pm, jzakiya <jzak...@mail.com> 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/9...1/sharing.html
>
> Below is a sample of one of the prime generators, and the primality
> teste:
>
> class Integer
> def primesP3a
> # all prime candidates > 3 are of form 6*k+1 and 6*k+5
> # initialize sieve array with only these candidate values
> # where sieve contains the odd integers representatives
> # convert integers to array indices/vals by i=(n-3)>>1=(n>>1)-1
> n1, n2 = -1, 1; lndx= (self-1) >>1; sieve = []
> while n2 < lndx
> n1 +=3; n2 += 3; sieve[n1] = n1; sieve[n2] = n2
> end
> #now initialize sieve array with (odd) primes < 6, resize array
> sieve[0] =0; sieve[1]=1; sieve=sieve[0..lndx-1]
>
> 5.step(Math.sqrt(self).to_i, 2) do |i|
> next unless sieve[(i>>1) - 1]
> # p5= 5*i, k = 6*i, p7 = 7*i
> # p1 = (5*i-3)>>1; p2 = (7*i-3)>>1; k = (6*i)>>1
> i6 = 6*i; p1 = (i6-i-3)>>1; p2 = (i6+i-3)>>1; k = i6>>1
> while p1 < lndx
> sieve[p1] = nil; sieve[p2] = nil; p1 += k; p2 += k
> end
> end
> return [2] if self < 3
> [2]+([nil]+sieve).compact!.map {|i| (i<<1) +3 }
> end
>
> def primz?
> # number theory based deterministic primality tester
> n = self.abs
> return true if [2, 3, 5].include? n
> return false if n == 1 || n & 1 == 0
> return false if n > 5 && ( ! [1, 5].include?(n%6) || n%5 == 0)
>
> 7.step(Math.sqrt(n).to_i,2) do |i|
> # p5= 5*i, k = 6*i, p7 = 7*i
> p1 = 5*i; k = p1+i; p2 = k+i
> return false if [(n-p1)%k , (n-p2)%k].include? 0
> end
> return true
> end
> end
>
> Now to generate an array of the primes up to N do this in Ruby:
>
> 1000001.primesP3a
>
> To check the primality of any integer just do: 13328237.primz?
>
> The paper presents benchmarks with Ruby 1.9.0-1 (YARV).
> I would love to see the various prime generators benchmarked
> with other languages. I would also like to see at least the primality
> tester make it into the standard library, since its so short,
> elegant,
> and good.
>
> I've finally just finished writing this up, and now I'm releasing it
> into
> the wild. I didn't haven't done Forth versions yet, but people should
> be able to create them from the code in my paper, and the
> explanations.
>
> Of course, questions and feedback is welcomed.
>
> Well, may the Forth be with you. :-)
>
> Jabari Zakiya

The code from the paper can be seen here:

http://snippets.dzone.com/posts/show/5610

jzakiya <jzakiya@mail.com> writes Re: Ultimate Prime Sieve -- Sieve of Zakiya (SoZ)
[..]
> 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.
[..]
> The paper presents benchmarks with Ruby 1.9.0-1 (YARV).
> I would love to see the various prime generators benchmarked
> with other languages.

What would the benchmark look like?

Example: (3 GHz PIV)

FORTH> timer-reset S" 18446744073709551617" cr .FACTOR cr .elapsed
274177 * 67280421310721
0.028 seconds elapsed. ok

FORTH> timer-reset S" 1844674407370955161718446744073709551611" cr .FACTOR cr .elapsed
661 * 25589 * 109059863230220670398361456967859
0.024 seconds elapsed. ok

etc.

-marcel

On Jun 8, 2:08 am, m...@iae.nl (Marcel Hendrix) wrote:
> jzakiya <jzak...@mail.com> writes Re: Ultimate Prime Sieve -- Sieve of Zakiya (SoZ)
> [..]
>
> > 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.
> [..]
> > The paper presents benchmarks with Ruby 1.9.0-1 (YARV).
> > I would love to see the various prime generators benchmarked
> > with other languages.
>
> What would the benchmark look like?
>
> Example: (3 GHz PIV)
>
> FORTH> timer-reset S" 18446744073709551617" cr .FACTOR cr .elapsed
> 274177 * 67280421310721
> 0.028 seconds elapsed. ok
>
> FORTH> timer-reset S" 1844674407370955161718446744073709551611" cr .FACTOR cr .elapsed
> 661 * 25589 * 109059863230220670398361456967859
> 0.024 seconds elapsed. ok
>
> etc.
>
> -marcel

I haven't done Forth versions yet, but I put the code out there so
others can start translating
them. I've also uploaded the Ruby and Python code from the paper it
my site which has the pdf
so people can download those too. When I do Forth versions they will
go there also.

The benchmarks for the generators would be the various N values for
the different versions.

10000001 primesP3a
10000001 primesP5a
etc

I also ran out of memory on my laptop, so I couldn't use my primality
tester for REALLY big
numbers. But for a 64-bit processor you can represent in one cell some
stupid BIG NUMS!

In fact, the first routine I will do in Forth is my primality tester,
primz?

Jabari

On 8 Jun., 08:08, m...@iae.nl (Marcel Hendrix) wrote:
..
> Example: *(3 GHz PIV)
>
> FORTH> timer-reset S" 18446744073709551617" cr .FACTOR cr .elapsed
> 274177 * 67280421310721
> 0.028 seconds elapsed. ok

May be I missed your TIMER-RESET and .ELAPSED words earlyer - looks
great.

Is there a gforth version around?
Michael

On Jun 8, 6:41 pm, Michael <michael.ka...@onlinehome.de> wrote:
> On 8 Jun., 08:08, m...@iae.nl (Marcel Hendrix) wrote:
> ..
>
> > Example: (3 GHz PIV)
>
> > FORTH> timer-reset S" 18446744073709551617" cr .FACTOR cr .elapsed
> > 274177 * 67280421310721
> > 0.028 seconds elapsed. ok
>
> May be I missed your TIMER-RESET and .ELAPSED words earlyer - looks
> great.
>
> Is there a gforth version around?
> Michael

Below is Forth code to perform the Sieve of Zakiya (SoZ).
This code is a direct translation of a few of the sieves
in my paper, "Ultimate Prime Sieve -- Sieve of Zakiya."
The pdf of the paper, and this source code (with others)
is available to download from this site:

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

This code was developed and tested on gforth on Linux.
Hardware system: Intel P4 2.8 Ghz, 1 GB, laptop

Please test/benchmark to your hearts contents, and post results.
(I have to find the gforth benchmarking words again)

On gforth, I was only able to use arrays up to ~8 meg.
Is there some way I can raise this limit to do bigger numbers?

In fact, I would like to do a BIGNUMBER version in Forth, but
the easiest way I could think of to do that is to use Floats.
Any suggestions (translations) to do that are welcomed.

I want to benchmark my versions with N =100,000,000,000 to compare.
it to a C version that is purported to do it in 60 secs on a 3 Ghz P4.

See the 4th post do from comp.lang.c here
http://groups.google.com/group/comp....d0ea5a77a0723#

which sites this: www.primzahlen.de/files/referent/kw/sieb.htm

Question, comments, suggestions always welcomed

Jabari
------------------------------------------------------

: array create here over erase allot does> swap + ;
: sqrt ( n - n) 0 d>f fsqrt f>d drop ;

0 value num
8000007 to num \ set number to find primes upto
num 1- 2/ value lndx \ max index for sieve array
lndx 105 + array sieve \ 105 will allow sieve for modulus <= 210

\ nprimes - show number of primes found, .primes - display prime
values
: nprimes ( - n) 1 ( for 2) lndx 0 do I sieve c@ if 1+ then loop . ;
: .primes ." 2 " lndx 0 do I sieve c@ if I 2* 3 + . then loop ;

0 value n1 0 value n2 0 value x1 0 value p1 0 value p2

: primesP3a ( N - )
\ all prime candidates > 3 are of the form 6*x+1 and 6*x+5
\ initialize sieve array with only these candidate values
\ where byte array indices for sieve are odd integers
representations
\ convert integers to array indices/vals by i = (n-3)>>1 = (n>>1)-1

to num -1 to n1 1 to n2
begin n2 lndx < while
3 n1 + to n1 3 n2 + to n2 1 n1 sieve c! 1 n2 sieve c!
repeat
\ now initialize sieve array with (odd) primes < 6
1 0 sieve c! 1 1 sieve c!

num sqrt 1+ 5 do
I 2/ 1- sieve c@ if
\ p1= 5*i, x = 6*i, p2 = 7*i
\ p1 = (5*i-3)>>1; p2 = (7*i-3)>>1; x1 = (6*i)>>1
I dup 6 * dup 2/ to x1 dup I - 2/ 1- to p1 + 2/ 1- to p2
begin p2 lndx < while
0 dup p1 sieve c! p2 sieve c! x1 dup p1 + to p1 p2 + to
p2
repeat
p1 lndx < if 0 p1 sieve c! then
then
2 +loop
;

0 value n3 0 value n4 0 value n5 0 value n6 0 value n7 0 value
n8
0 value p3 0 value p4 0 value p5 0 value p6 0 value p7 0 value
p8

: primesP5a ( N - )
\ prime candidates > 3 are of the form 30*x+(1,7,11,13,17,19,23,29)
\ initialize sieve array with only these candidate values
\ where byte array indices for sieve are odd integers
representations
\ convert integers to array indices/vals by i = (n-3)>>1 = (n>>1)-1

to num
-1 to n1 2 to n2 4 to n3 5 to n4 7 to n5 8 to n6 10 to n7 13 to n8
begin n8 lndx < while
15 n1 + to n1 15 n2 + to n2 15 n3 + to n3 15 n4 + to n4
15 n5 + to n5 15 n6 + to n6 15 n7 + to n7 15 n8 + to n8
1 n1 sieve c! 1 n2 sieve c! 1 n3 sieve c! 1 n4 sieve c!
1 n5 sieve c! 1 n6 sieve c! 1 n7 sieve c! 1 n8 sieve c!
repeat
\ now initialize sieve array with (odd) primes < 30
1 0 sieve c! 1 1 sieve c! 1 2 sieve c! 1 4 sieve c! 1 5 sieve c!
1 7 sieve c! 1 8 sieve c! 1 10 sieve c! 1 13 sieve c!

num sqrt 1+ 7 do
I 2/ 1- sieve c@ if
\ p1=7*i, p2=11*i, p3=13*i --- p7=29*i, p8=31*i, x=30*i
\ maps to: p1= (7*i-3)>>1, --- p8=(31*i-3)>>1, x1=30*i>>1
I 7 * 2/ 1- to p1 I 11 * 2/ 1- to p2 I 13 * 2/ 1- to p3
I 17 * 2/ 1- to p4 I 19 * 2/ 1- to p5 I 23 * 2/ 1- to p6
I 29 * 2/ 1- to p7 I 31 * 2/ 1- to p8 I 30 * 2/ to x1
begin p8 lndx < while
0 p1 sieve c! 0 p2 sieve c! 0 p3 sieve c! 0 p4 sieve c!
0 p5 sieve c! 0 p6 sieve c! 0 p7 sieve c! 0 p8 sieve c!
x1 p1 + to p1 x1 p2 + to p2 x1 p3 + to p3 x1 p4 + to p4
x1 p5 + to p5 x1 p6 + to p6 x1 p7 + to p7 x1 p8 + to p8
repeat
p1 lndx < if 0 p1 sieve c! then p2 lndx < if 0 p2 sieve c!
then
p3 lndx < if 0 p3 sieve c! then p4 lndx < if 0 p4 sieve c!
then
p5 lndx < if 0 p5 sieve c! then p6 lndx < if 0 p6 sieve c!
then
p7 lndx < if 0 p7 sieve c! then
then
2 +loop
;

0 value q1 0 value q2 0 value x2

: primz? ( n - ?)
abs dup to num
\ return true if n is 2, 3, or 5
dup >r 2 = r@ 3 = or r@ 5 = or if r> drop true exit then

\ return false if n == 1 OR n is even
r@ 1 = r@ 1 and 0= or if r> drop false exit then

\ return false if n > 5 AND ( n mod 6 != [1,5] OR n mod 5 = 0)
r@ 5 mod 0= r@ 6 mod dup 1 = swap 5 = or invert or r@ 5 > and
if r> drop false exit then

7 to n1 11 to n2
r> sqrt 1+ \ sqrt(n)
begin n1 over < while \ do while n1 <= sqrt N
\ p1= 5*i, x = 6*i, p2 = 7*i
\ p1 = 5*n1; x1 = p1+n1; p2 = x1+n1
\ q1 = 5*n2; x2 = q1+n2; q2 = x2+n2
n1 dup 5 * dup to p1 over + dup to x1 + to p2
n2 dup 5 * dup to q1 over + dup to x2 + to q2
\ non-prime if (n-p1)%x1,(n-p2)%x1,(n-q1)%x2,(n-q2)%x2 = 0
num p1 - x1 mod 0= num p2 - x1 mod 0=
num q1 - x2 mod 0= num q2 - x2 mod 0= or or or
if drop false exit then
6 n1 + to n1 6 n2 + to n2
repeat
drop true
;

: prime? primz? if ." true" else ." false" then ;

On Jun 16, 9:24*pm, jzakiya <jzak...@mail.com> wrote:
> On Jun 8, 6:41 pm, Michael <michael.ka...@onlinehome.de> wrote:
>
> > On 8 Jun., 08:08, m...@iae.nl (Marcel Hendrix) wrote:
> > ..
>
> > > Example: *(3 GHz PIV)
>
> > > FORTH> timer-reset S" 18446744073709551617" cr .FACTOR cr .elapsed
> > > 274177 * 67280421310721
> > > 0.028 seconds elapsed. ok
>
> > May be I missed your TIMER-RESET and .ELAPSED words earlyer - looks
> > great.
>
> > Is there a gforth version around?
> > Michael
>
> Below is Forth code to perform theSieveof Zakiya (SoZ).
> This code is a direct translation of a few of the sieves
> in my paper, "UltimatePrimeSieve--Sieveof Zakiya."
> The pdf of the paper, and this source code (with others)
> is available to download from this site:
>
> http://www.4shared.com/account/dir/7...bd7b71/sharing
>
> This code was developed and tested on gforth on Linux.
> Hardware system: Intel P4 2.8 Ghz, 1 GB, laptop
>
> Please test/benchmark to your hearts contents, and post results.
> (I have to find the gforth benchmarking words again)
>
> On gforth, I was only able to use arrays up to ~8 meg.
> Is there some way I can raise this limit to do bigger numbers?
>
> In fact, I would like to do a BIGNUMBER version in Forth, but
> the easiest way I could think of to do that is to use Floats.
> Any suggestions (translations) to do that are welcomed.
>
> I want to benchmark my versions with N =100,000,000,000 to compare.
> it to a C version that is purported to do it in 60 secs on a 3 Ghz P4.
>
> See the 4th post do from comp.lang.c *herehttp://groups.google.com/group/comp.lang.c/browse_thread/thread/138d0...
>
> which sites this:www.primzahlen.de/files/referent/kw/sieb.htm
>
> Question, comments, suggestions always welcomed
>
> Jabari
> ------------------------------------------------------
>
> : array create *here over erase *allot *does> swap + ;
> : sqrt ( n - n) *0 d>f fsqrt f>d drop ;
>
> * *0 value num
> * *8000007 to num * * * * \ set number to find primes upto
> * *num 1- 2/ value lndx * \ max index forsievearray
> * *lndx 105 + arraysieve\ 105 will allowsievefor modulus <= 210
>
> \ nprimes - show number of primes found, .primes - displayprime
> values
> : nprimes ( - n) 1 ( for 2) lndx 0 do Isievec@ if 1+ then loop . ;
> : .primes ." 2 " lndx 0 do Isievec@ if I 2* 3 + . then loop ;
>
> * 0 value n1 *0 value n2 *0 value x1 *0 value p1 *0 value p2
>
> : primesP3a ( N - )
> * \ allprimecandidates > 3 are of the form 6*x+1 and 6*x+5
> * \ initializesievearray with only these candidate values
> * \ where byte array indices forsieveare odd integers
> representations
> * \ convert integers to array indices/vals by *i = (n-3)>>1 = (n>>1)-1
>
> * *to num * -1 to n1 * 1 to n2
> * *begin n2 lndx < while
> * * * 3 n1 + to n1 * 3 n2 + to n2 * 1 n1sievec! * 1 n2sievec!
> * *repeat
> * *\ now initializesievearray with (odd) primes < 6
> * *1 0sievec! * 1 1sievec!
>
> * *num sqrt 1+ 5 do
> * * * *I 2/ 1-sievec@ if
> * * * * * \ p1= 5*i, *x = 6*i, *p2 = 7*i
> * * * * * \ p1 = (5*i-3)>>1; *p2 = (7*i-3)>>1; *x1 = (6*i)>>1
> * * * * * I dup 6 * dup 2/ to x1 dup I - 2/ 1- to *p1 + 2/ 1-to p2
> * * * * * begin p2 lndx < while
> * * * * * * *0 dup p1sievec! p2sievec! x1 dup p1 + to p1 p2+ to
> p2
> * * * * * repeat
> * * * * * p1 lndx < if 0 p1sievec! then
> * * * *then
> * *2 +loop
> ;
>
> *0 value n3 *0 value n4 *0 value n5 *0 value n6 *0 value n7 *0 value
> n8
> *0 value p3 *0 value p4 *0 value p5 *0 value p6 *0 value p7 *0 value
> p8
>
> : primesP5a ( N - )
> * \primecandidates > 3 are of the form 30*x+(1,7,11,13,17,19,23,29)
> * \ initializesievearray with only these candidate values
> * \ where byte array indices forsieveare odd integers
> representations
> * \ convert integers to array indices/vals by i = (n-3)>>1 = (n>>1)-1
>
> * *to num
> * *-1 to n1 2 to n2 4 to n3 5 to n4 7 to n5 8 to n6 10 to n7 13 to n8
> * *begin n8 lndx < while
> * * * 15 n1 + to n1 * 15 n2 + to n2 * 15 n3 + to n3 *15 n4 + to n4
> * * * 15 n5 + to n5 * 15 n6 + to n6 * 15 n7 + to n7 *15 n8 + to n8
> * * * 1 n1sievec! * 1 n2sievec! * 1 n3sievec! *1 n4sievec!
> * * * 1 n5sievec! * 1 n6sievec! * 1 n7sievec! *1 n8sievec!
> * *repeat
> * *\ now initializesievearray with (odd) primes < 30
> * *1 0sievec! 1 1sievec! 1 2 *sievec! 1 4 *sievec! 1 5sievec!
> * *1 7sievec! 1 8sievec! 1 10sievec! 1 13sievec!
>
> * *num sqrt 1+ 7 do
> * * *I 2/ 1-sievec@ if
> * * * *\ p1=7*i, p2=11*i, p3=13*i --- p7=29*i, p8=31*i,*x=30*i
> * * * *\ maps to: p1= (7*i-3)>>1, --- p8=(31*i-3)>>1, x1=30*i>>1
> * * * *I *7 * 2/ 1- to p1 *I 11 * 2/ 1- to p2 *I 13 * 2/ 1-to p3
> * * * *I 17 * 2/ 1- to p4 *I 19 * 2/ 1- to p5 *I 23 * 2/ 1- to p6
> * * * *I 29 * 2/ 1- to p7 *I 31 * 2/ 1- to p8 *I 30 * 2/ to x1
> * * * *begin p8 lndx < while
> * * * * * 0 p1sievec! *0 p2sievec! *0 p3sievec! *0 p4sievec!
> * * * * * 0 p5sievec! *0 p6sievec! *0 p7sievec! *0 p8sievec!
> * * * * * x1 p1 + to p1 *x1 p2 + to p2 *x1 p3 + to p3 *x1p4 + to p4
> * * * * * x1 p5 + to p5 *x1 p6 + to p6 *x1 p7 + to p7 *x1p8 + to p8
> * * * *repeat
> * * * *p1 lndx < if 0 p1sievec! then *p2 lndx < if 0 p2sievec!
> then
> * * * *p3 lndx < if 0 p3sievec! then *p4 lndx < if 0 p4sievec!
> then
> * * * *p5 lndx < if 0 p5sievec! then *p6 lndx < if 0 p6sievec!
> then
> * * * *p7 lndx < if 0 p7sievec! then
> * * *then
> * *2 +loop
> ;
>
> * *0 value q1 *0 value q2 *0 value x2
>
> : primz? ( n - ?)
> * * * abs dup to num
> * * * \ return true *if n is 2, 3, or 5
> * * * dup >r 2 = r@ 3 = or r@ 5 = or if r> drop true exit then
>
> * * * \ return false if n == 1 OR n is even
> * * * r@ 1 = r@ 1 and 0= or if r> drop false exit then
>
> * * * \ return false if n > 5 AND ( n mod 6 != [1,5] OR n mod 5 = 0)
> * * * r@ 5 mod 0= *r@ 6 mod dup 1 = swap 5 = or invert or r@ 5 > and
> * * * if r> drop false exit then
>
> * * * 7 to n1 *11 to n2
> * * * r> sqrt 1+ * * * * * * *\ sqrt(n)
> * * * begin n1 over < while * \ do while *n1 <= sqrt N
> * * * * *\ p1= 5*i, *x = 6*i, *p2 = 7*i
> * * * * *\ p1 = 5*n1; *x1 = p1+n1; *p2 = x1+n1
> * * * * *\ q1 = 5*n2; *x2 = q1+n2; *q2 = x2+n2
> * * * * *n1 dup 5 * dup to p1 over + dup to x1 + to p2
> * * * * *n2 dup 5 * dup to q1 over + dup to x2 + to q2
> * * * * *\ non-primeif (n-p1)%x1,(n-p2)%x1,(n-q1)%x2,(n-q2)%x2 = 0
> * * * * *num p1 - x1 mod 0= * num p2 - x1 mod 0=
> * * * * *num q1 - x2 mod 0= * num q2 - x2 mod 0= or or or
> * * * * *if drop false exit then
> * * * * *6 n1 + to n1 * 6 n2 + to n2
> * * * repeat
> * * * drop true
> ;
>
> rime? *primz? if ." true" else ." false" then ;

I've uploaded more efficient/faster code:

http://www.4shared.com/dir/7467736/9...1/sharing.html

Jabari

jzakiya <jzakiya@mail.com> writes Re: Ultimate Prime Sieve -- Sieve of Zakiya (SoZ)

> On Jun 16, 9:24=A0pm, jzakiya <jzak...@mail.com> wrote:
>> On Jun 8, 6:41 pm, Michael <michael.ka...@onlinehome.de> wrote:

> I've uploaded more efficient/faster code:

> http://www.4shared.com/dir/7467736/9...1/sharing.html

I had some problems understanding what (or better *why*) your code
tried to do things.

The way a prime sieve gets used, e.g. in the Euler Project, I normally
allocate a 1 megabyte array, initialize it with boolean flags (true:
the value corresponding with this index is a prime, where the integer
to index code is "3 - 1 rshift"), and then use this boolean
array for the rest of the program. The setting up time of the Sieve is
truly insignificant compared to the run-time of the actual code that
uses the Sieve to determine if a given integer is prime.

(Of course, I uses Albert's van der Horst benchpin code to do the real
searching, the sieve array is only to weed out the common candidates.
If benchpin is not used, the Sieve might need to be hundredths of
megabytes in size for Euler Project programs.)

An interesting improvement in this area would be when many more (than
currently done) prime booleans could be compressed into the allocated
array. Or in other words: a better compressor than the standard
: int->index 3 - 1 rshift ; .

However, this is not what your code does.

I did not really understand why you called it the 'Ultimate' prime sieve.
It will be faster to store precomputed boolean flags in a diskfile and
read them with mmap. Of course, one would only do that when the prime
setup time was limiting the run time of the actual code (?) or when the
size of the array is larger than what can be conveniently allocated. Your
code ALLOTs an array, which for common Forths limits the Sieve size to
some 64 MByte (tiny compared to main memory or disk space).

After these deliberations I tried to run your code. As the point (probably)
is to compare the Sieve setup time of primesP3, primesP4 and primesP7,
I came up with a test rig which sets the sieve to its maximum size (num
and lndx), erases it, and then runs the words. To have a basic reference,
I timed the way benchpin initializes its Sieve (453 ms). Furthermore,
I tested the speed of your base word primz? which finds primes without
using the sieve, and of the word primz2? which one would normally use
to access the Sieve in practice as

: primz2? ( test# -- bool ) 3 - 1 rshift sieve c@ ;

Here are the results for iForth32 on a 3 GHz Intel PIV

FORTH> test ( iForth32, 3 GHz Intel PIV, XP, 1 GN memory )
Setup time for benchpin is 0.453 seconds (2000003 boolean flags)
10 * primesP3 : 0.329 seconds elapsed. (148934 primes in sieve)
10 * primesP5 : 0.259 seconds elapsed. (148934 primes in sieve)
10 * primesP7 : 0.236 seconds elapsed. (148934 primes in sieve)
10M * primz2? : 0.013 seconds elapsed.
10M * primz? : 2.086 seconds elapsed. ok

The speedup going from primesP3 through primesP5 to primesP7 is not
dramatic, so I'd say that primesP3 is a nice balance between size,
speed and complexity :-)

I hope I understood the point of your work correctly.

-marcel

In article <86283821153559@frunobulax.edu>, Marcel Hendrix <mhx@iae.nl> wrote:
>jzakiya <jzakiya@mail.com> writes Re: Ultimate Prime Sieve -- Sieve of Zakiya (SoZ)

<SNIP>

>
>(Of course, I uses Albert's van der Horst benchpin code to do the real
>searching, the sieve array is only to weed out the common candidates.
>If benchpin is not used, the Sieve might need to be hundredths of
>megabytes in size for Euler Project programs.)

A remark: the benchpin program doesn't use a sieve at all!
It is an example of a recursive program that calculates something
useful, and at the same time of prime counting without using
a sieve, or for that matter any storage outside of the stacks.

I would paraphraze this as: "I use the techniques of Mentzel,
that I learned from the benchpin code."

The world record for prime counting is above 10^22. This is totally
out of reach for simple sieving.

>
>An interesting improvement in this area would be when many more (than
>currently done) prime booleans could be compressed into the allocated
>array. Or in other words: a better compressor than the standard
>: int->index 3 - 1 rshift ; .

Interesting, for 16 bit processors with limited address range.
A very long time ago, in the CP/M age before MSDOS, I made a sieve
with 30 numbers per byte. It is still there, as an example in
ciforth. (If you have lina/wina/mina
``REQUIRE SIEVE REQUIRE LOCATE LOCATE SIEVE'' )
Or you can just look up SIEVE in forth.lab, it is an ordinary
text file.
Nowadays, such programs are interesting, but make little sense.

>
>However, this is not what your code does.
>
>I did not really understand why you called it the 'Ultimate' prime sieve.
>It will be faster to store precomputed boolean flags in a diskfile and
>read them with mmap. Of course, one would only do that when the prime
>setup time was limiting the run time of the actual code (?) or when the
>size of the array is larger than what can be conveniently allocated. Your
>code ALLOTs an array, which for common Forths limits the Sieve size to
>some 64 MByte (tiny compared to main memory or disk space).
>
>After these deliberations I tried to run your code. As the point (probably)
>is to compare the Sieve setup time of primesP3, primesP4 and primesP7,
>I came up with a test rig which sets the sieve to its maximum size (num
>and lndx), erases it, and then runs the words. To have a basic reference,
>I timed the way benchpin initializes its Sieve (453 ms). Furthermore,

There is no sieve in benchpin. So what?
http://home.hccnet.nl/a.w.m.van.der.horst/benchpin.frt
Where this program is intended to be a benchmark, I object to
versions floating around that are different without notice.
If you don't intend to use the code as a benchmark for recursion, the
name "benchpin" doesn't make sense anyway.

>I tested the speed of your base word primz? which finds primes without
>using the sieve, and of the word primz2? which one would normally use
>to access the Sieve in practice as
>
> : primz2? ( test# -- bool ) 3 - 1 rshift sieve c@ ;
>
>Here are the results for iForth32 on a 3 GHz Intel PIV
>
>FORTH> test ( iForth32, 3 GHz Intel PIV, XP, 1 GN memory )
>Setup time for benchpin is 0.453 seconds (2000003 boolean flags)
>10 * primesP3 : 0.329 seconds elapsed. (148934 primes in sieve)
>10 * primesP5 : 0.259 seconds elapsed. (148934 primes in sieve)
>10 * primesP7 : 0.236 seconds elapsed. (148934 primes in sieve)
>10M * primz2? : 0.013 seconds elapsed.
>10M * primz? : 2.086 seconds elapsed. ok
>
>The speedup going from primesP3 through primesP5 to primesP7 is not
>dramatic, so I'd say that primesP3 is a nice balance between size,
>speed and complexity :-)
>
>I hope I understood the point of your work correctly.
>
>-marcel
>


--
--
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- like all pyramid schemes -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

Marcel

I hope this answers your questions.

>I had some problems understanding what (or better *why*) your code
>tried to do things.

>The way a prime sieve gets used, e.g. in the Euler Project, I normally
>allocate a 1 megabyte array, initialize it with boolean flags (true:
>the value corresponding with this index is a prime, where the integer
>to index code is "3 - 1 rshift"), and then use this boolean
>array for the rest of the program. The setting up time of the Sieve is
>truly insignificant compared to the run-time of the actual code that
>uses the Sieve to determine if a given integer is prime.

>(Of course, I uses Albert's van der Horst benchpin code to do the real
>searching, the sieve array is only to weed out the common candidates.
>If benchpin is not used, the Sieve might need to be hundredths of
>megabytes in size for Euler Project programs.)

The Forth versions also set up a boolean SIEVE array set to FALSE.
Then for each prime generator (P3,P5,P7, etc) it sets to non-FALSE
only potential prime candidates, and the initial set of seed primes.
Fewer prime candidates are selected as the prime generators get
bigger, thus they are more efficient at selecting primes for large N.

>An interesting improvement in this area would be when many more (than
>currently done) prime booleans could be compressed into the allocated
>array. Or in other words: a better compressor than the standard
>: int->index 3 - 1 rshift ; .

>However, this is not what your code does.

If memory use efficiency is more important than speed you can do this.
The modulus value tells you the span of numbers examined by each pass
of the prime generators, and the residue values tells you the specific
values that can possibly be prime over that span.

So for P5=30*k+(1,7,11,13,17,19,23,29) for each pass (k=0,1,2,3..n) up
to N 30 is added to (1,..29) each pass (0,30,60,90..), to identify
possible primes. These 30*k residue values can be a bit of a byte of
memory (lsb low value) starting at k=1 (k=0 gives you the residue,
which you don't have to store).
byte01 = 59,53,49,47,43,41,37,31 would be 1101111, (49 not prime)
byte02 = 89,83,79,77,73,71,67,61 would be 1110111, (77 not prime)
........ etc

For larger Pn's you'd get greater compression. P11 has a modulus of
2310 and 480 residues. The 480 residues generate 480 possible primes
for each span of 2310 numbers. Thus, you would need only 480/8 = 60
bytes to represent the primes over each span of 2310. So you would
need only about 60*(N/2310) bytes of memory to store prime
representatives up to a value of N.

>I did not really understand why you called it the 'Ultimate' prime sieve.
>It will be faster to store precomputed boolean flags in a diskfile and
>read them with mmap. Of course, one would only do that when the prime
>setup time was limiting the run time of the actual code (?) or when the
>size of the array is larger than what can be conveniently allocated. Your
>code ALLOTs an array, which for common Forths limits the Sieve size to
>some 64 MByte (tiny compared to main memory or disk space).

The word "Ultimate" was an inside joke to myself, and a hyperbalistic
way to get people to scrutinize my math/methodology. As I said in my
paper, I started this because I was looking at ways to generate primes
to solve Project Euler problems. In my search for code I found ways to
do the Sieve of Eratosthenes, then the Sieve of Atkin, and wheel
sieves. So when I came up with my sieving
methodology (as compared to non-sieving approaches) I labeled it as
the "ultimate" prime sieve as a way of saying "here's another one" and
to draw attention to it. BUT, mathematically, the generators I've
identified, and the process to identify additional generators of my
form, CAN produce actual implementations that generate primes faster
than what now exists, especially when implemented in a parallel. So in
that sense they could be "ultimate" too.

>After these deliberations I tried to run your code. As the point (probably)
>is to compare the Sieve setup time of primesP3, primesP4 and primesP7,
>I came up with a test rig which sets the sieve to its maximum size (num
>and lndx), erases it, and then runs the words. To have a basic reference,

Thanks for benchmarking my code. I've found Forth restricts the use
of my method because I can't do really big arrays (gforth lets me have
an array up to about 8 million, other forths much lower). Other
languages let you get into the billions, and even trillions, for array
sizes much easier.

>I timed the way benchpin initializes its Sieve (453 ms). Furthermore,
>I tested the speed of your base word primz? which finds primes without
>using the sieve, and of the word primz2? which one would normally use
>to access the Sieve in practice as

As Albert has stated, benchpin isn't a sieve, and doesn't generate the
primes (though it can be modified to to so), it only counts them up to
N. primz? is a proof-of-concept implementation of a deterministic
primality tester I did to show how the reverse prime generation
methodology can be used to check numbers for primality. It is NOT the
fastest general purpose way to deterministically check for primality,
though it is deterministic.

FYI, here are the most current timings from someone who is
benchmarking my methods against the Sieve of Eratoshenes/Atkin. He's
using an overclocked 3.67 GHz Intel quadcore 9650 system, coding in C.
Times are in seconds.

Case nPrime7x nPrime7x nPrime7x
Atkin Zakiya Erat.

1 trillion 459.97 462.58 527.03

2 trillion 943.66 951.47 1065.09

3 trillion 1465.52 1496.38 1636.63

So, he's got the Sieve of Atkin and my P7 generator able to generate
all the primes up to N=1,000,000,000,000 (1 Trillion) in about 7 min,
40 secs. Impressive!!

>I hope I understood the point of your work correctly.

>-marcel

I hope this helps to explain my work more clearly. ;-)

Jabari

PS: Albert, I've run your benchpin.f code, as is, on 6 different
forths. For straight Linux, it runs on gforth, pfe, and kforth, and
using wine on Linux, it runs on Swiftforth, MPE, and Win32Forth.