Sieve of Zakiya


#1

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:

Versions for Python and Forth also provided here too.

I am also finishing a paper presenting a mathematical/algorithmic
analysis and explanation of my method. This will explain why the SoZ
generators are computationally superior than the SoA and SoE.

An interesting result is the benchmarks under Ruby 1.9.0-1 are many
times faster than under “normal” Python, and even close compared to
Python using the psyco C optimizing library.

I’ve tried to run my Ruby code with JRuby, but I can’t get JRuby to
install correctly on my laptop (w/PCLinuxOS, Intel P4 2.8Ghz).
I would appreciate if someone would run my code under JRuby, Rubinius,
et al, and post results.

Jabari


#2

On Thu, Nov 20, 2008 at 9:33 PM, Frank Cameron > $ jruby
SieveOfZakiya.rb

Error, could not compile; pass -d or
-J-Djruby.jit.logging.verbose=true for more details
user system total real
primes up to 10000001: 10.529000 0.000000 10.529000 ( 10.528562)

$ jruby -J-Djruby.jit.logging.verbose=true SieveOfZakiya.rb
could not compile: SieveOfZakiya.rb because of: “Invalid method Code
length 78818 in class file SieveOfZakiya”
java.lang.ClassFormatError: Invalid method Code length 78818 in class
file SieveOfZakiya
at java.lang.ClassLoader.defineClass1(Native Method)
at java.lang.ClassLoader.defineClass(ClassLoader.java:637)
at
org.jruby.util.JRubyClassLoader.defineClass(JRubyClassLoader.java:22)
at
org.jruby.compiler.impl.StandardASMCompiler.loadClass(StandardASMCompiler.java:147)
at org.jruby.Ruby.tryCompile(Ruby.java:494)
at org.jruby.Ruby.tryCompile(Ruby.java:474)
at org.jruby.Ruby.runNormally(Ruby.java:453)
at org.jruby.Ruby.runFromMain(Ruby.java:337)
at org.jruby.Main.run(Main.java:214)
at org.jruby.Main.run(Main.java:100)
at org.jruby.Main.main(Main.java:84)
user system total real
primes up to 10000001: 10.125000 0.000000 10.125000 ( 10.125155)


#3

On Thu, Nov 20, 2008 at 3:46 PM, jzakiya removed_email_address@domain.invalid 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’ve tried to run my Ruby code with JRuby, but I can’t get JRuby to
install correctly on my laptop (w/PCLinuxOS, Intel P4 2.8Ghz).
I would appreciate if someone would run my code under JRuby, Rubinius,
et al, and post results.

$ uname -a
Linux ViBEStation-alpha 2.6.27-7-generic #1 SMP Fri Oct 24 06:42:44
UTC 2008 i686 GNU/Linux
$ cat /proc/cpuinfo | fgrep “model name”
model name : Genuine Intel® CPU T2400 @ 1.83GHz
model name : Genuine Intel® CPU T2400 @ 1.83GHz
$ cat /proc/meminfo | fgrep MemTotal
MemTotal: 1552052 kB

$ ruby1.8 -v
ruby 1.8.7 (2008-08-11 patchlevel 72) [i486-linux]
$ ruby1.9 -v
ruby 1.9.0 (2008-06-20 revision 17482) [i486-linux]
$ jruby -v
jruby 1.1.5 (ruby 1.8.6 patchlevel 114) (2008-11-03 rev 7996)
[i386-java]
$ java -version
java version “1.6.0_0”
IcedTea6 1.3.1 (6b12-0ubuntu6) Runtime Environment (build 1.6.0_0-b12)
OpenJDK Client VM (build 1.6.0_0-b12, mixed mode, sharing)

$ ruby1.8 SieveOfZakiya.rb
user system total real
primes up to 10000001: 12.060000 3.290000 15.350000 ( 15.416156)
primes up to 10000001: 16.500000 2.690000 19.190000 ( 19.257785)
primes up to 10000001: 4.530000 0.210000 4.740000 ( 4.748393)
primes up to 10000001: 18.600000 2.510000 21.110000 ( 21.313465)
primes up to 10000001: 11.830000 1.840000 13.670000 ( 13.736428)
primes up to 10000001: 9.470000 1.300000 10.770000 ( 10.836533)
primes up to 10000001: 8.810000 1.320000 10.130000 ( 10.169567)
primes up to 10000001: 6.640000 0.210000 6.850000 ( 6.901754)
primes up to 10000001: 4.650000 0.160000 4.810000 ( 4.859772)
primes up to 10000001: 4.000000 0.190000 4.190000 ( 4.261946)
primes up to 10000001: 7.780000 0.210000 7.990000 ( 8.005944)

$ ruby1.9 SieveOfZakiya.rb
user system total real
primes up to 10000001: 3.970000 0.020000 3.990000 ( 4.038134)
primes up to 10000001: 4.700000 0.040000 4.740000 ( 4.750093)
primes up to 10000001: 1.770000 0.050000 1.820000 ( 1.825153)
primes up to 10000001: 6.190000 0.080000 6.270000 ( 6.293999)
primes up to 10000001: 4.120000 0.080000 4.200000 ( 4.220465)
primes up to 10000001: 3.360000 0.060000 3.420000 ( 3.427870)
primes up to 10000001: SieveOfZakiya.rb:962: [BUG] Segmentation fault
ruby 1.9.0 (2008-06-20 revision 17482) [i486-linux]

$ jruby SieveOfZakiya.rb
Error, could not compile; pass -d or
-J-Djruby.jit.logging.verbose=true for more details
user system total real
primes up to 10000001: 10.529000 0.000000 10.529000 ( 10.528562)
primes up to 10000001: 14.105000 0.000000 14.105000 ( 14.105188)
primes up to 10000001: 7.248000 0.000000 7.248000 ( 7.248299)
primes up to 10000001: 15.564000 0.000000 15.564000 ( 15.564142)
primes up to 10000001: 11.170000 0.000000 11.170000 ( 11.170565)
primes up to 10000001: 8.735000 0.000000 8.735000 ( 8.734701)
primes up to 10000001: 9.330000 0.000000 9.330000 ( 9.330105)
primes up to 10000001: 11.366000 0.000000 11.366000 ( 11.365478)
primes up to 10000001: 8.015000 0.000000 8.015000 ( 8.015094)
primes up to 10000001: 12.421000 0.000000 12.421000 ( 12.420387)
primes up to 10000001: 14.079000 0.000000 14.079000 ( 14.079476)

$ python -V
Python 2.5.2

$ python Sieves.py
Traceback (most recent call last):
File “Sieves.py”, line 30, in
import psyco; psyco.full()
ImportError: No module named psyco

$ python Sieves.py
5 0.000430822372437 0.00113892555237 0.000353097915649
0.00146794319153 0.0988550186157
1000005 0.0542759895325 0.0466251373291 0.030809879303 0.0351409912109
0.318035125732
2000005 0.114179849625 0.104732990265 0.0793678760529 0.071692943573
0.142382144928
3000005 0.185572147369 0.170922994614 0.133031129837 0.12051987648
0.174972057343
4000005 0.268694877625 0.239547967911 0.192733049393 0.169470071793
0.171880960464
5000005 0.346322059631 0.307791948318 0.243360996246 0.21952009201
0.220386981964
6000005 0.43289399147 0.449116945267 0.302098035812 0.268841981888
0.269742965698
7000005 0.51304602623 0.448477983475 0.356249094009 0.31923699379
0.319150924683
8000005 0.598546981812 0.519491910934 0.415519952774 0.372243881226
0.374433994293
9000005 0.671094894409 0.591510057449 0.469482898712 0.424551010132
0.42044210434
10000005 0.757035017014 0.669479131699 0.5306661129 0.481162071228
0.471302032471
11000005 0.8411860466 0.747767925262 0.612731933594 0.523928880692
0.520886898041
12000005 0.920516967773 0.8079829216 0.652818202972 0.608549118042
0.570842981339
13000005 1.02680706978 0.879048109055 0.708424806595 0.627990007401
0.618942975998
14000005 1.08641910553 0.952656030655 0.779363870621 0.689521074295
0.667888879776
15000005 1.16809296608 1.02370405197 0.817245006561 0.72927904129
0.747013092041
16000005 1.24769997597 1.12631702423 0.87025809288 0.789395809174
0.765959024429
17000005 1.34199690819 1.16786408424 0.931406021118 0.826653003693
0.818248033524
18000005 1.41291308403 1.2686560154 0.988373041153 0.878173112869
0.867197990417
19000005 1.49461913109 1.34461092949 1.04254007339 0.94869184494
0.916136980057
20000005 1.58202815056 1.4249458313 1.1114461422 0.978127002716
0.96474814415


#4

On Thu, Nov 20, 2008 at 9:37 PM, removed_email_address@domain.invalid wrote:

et al, and post results.
primes up to 10000001: 8.735000 0.000000 8.735000 ( 8.734701)
primes up to 10000001: 9.330000 0.000000 9.330000 ( 9.330105)
primes up to 10000001: 11.366000 0.000000 11.366000 ( 11.365478)
primes up to 10000001: 8.015000 0.000000 8.015000 ( 8.015094)
primes up to 10000001: 12.421000 0.000000 12.421000 ( 12.420387)
primes up to 10000001: 14.079000 0.000000 14.079000 ( 14.079476)

$ jruby -J-server SieveOfZakiya.rb
Error, could not compile; pass -d or
-J-Djruby.jit.logging.verbose=true for more details
user system total real
primes up to 10000001: 6.195000 0.000000 6.195000 ( 6.194438)
primes up to 10000001: 11.389000 0.000000 11.389000 ( 11.388889)
primes up to 10000001: 6.085000 0.000000 6.085000 ( 6.085215)
primes up to 10000001: 12.252000 0.000000 12.252000 ( 12.252067)
primes up to 10000001: 7.555000 0.000000 7.555000 ( 7.555602)
primes up to 10000001: 6.153000 0.000000 6.153000 ( 6.153644)
primes up to 10000001: 5.805000 0.000000 5.805000 ( 5.805000)
primes up to 10000001: 9.916000 0.000000 9.916000 ( 9.916375)
primes up to 10000001: 9.148000 0.000000 9.148000 ( 9.147656)
primes up to 10000001: 13.169000 0.000000 13.169000 ( 13.169869)
primes up to 10000001: 16.541000 0.000000 16.541000 ( 16.540694)

$ jruby -J-Xmn128m -J-Xms1024m -J-Xmx1024m -J-server SieveOfZakiya.rb
Error, could not compile; pass -d or
-J-Djruby.jit.logging.verbose=true for more details
user system total real
primes up to 10000001: 6.087000 0.000000 6.087000 ( 6.086382)
primes up to 10000001: 9.360000 0.000000 9.360000 ( 9.360478)
primes up to 10000001: 3.681000 0.000000 3.681000 ( 3.681715)
primes up to 10000001: 10.023000 0.000000 10.023000 ( 10.022875)
primes up to 10000001: 8.585000 0.000000 8.585000 ( 8.585405)
primes up to 10000001: 5.008000 0.000000 5.008000 ( 5.007991)
primes up to 10000001: 5.066000 0.000000 5.066000 ( 5.065975)
primes up to 10000001: 6.416000 0.000000 6.416000 ( 6.415926)
primes up to 10000001: 3.556000 0.000000 3.556000 ( 3.556291)
primes up to 10000001: 4.631000 0.000000 4.631000 ( 4.631488)
primes up to 10000001: 3.163000 0.000000 3.163000 ( 3.163181)


#5

removed_email_address@domain.invalid wrote:

$ jruby -J-Xmn128m -J-Xms1024m -J-Xmx1024m -J-server SieveOfZakiya.rb

Error, could not compile; pass -d or
-J-Djruby.jit.logging.verbose=true for more details

Odd…the main script, or a method in it, must be gi-frigging-gantic to
blow out the bytecode cap. Glad to see in your results below that with a
bit of tweaking we’re on par with 1.9. I’ll look into the compilation
issue; I know there are a few cases that can still pop the compiler,
like really big arrays that require a lot of init.

                user     system      total        real

primes up to 10000001: 3.163000 0.000000 3.163000 ( 3.163181)

Much better! Pretty noisy on the warmup though.

  • Charlie

#6

On Nov 21, 1:31 am, Charles Oliver N. removed_email_address@domain.invalid
wrote:

issue; I know there are a few cases that can still pop the compiler,
like really big arrays that require a lot of init.

Yeah, there’s several methods there that could easily blow the cap and
have to remain interpreted. The inability to compile the whole file as a
result is probably a large part of the lower perf. The algorithm is also
extremely memory-intensive; logging GC on JRuby it had to do multiple
full collections before the first iteration even came back.

  • Charlie

I just uploaded a more memory efficient and faster upgrade.

Please check it out.

Jabari


#7

Charles Oliver N. wrote:

like really big arrays that require a lot of init.
Yeah, there’s several methods there that could easily blow the cap and
have to remain interpreted. The inability to compile the whole file as a
result is probably a large part of the lower perf. The algorithm is also
extremely memory-intensive; logging GC on JRuby it had to do multiple
full collections before the first iteration even came back.

  • Charlie

#8

jzakiya removed_email_address@domain.invalid wrote:

Please check it out.
Cool, I’ll try to give it a go on the same machine later today.


#9

On Nov 24, 2008, at 11:25 AM, jzakiya wrote:

Odd…the main script, or a method in it, must be gi-frigging-
have to remain interpreted. The inability to compile the whole file

Please check it out.

On a Mac Pro (2.8 Ghz). Jruby 1.1.5

cremes$ jruby -J-Xmn128m -J-Xms1024m -J-Xmx1024m -J-server
SieveOfZakiya.rb
user system total real
primes up to 10000001: 3.106000 0.000000 3.106000 ( 3.105799)
primes up to 10000001: 5.774000 0.000000 5.774000 ( 5.773820)
primes up to 10000001: 2.893000 0.000000 2.893000 ( 2.893756)
primes up to 10000001: 7.883000 0.000000 7.883000 ( 7.883993)
primes up to 10000001: 5.714000 0.000000 5.714000 ( 5.714248)
primes up to 10000001: 4.792000 0.000000 4.792000 ( 4.791677)
primes up to 10000001: 4.697000 0.000000 4.697000 ( 4.697211)
primes up to 10000001: 4.066000 0.000000 4.066000 ( 4.065598)
primes up to 10000001: 3.395000 0.000000 3.395000 ( 3.394890)
primes up to 10000001: 3.232000 0.000000 3.232000 ( 3.232953)
primes up to 10000001: 3.245000 0.000000 3.245000 ( 3.244323)

Rubinius (built as of 5 minutes ago from latest git pull).

I cancelled the run after an hour. It had not yet completed a single
run.

cr


#10

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)


#11

jzakiya removed_email_address@domain.invalid wrote:

Charles Oliver N. removed_email_address@domain.invalid wrote:

Yeah, there’s several methods there that could easily blow the cap and
have to remain interpreted. The inability to compile the whole file as a
result is probably a large part of the lower perf. The algorithm is also
extremely memory-intensive; logging GC on JRuby it had to do multiple
full collections before the first iteration even came back.

I just uploaded a more memory efficient and faster upgrade.

Please check it out.

$ ruby1.8 -v SieveOfZakiya.rb
ruby 1.8.7 (2008-08-11 patchlevel 72) [i486-linux]
user system total real
primes up to 10000001: 12.160000 3.280000 15.440000 ( 15.968446)
primes up to 10000001: 16.410000 2.710000 19.120000 ( 19.802800)
primes up to 10000001: 4.340000 0.300000 4.640000 ( 4.708012)
primes up to 10000001: 18.340000 2.510000 20.850000 ( 21.099350)
primes up to 10000001: 11.600000 1.750000 13.350000 ( 13.638693)
primes up to 10000001: 9.060000 1.450000 10.510000 ( 10.802420)
primes up to 10000001: 8.410000 1.260000 9.670000 ( 9.923761)
primes up to 10000001: 6.620000 0.200000 6.820000 ( 7.042592)
primes up to 10000001: 4.620000 0.210000 4.830000 ( 4.858175)
primes up to 10000001: 4.010000 0.210000 4.220000 ( 4.241419)
primes up to 10000001: 9.060000 0.230000 9.290000 ( 9.345546)

$ ruby1.9 -v SieveOfZakiya.rb
ruby 1.9.0 (2008-06-20 revision 17482) [i486-linux]
user system total real
primes up to 10000001: 3.870000 0.020000 3.890000 ( 4.007278)
primes up to 10000001: 4.670000 0.050000 4.720000 ( 4.884780)
primes up to 10000001: 1.710000 0.060000 1.770000 ( 1.818867)
primes up to 10000001: 6.020000 0.080000 6.100000 ( 6.291805)
primes up to 10000001: 3.970000 0.050000 4.020000 ( 4.189796)
primes up to 10000001: 3.170000 0.080000 3.250000 ( 3.355820)
primes up to 10000001: SieveOfZakiya.rb:1272: [BUG] Segmentation fault
ruby 1.9.0 (2008-06-20 revision 17482) [i486-linux]

$ jruby -v SieveOfZakiya.rb
jruby 1.1.5 (ruby 1.8.6 patchlevel 114) (2008-11-03 rev 7996)
[i386-java]
Error, could not compile; pass -d or
-J-Djruby.jit.logging.verbose=true for more details
user system total real
primes up to 10000001: 10.117000 0.000000 10.117000 ( 10.116355)
primes up to 10000001: 14.625000 0.000000 14.625000 ( 14.624596)
primes up to 10000001: 7.303000 0.000000 7.303000 ( 7.303146)
primes up to 10000001: 16.469000 0.000000 16.469000 ( 16.468992)
primes up to 10000001: 10.874000 0.000000 10.874000 ( 10.874482)
primes up to 10000001: 8.648000 0.000000 8.648000 ( 8.648109)
primes up to 10000001: 9.625000 0.000000 9.625000 ( 9.624519)
primes up to 10000001: 10.190000 0.000000 10.190000 ( 10.190249)
primes up to 10000001: 9.384000 0.000000 9.384000 ( 9.383951)
primes up to 10000001: 10.588000 0.000000 10.588000 ( 10.587707)
primes up to 10000001: 15.747000 0.000000 15.747000 ( 15.747025)

$ jruby -v -J-server SieveOfZakiya.rb
jruby 1.1.5 (ruby 1.8.6 patchlevel 114) (2008-11-03 rev 7996)
[i386-java]
Error, could not compile; pass -d or
-J-Djruby.jit.logging.verbose=true for more details
user system total real
primes up to 10000001: 6.457000 0.000000 6.457000 ( 6.457001)
primes up to 10000001: 11.203000 0.000000 11.203000 ( 11.202618)
primes up to 10000001: 5.599000 0.000000 5.599000 ( 5.599136)
primes up to 10000001: 12.384000 0.000000 12.384000 ( 12.384355)
primes up to 10000001: 7.844000 0.000000 7.844000 ( 7.844102)
primes up to 10000001: 6.420000 0.000000 6.420000 ( 6.420077)
primes up to 10000001: 7.478000 0.000000 7.478000 ( 7.478256)
primes up to 10000001: 8.779000 0.000000 8.779000 ( 8.778884)
primes up to 10000001: 8.752000 0.000000 8.752000 ( 8.752092)
primes up to 10000001: 10.061000 0.000000 10.061000 ( 10.060471)
primes up to 10000001: 11.674000 0.000000 11.674000 ( 11.674323)

$ jruby -v -J-Xmn128m -J-Xms1024m -J-Xmx1024m -J-server SieveOfZakiya.rb
jruby 1.1.5 (ruby 1.8.6 patchlevel 114) (2008-11-03 rev 7996)
[i386-java]
Error, could not compile; pass -d or
-J-Djruby.jit.logging.verbose=true for more details
user system total real
primes up to 10000001: 4.512000 0.000000 4.512000 ( 4.512570)
primes up to 10000001: 9.059000 0.000000 9.059000 ( 9.058663)
primes up to 10000001: 3.557000 0.000000 3.557000 ( 3.556361)
primes up to 10000001: 11.114000 0.000000 11.114000 ( 11.113504)
primes up to 10000001: 16.059000 0.000000 16.059000 ( 16.059220)
primes up to 10000001: 5.075000 0.000000 5.075000 ( 5.075088)
primes up to 10000001: 4.964000 0.000000 4.964000 ( 4.964077)
primes up to 10000001: 6.260000 0.000000 6.260000 ( 6.260179)
primes up to 10000001: 3.720000 0.000000 3.720000 ( 3.720471)
primes up to 10000001: 2.877000 0.000000 2.877000 ( 2.877802)
primes up to 10000001: 4.547000 0.000000 4.547000 ( 4.547695)


#12

On Nov 24, 3:35 pm, Lloyd L. removed_email_address@domain.invalid wrote:

consider this as psuedo code, it should give you an idea of what I am
flag_non_primes(2) # get all even numbers

You only need to start with the square of the number as everything


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